33.png 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第1张

Improved iterative scaling/IIS简介

改进的迭代尺度法Improved iterative scaling/IIS,在很多模型求解中用到,比如最大熵、CRFs等,对模型是对数线性模型的似然都适用。这个算法的思想也很简单,通俗的理解就是通过两个不等式变形优化下界,从而迭代到收敛的算法。

用到两个不等式,对 α>0 :

logα1α

对 p(x) 是一个概率密度函数

exp(x)q(x)xp(x)eq(x)

为了阅读方便,可以先记住上面两个不等式,至于为什么用这两个不等式变换,文章末尾有我个人简单的思考。

假设模型为:

Pλ(y|x)=1Zλ(x)exp(1nλifi(x,y))

其中 λ 是参数, Z(x) 是归一化因子。

似然函数可以写成:

L(λ)=x,yp~(x,y)logp(y|x)

其中 p~(x,y) 是样本(x,y)出现的频率。

接下来我们就是要找到合适的 λ ,找 λ 的过程可以看做是下面迭代过程:

λ=λ+Δλ

所以问题可以看做每次寻找一个 λ 的移动向量,然后不断迭代,接下来就是确定每一步如何找到 Δλ .一种容易想到的做法就是通过最大化两次迭代的差值,从而实现每一步得到最优的 Δλ 。

(1)L(λ)L(λ)=x,yp~(x,y)logpλ(y|x)x,yp~(x,y)logpλ(y|x)(2)=x,yp~(x,y)iΔifi(x,y)xp~(x)logZλ(x)Zλ(x)

对上面式子通过不等式 logα1α 可以改写为:

(3)L(λ)L(λ)x,yp~(x,y)iΔifi(x,y)+1xp~(x)Zλ(x)Zλ(x)(4)=x,yp~(x,y)iΔifi(x,y)+1xp~(x,y)ypλ(y|x)exp(iΔifi(x,y))

定义:

f#(x,y)=ifi(x,y)

可以将上式修改为:

L(λ)L(λ)=x,yp~(x,y)iΔifi(x,y)+1xp~(x,y)ypλ(y|x)exp(f#(x,y)iΔifi(x,y))f#(x,y))

对上面等式通过不等式: exp(x)q(x)xp(x)eq(x) 可以改写为:

L(λ)L(λ)x,yp~(x,y)iΔifi(x,y)+1xp~(x,y)ypλ(y|x)i(fi(x,y))f#(x,y)eΔif#(x,y))

上式直接对 Δλ 求导数,令导函数为0可以直接解出来 Δλ , 从而不断迭代达到收敛。

一些思考

不等式的选择问题,对于第一个不等式 logα1α 画图之后的效果:

11.png 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第2张

在坐标逼近(1,0)处,他们两个的值是无限接近,当迭代收敛的时候 Zλ(x)Zλ(x)1 ,刚好是在这个点。

第二个不等式以前没有接触过,但是容易想到的是凸函数的期望不等式,『期望的函数』小于等于『函数的期望』:

扩展阅读:  Improved Iterative Scaling算法以及JAVA实现

背景

IIS算法主要用来计算参数估计的maximum-likelihood。 这篇文章主要是解读Adam Berger的算法(IIS Algorithm)。首先这里采用的是概率模型。
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第3张
其中 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第4张
参数解释:
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第5张:表示再输入文档是x的情况下,输出label为y的概率。(在Adam的文章中这个是表示language modeling的一个句子概率问题,但是这里用于文本分类)。y就是你的模型中会包含有多少个的label,然后去判断你输入的文档属于每个label的概率,当然概率最大的就会判断哪一个。
:这个其实就是我们用IIS算法训练出来的权重,i的范围就是1到n,n就是你的所有training dataset 里面的feature总数。
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第6张:就是feature function了。我这里feature function的定义就是,如果在一篇文章里 word[i] 属于 document x并且 word[i] 也属于label y就为1,否则为0.
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第7张
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第8张:是用在标准化的,使得概率在0到1之间。
:这个是表示 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第9张 .

Improved Iterative Scaling算法

Maximum-likelihood

首先我们构造基于对数的log-likelihood.
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第10张
这里的 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第11张 表示<x,y> pair出现在dataset中的概率,一般都是.。 然后具体的推导不在这里详细详述,推导可以看adam上的论文,我这里直接把结果给出来。因为要求最大的可能性,所以我们需要求这个公式的最大值,就是说对这个公式就导,求导的话,因为有n个值,所以就要求n次偏导数。从而求到每一个的.

因为这个式子优化还是比较麻烦,所以Adam文章中采用办法就是一点一点的迭代。原理就是如果我们能够找到一个使得下面的式子成立就可以了。
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第12张
而且又有 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第13张
所以只需要上式右边的式子大于0即可,可以看到现在要求的变量变成了。 然后论文最后,再继续优化上式,得到一个式子可以单独的求取,如下:
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第14张
其实就是表示在<x,y>这个pair中的所有的feature,在文本分类模型中,就是总共有多少种feature(注意不是多少个.)
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第15张
因为这里可能每一个的都会不一样,所以可能需要用牛顿迭代求解的方法去求解。但是,其实有两篇文章(忘了什么名字了)都证明只需要取最大的来代替就可以了,就是说我们希望计算的方便。
所以我们这里选择:
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第16张 针对所有的x 和y.
最后可以得到的表达式:
 改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第17张 

IIS算法流程

第一步,随便选择,一般初始化每一个都是0.

第二步,不断执行一下的操作收敛为止,一般很快。

-----求解, 用上面最后推导出来的式子
-----Set  改进的迭代尺度法:Improved iterative scaling/IIS 人工智能算法大全_AI算法 第18张



算法的实现和模型训练测试

这里因为代码太长不可能完全放出来,所以打算讲解一部分的核心代码然后把完整代码和数据都放到出来大家下载好了。
首先是feature function的定义。
/*** feature function* wordInLabel[c] is a map, to denote that if this word is also in this label.* Note: a word can belongs to many labels.* allFeature List has contained all the words in training dataset* @param i: denote the word[i] in document d* @param d: doc[d], the number of this document* @param c: the label of this document* @return*/private int featureFun(int i,int d,int c){if(doc[d].getDoc().containsKey(allFeature.get(i)) && wordInLabel[c].containsKey(allFeature.get(i)))return 1;else return 0;}
doc 是我定义的一个document的结构,这个结构里面包含一个 map<word,value>容器的document, key是单词,value是这个单词在这个document中出现的次数。这个结构另外一个成员就是label. 就是这篇document的label.主要是用在训练过程中,测试过程不需要。
接下来直接上训练阶段的核心代码,就是不停迭代求解然后更新的过程。
/*** Train the data.* getExponentialProb(x,y) function is used to calculate p(y|x)* lamda[] is the final weight coefficients we can get.* @param times: the iteration time, depends on your choice*/private void trainData(int times){lambda = new double[allFeature.size()];double[] delta = new double[allFeature.size()];for(int t=0;t
上面的 this.NUMERTOR[I]是因为我们仔细看上一部分求的,显然分子和是没有关系的,所以我已经预处理在另外一个方法中计算存储起来,这个也是空间换时间的一个概念。
在测试阶段,我通过预测每个label的概率然后进行比较,得到概率最大的那个label. 先给出测试的代码,然后最后给出结果。
/*** Get the error rate, remember run the startUp function first* Get the error rate of our model.*/public void testModel(){int ein = 0;for(int d=0;dmax){max = p;maxType=labelType.get(type);}}res+=" Best:"+maxType+" True:"+doc[d].getLabel();if(!maxType.equals(doc[d].getLabel()))ein++;System.out.println(res);}System.out.println("error rate is:"+ein*1.0/doc.length);}

测试数据采用的是 Reuter21578的数据,用了其中的4种类型,acq, coffee, fuel and housing.
Best::就是这个算法中预测出来的最好的,就是概率最大的。True:就是真正测试中的结果。
coefficient vector size:1728acq[0.3559] coffee[0.3012] fuel[0.2457] housing[0.0972] Best:acq True:acqacq[0.2893] coffee[0.2815] fuel[0.2438] housing[0.1853] Best:acq True:acqacq[0.2704] coffee[0.2562] fuel[0.2565] housing[0.2170] Best:acq True:acqacq[0.3340] coffee[0.2252] fuel[0.2659] housing[0.1749] Best:acq True:acqacq[0.2990] coffee[0.2590] fuel[0.2466] housing[0.1955] Best:acq True:acqacq[0.2904] coffee[0.2416] fuel[0.2544] housing[0.2136] Best:acq True:acqacq[0.2978] coffee[0.2767] fuel[0.2406] housing[0.1848] Best:acq True:acqacq[0.3844] coffee[0.2638] fuel[0.2282] housing[0.1236] Best:acq True:acqacq[0.2855] coffee[0.3156] fuel[0.2547] housing[0.1442] Best:coffee True:coffeeacq[0.2486] coffee[0.2780] fuel[0.2744] housing[0.1989] Best:coffee True:coffeeacq[0.2407] coffee[0.2871] fuel[0.2596] housing[0.2126] Best:coffee True:coffeeacq[0.2788] coffee[0.2859] fuel[0.2580] housing[0.1773] Best:coffee True:coffeeacq[0.2518] coffee[0.2501] fuel[0.2518] housing[0.2464] Best:acq True:coffeeacq[0.2850] coffee[0.2646] fuel[0.2532] housing[0.1972] Best:acq True:coffeeacq[0.2348] coffee[0.2692] fuel[0.2735] housing[0.2224] Best:fuel True:coffeeacq[0.2382] coffee[0.2678] fuel[0.2727] housing[0.2214] Best:fuel True:coffeeacq[0.2548] coffee[0.2632] fuel[0.2859] housing[0.1962] Best:fuel True:fuelacq[0.2733] coffee[0.2613] fuel[0.2541] housing[0.2113] Best:acq True:fuelacq[0.2844] coffee[0.2530] fuel[0.2727] housing[0.1899] Best:acq True:fuelacq[0.2421] coffee[0.2345] fuel[0.3366] housing[0.1867] Best:fuel True:fuelacq[0.2579] coffee[0.2519] fuel[0.3093] housing[0.1809] Best:fuel True:fuelacq[0.2435] coffee[0.2466] fuel[0.3049] housing[0.2050] Best:fuel True:fuelacq[0.2871] coffee[0.3343] fuel[0.2452] housing[0.1334] Best:coffee True:fuelacq[0.2738] coffee[0.2191] fuel[0.3157] housing[0.1914] Best:fuel True:fuelacq[0.2450] coffee[0.2397] fuel[0.2450] housing[0.2702] Best:housing True:housingacq[0.2202] coffee[0.2054] fuel[0.2335] housing[0.3409] Best:housing True:housingacq[0.2350] coffee[0.2372] fuel[0.2393] housing[0.2885] Best:housing True:housingacq[0.2340] coffee[0.2361] fuel[0.2382] housing[0.2917] Best:housing True:housingacq[0.3156] coffee[0.2897] fuel[0.2219] housing[0.1728] Best:acq True:housingacq[0.2340] coffee[0.2238] fuel[0.2475] housing[0.2947] Best:housing True:housingacq[0.2431] coffee[0.2383] fuel[0.2481] housing[0.2706] Best:housing True:housingacq[0.2525] coffee[0.2460] fuel[0.2737] housing[0.2278] Best:fuel True:housingerror rate is:0.28125accuracy: 71.75%
其实做了另外一个实验发现用binary classification 的结果更好,就是首先预测
acq- not acq
coffee - not coffee
fuel - not fuel
housing -not housing.
然后最后在combine 这四个结果,得到的准确率会更高。

最后其实我也把IIS模型和 maxent里面已经实现了的GIS模型对比了,发现GIS的收敛的确比IIS慢一点,但是GIS的迭代速度更快。我觉得可能是我的算法写的不好,比较慢。有兴趣的可以尝试用用OPENNLP 的maxent 包。

代码和数据下载

因为我貌似没有找到上传附件的地方,所以我放到百度云上让大家下载吧,下面是连接。