用琴生(Jensen)不等式证明期望最大值(EM)算法收敛

今年二月份刷了一遍“机器学习白板推导”系列视频。https://www.bilibili.com/video/BV1aE411o7qd 。这个机器学习的公式推导系列讲地真是太好了,当时像追剧一般花了两个星期听完。非常感谢录这个视频系列的老师shuhuai008。不过,因为以前机器学习的基础几乎为0,又没有动手做相关练习。三个半月以后,又忘了很多了。昨天,我想起要复习一下EM算法,于是又把视频捡起来找到EM算法的部分,复习一下。

第二次看,果然快了很多。不过,在用琴生不等式证明EM算法收敛的部分,卡住了。我不断回忆第一次看的时候是如何理解的,奈何回忆不起来了。于是,找到Jensen不等式的词条看了看,琢磨了好久。终于懂了,在这里把这个思考过程记下来。

我卡在这个步骤:需要用Jensen Inequality证明如下不等式:
\(
\int\limits_z P(z|x, \theta^{(t)}) \log_{}{\frac{P(z|x, \theta^{(t+1)})}{P(z|x, \theta^{(t)})} } dz \le 0
\)
上面公式中的z表示模型中的隐变量,x表示观测值,$ \theta $是参数,$ \theta^{(t)} $表示theta在第t时刻的值(EM算法是一个迭代算法)。

证明这个不等式需要用到琴生不等式在凹函数上的性质。如下:
设f(x)中一个凹函数(凹函数图形和中文字凹的形状相反,可以理解为上凸,log函数即一个凹函数),下面的不等式成立。
$$
a_1f(x_1) + a_2f(x_2) + \dots + a_nf(x_n) \le f(a_1x_1 + a_2x_2 + \dots + a_nx_n)
且 a_1 + a_2 + \dots + a_n = 1
$$
用自然语言描述是:凹函数定义域内的n个自变量对应的因变量的线性组合小于或等于n个自变量先做线性组合再求对应的因变量,作线性组合的系数之和为1。简单地说:先求函数值再做线性组合 小于或等于 先做线性组合再求函数值。

再回到我们要证明的不等式。积分号即可看成是无穷多个值的线性组合,对数符号log后面对应的那一坨
$$ {\frac{P(z|x, \theta^{(t+1)})} {P(z|x, \theta^{(t)})} } $$
看成是log函数的因变量,log前面的
$$
P(z|x, \theta^{(t)})
$$
看成是线性组合的系数,很明显这个系数是满足积分和为1的概率密度。于是,就可以套用上面提到的凹函数上的琴生不等式。不等式的右边为0,左边是“先求函数值再做线性组合”,化简为左边小于“先做线性组合再求函数值”:
$$
\begin{aligned}
左边 &\le log_{}{\int\limits_z {\frac{P(z|x, \theta^{(t+1)})} {P(z|x, \theta^{(t)})} } P(z|x, \theta^{(t)})}dz \&=log_{}{}\int \limits_zP(z|x,\theta^{(t+1)})dz=log_{}{1}=0
\end{aligned}
$$
得证!

A very brief Introduction to Neural Network.

 

I have huge interests in the mysterious Artificial Intelligence. Because of the lack of time to devote into learning AI, I still barely know AI related theories. Tonight I read something about Neural Network, which plays a important role in the AI field.
 
So, what is A NEURAL NETWORK?
A neural network is a massively parallel distributed processor made up of simple processing units that has a natural propensity for storing experiential knowledge and making it available for use. It resemble the brain in two respects:
knowledge is acquired by the network from its environment through a learning process.
Interneuron connection strengths  known as synaptic weights, are used to store the acquired knowledge.
 
Let us take the human vision as an example to demonstrate why it is necessary to study neural network. Human vision is a very complex information processing task. It is the function of the visual system to provide a representation of the the environment around us and to supply the information we need to interact with the environment. The brain accomplishes recognition task at the same time. For instance, the brain can recognize a familiar face embedded in an unfamiliar scene in shorter than a blink of eye, actually 100-200ms, whereas tasks of much lesser complexity take a great deal longer on a very powerful computer.
 
What's the reason makes the biological brains so efficient? How to let our machines think and do reasoning like biological brains do. The course of Neural Network has been trying to answer these questions from the day the course was established.
A typical neural network has many useful properties and capacities. 1. Nonlinearity 2. Input-output Mapping 3. Adaptivity 4. Evidential Response 5. Contextual Information 6. Fault Tolerance 7. VLSI(Very Large Scale Integrated) Implementability. 8. Uniformity of Analysis and Design 9. Neurobiological Analogy.
 

十分钟,教你创建自己的聊天机器人

这几天在网络上闲逛发现一个帮助你创建聊天机器人(Chat Robot)的网站。尝试了一下,很有意思呀!

关于人工智能(AI Artificial Intelligence)是我一直感兴趣的领域,但一直未能分出时间系统学习。目前为止,知道的最深入的也只是基于贝叶斯统计算法的专家系统。至于机器学习,还有神经网络哥一点都不懂哈!希望以后能有时间学习并应用。

言归正传。我发现的这个帮助你快速创建在线聊天机器人的网站是 http://www.pandorabots.com  。你在这个网站注册以后就只需要几步就可以创建一个WEB页面上的聊天机器人了。这个网站的机器人技术是基于AIML语言的。前几天写过一篇关于AIML的博文,可以参考下。前期工作来自于自由软件设区 www.alicebot.org。Pandorabots网站上的About介绍里说该网站还在继续语音识别,TTS(语音合成)等方面的研究,不过据我观赛。已经好久都没有更新了喔。

STEP ONE:在pandorabots的首页,找到Sign-up for an Account,按ctrl+F 搜索一下 Sign,就能马上定位到了。点击这个链接就可以注册一个账号了。

STEP TWO:和大多数注册过程一样,填上一些最基本的信息就注册成功。记得勾选上 By checking this box and clicking on the button labeled “Submit Account Request” you are agreeing to the Term Service 复选框。点击 SUBMIT ACCOUT REQUEST.

STEP THREE:接着网站提示: There are no Pandorabots defined yet. You must first create a new  chat robot。点击 create 单词上的链接。

STEP FOUR:  接着是聊天机器人最基本的设定。

Name:      // 这里填上你要创建的机器人的名字。

– automatically discover spaces between words (suggested for Japanese)   // 建议勾选上,因为中文和日文都没有用空格分词。

Startup AIML – Please select the AIML set you wish to include:     // 让你选择你创建的机器人的知识库。不要选最后一个就好!因为最后一个是没有任何知识库~你需要从头开始创建。但如果你喜欢从头开始。那就选最后一个吧。

– Standard AIML – Sept 2001
– Dr Wallace's A.L.I.C.E – March 2002
– Annotated A.L.I.C.E. AIML – September 2003
– Christian Drossmann's standalone German AIML – January 2002
– Sandro Pons' Italian AIML set – April 2001

– No initial content, the pandorabot starts with no knowledge.

点击下面的 Create Chat Robot 按钮,完成创建。

STEP FIVE: 于是你看到了一个界面,上面有各种按钮。你可以一个一个试试看看有什么功能。最重要的就是选 TRAIN 菜单项,你就可以开始训练你的机器人了。在 HUMAN ASK 栏里填上人类要说的话,然后在 SAY INSTEAD前面的框框里填上聊天机器人要回答的话,于是一条规则就创建好了。当然一般情况下会提示匹配到了某条规则,机器人会如何回答,你可以看到当前机器人会如何回答。可以支持中文喔。比如我要教机器人回答“你是学生吗”?

Human: 你是学生吗
Matched:
*   (category defined in star.aiml )
zzz: A deeper algorithm is needed to respond to that correctly. 

zzz是我刚创建的机器人的名字,上面提示当前聊天机器人不知道如何回答。因为基本上没有人用中文教过他。其它他已经对英文回答得相当好了。

那么,我可以教他回答: 我是。 再选择 SAY INSTEAD。

STEP FIVE: 下面我们可以验证下。

在菜单项里找到你的机器人的名字那个菜单项,右上方有个小星号。打开新页面后选择下面的 PUBLISH。然后会有一个链接给你,你点击这个链接。就可以和你的机器人聊天啦。看看我的:

Human: Because you are so stupid                    // 我说因为你好笨呀

zzz: Interesting explanation. Wrong. I am smart.          // 它说:你的解释真有意思,但是错了,我很聪明呢

Human: Are you a robot                                   // 问它你是机器人吗
zzz: How did you know I am a machine?    // 它回答: 你怎么知道我是机器。

Human: what's your name                           // 对英文回答得很好
zzz: My name is zzz.

Human: 你叫什么名字                                        # 不识别其它中文
zzz: I will mention that to my botmaster, . 

Human: 你是学生吗                                           # 这是刚才教他的。
zzz: 我是,我在中山大学读书。

 

是不是很有趣呢? 还可以教他广东话喔。

本博原创,转载请注明出处 http://blog.ykyi.net/2012/06/%E5%8D%81%E5%88%86%E9%92%9F%EF%BC%8C%E6%95%99%E4%BD%A0%E5%88%9B%E5%BB%BA%E8%87%AA%E5%B7%B1%E7%9A%84%E8%81%8A%E5%A4%A9%E6%9C%BA%E5%99%A8%E4%BA%BA/ 谢谢喔

什么是AIML,人工智能标志语言

 

 

AIML是Artificial Intelligence Markup Language的缩写。这种语言基于XML,它易学习易掌握。使用AIML可以很容易的定制一个Alicebot或者从头开始创建一个Alicebot。Alicebot是种聊天机器人,参见http://www.alicebot.org/ 。

下面简单的介绍下AIML的语法。

AIML语言中最重要的四个标志:

· <aiml>: 这个标签用来标志一个AIML文档的开始和结束。

· <category>: 这个标志表示在Alicebot的知识体系里暂时无法理解的东西。

· <pattern>: 用来描述一个简单的模式表示用户会同Alicebot说什么。

· <template>: 用来描述Alicebot的回复。

还有20余种标签会在AIML文件中经常碰到。你也可以创建你自己的“定制标签”。现在就开始学习使用AIML吧,这里有一个初级教程 AIML Primer

举例说明吧。免费的A.L.I.C.E. AIML 已经包含了一个基本的知识库,描述了大概41,000个category。看这个例子:

<category>
    <pattern>WHAT ARE YOU</pattern>
    <template>
        <think><set name="topic">Me</set></think> 
        I am the latest result in artificial intelligence,
        which can reproduce the capabilities of the human brain
        with greater speed and accuracy.
    </template>
</category>

<aiml>标签在这里没有显示出来,因为这里只是文档的一个节选。

如你所见<categoray>与</category>之间,就是描述一个category啦!每个category可以有一个pattern和一个template,还可以有一个<that>标签的,但是我不想在这里讨论它。

如上的category中的pattern只能够匹配精确的"what are you"(大小写忽略)。What are you 你不会不认识吧,好吧,直译是"你是什么东西啊?"

每个category还有可能被另外一个category调用,此时使用<srai>标签,这里也不作深入讨论。可以参见reductionism. Reductionism大根是还原论,简约化的意思。很难译出!

不管哪种情况,如果这个category被激发了,alicebot就会回答:"I am the latest result in artificial intelligence…" ,前面<template>里面的东东。意思是:我是最先进的人工智能的产物。我能够以超快的速度和准确度模拟人脑的功能。另外,还有一些其它有趣的事情发生呢。注间到<think>标签吗?这会让Alicebot联想到这个对话的相关的一个限制,比如上面的例子就告诉alicebot,这个对向在讨论你自己。set name="topic",又赋值Me。于是对于alicebot的其它N多category,同样是topic的值为Me的category会被优先采纳。由此,这个机制能让你更好更准确的控制对话的流程。想想还有更多的机制呢,就看你的创造力设计一个聪明的聊天机器人啦!