翻译:次梯度以及一阶最优性条件(Subgradient and First-order Optimality Condition)

本文是对文章Basics of Convex Analysis的部分翻译,若本文对您的任何权益造成侵犯,请联系我。

This article is a partial translation of Basics of Convex Analysis, if this infringes any of your rights, please contact me.


次梯度以及一阶最优性条件

若下述不等式成立:

则我们说是函数点上的一个次梯度,并且属于在该点(用表示)的一个次微分。

上述不等式表明函数的图像(graph)是由不等式右侧定义的超平面所(hyperplane)支撑的。一个次梯度因此也是这众多支持超平面其中一个的“斜率(slope)”。如果该函数在点处可微,则这样的次梯度有且仅有一个(即标准梯度),与此对应地,也只有一个支持超平面。相对地,如果一个函数在点处不可谓(比如,在处有个扭曲)那么就能有无穷多个支持超平面,并且相对应地,在该点的次微分是一个连续的次梯度的集合。

一个典型的例子是绝对值函数,它在0点是不可导的。但在这个点上,它可以由组成的所有直线支持。这个集合即该函数在0点的次微分,用表示。

函数的演示(粗线表示)以及其中两个支持直线(虚线表示)。这两条支持直线都有次微分中的斜率。注意,那条水平线也是支持超平面之一,表明。并且因此由一阶条件(下文定义),这个函数在原点有一个极小值。

现在,通过定义非限制问题中的一个最优点,必有,并且因此0必须是函数点处的一个子梯度。

这就是一阶最优性条件(FOC):

如果我们将次微分看做一个运算符那么,直观地,寻找极小可以看做“逆转”次微分并计算它在点0的值的过程,即。我们稍后再进一步介绍,但这个逆转次微分运算符的思路是非常重要的。

在继续之前,有必要提一下(并且这并不难理解)下述包含关系对于次微分的和是成立的:

对关注的大部分问题而言,上述关系可以强化为相等的关系, 但注意如果,则上述包含关系意味着,这对于证明是个极小值而言(这正是我们最感兴趣之处)足矣。


 

LeetCode 47. Permutations II

用回溯法完成,跟普通排列问题不同的是,需要排除掉一些重复“路径”。

可以这样做,先把输入数组排个序,这样重复的数就在相邻位置了。随后在回溯探求的过程中,我们要保证相同值的两个数nums[i], nums[j],如果i<j,那遍历只能有一种次序:nums[i]先,nums[j]后。

换句话说,就是判断这种情况是需要提前终止的:两个数nums[i]==nums[j] && i<j,但是nums[i]还没有被遍历。所以找个东西记录一下访问就行了。

时间复杂度是O(N!),空间复杂度是O(N)

 

LeetCode 368. Largest Divisible Subset

思路:

想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续…

时间复杂度应该是O(n^2)

 

LeetCode 424. Longest Repeating Character Replacement

思路很重要。

给定一个长度n的字符串s和限制k,将s中的部分字符替换(替换次数<=k)后,能得到连续字符(如AAAA)的长度最大为多少?

使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值(可以看做分布情况)以及当前窗口的起始点,窗口内最多字符的计数best。我们知道,最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话,就得把窗口缩小(起始点后挪)。窗口缩小时记得把窗口计数更新一下。

这里有一个tricky的地方,best值本来在滑动窗口的时候是要更新的,因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值,所以这个情况并不需要考虑对best进行更新,反正它也成不了最优。

代码

 

LeetCode 295. Find Median from Data Stream

题目大意是给定一个int数据流,判断当前整个数组的中位数值。由于数据流是可以不断增加的,因此采用两个堆(最大堆*1+最小堆*1)来实现。

这东西思路网上都有,每次新进一个数,维护堆就行了。维护一次的复杂度是O(logN),对应整个数组的复杂度是O(N logN)

STL 堆相关的三个函数 make_heap(), push_heap(), pop_heap()

STL是个好东西,在<algorithm>库里面就有三个与堆有关的函数,利用vector存储堆元素就可以调用这些函数来建立、更新堆。

make_heap(first, last, comp)是建立堆的函数,输入的first, last对应begin()和end()的iterator,comp函数可选,与库中sort()用到的方法相同,自定义的时候比较两个元素x, y的偏序关系,返回true说明x应该排在前面。相关的有两个仿函数叫less<T>() 和greater<T>(),直接用来比较<和>关系的。

push_heap(first, last, comp)使用时,将新元素放在数组末尾(代表堆的末叶节点),然后调用这个函数更新堆,是一个sift-up的过程。

pop_heap(first, last, comp)会将堆顶元素调整到数组末尾用于pop,同时调整更新堆。

代码

 

LeetCode 51. N-Queens

八皇后问题的延伸版,回溯实现。

 

基于单词的统计翻译模型 IBM Model1

统计翻译模型的基本思想是对大量平行(parallel)语料进行统计分析。之前实习的时候有幸接触到一些简单的模型,而事实上这种简单的模型在大量数据训练的基础上,发挥还是挺不错的。

IBM的统计翻译模型从简单到繁琐,一共有Model1-Model5五个模型,全都是基于词的统计模型。

本文只对Model1作简单介绍,方便起见,文中以将法文(French)翻译为英文(English)为例。

噪声信道模型。机器翻译=翻译模型+语言模型

模型假定源语言中的(法语)句子是由目标语言(英语)经过含有噪声的信道编码后得到的。寻找最佳的英文翻译结果等同于寻找

根据贝叶斯公式,容易得到,由于对于同一个法语单词来说,是一定的,因此上式等同于,其中

  • 称为翻译模型,即给定信号源,观察到信号的概率;
  • 称为语言模型,即信号源发生的概率;

机器翻译的任务就被拆解成这两个模型的任务了。本文只负责翻译模型:)

词对齐(Alignment)

Word Alignment

我们假设要翻译的法语句子包含m个单词,即,翻译出来的英语句子包含l个单词,即,那么之前提到的翻译概率其中包含了对句子长度服从这么个条件分布的假设。

然而这个概率是很难直接建模的,于是一帮聪明的人想出来一个方案:引入词对齐(word alignment):,其中这个a就是词对齐,它是个隐变量,表示源语言(法语)中的某个单词是用目标语言(英语)翻译而来的。

具体可以看这个例子:

这个例子中,,一个理想的对齐方式如下:

它对应的alignment标记可以表示为

此外在英文中还有加入个特殊的NULL单词,它表示法语中那些对于英语翻译“无用”的词。

IBM Model 1:翻译模型=对齐+词-词翻译

根据之前单词对齐的假设,我们可以把翻译任务进一步拆分成两部分:对齐和词到词的翻译,边际化参数A

第一部分是对齐,在Model 1中做了一个最简单的假设:每个对齐都是等概率发生的。所以

第二部分是词-词翻译,也是整个模型的核心部分,这里当然不能再精简了,否则就没有了…

这里头的就是单词到单词的翻译概率,也就是模型要学习的东西。

模型训练:期望最大化(EM)

很显然,要学习到词-词翻译概率,就必须知道单词对齐;要学习单词对齐,就得知道翻译概率,这种鸡生蛋的问题就需要用EM来解。

定义一个参数表示第k组平行预料(训练集中法文-英文句子)里的第i个法文词,第j个英文词。如果是上帝模式,那分别表示这两个词之间应当/不应当对齐。然而目前无人能观测到这个隐变量,所以采用最大似然估计来估计这个东西,意思就是说翻译概率的大小决定了单词对齐的概率,即

注意上面这个式子是根据Model 1“句子中的对齐都是等概率”假定推导来的:

算法

输入:训练集其中,其中

初始化:初始化所有词-词翻译概率

步骤:关键部分我用绿色的字注释了

  • for t=1…T
    • Set all counts
    • for
      • for
        • for
          • // word(i,j) in parallel corpus line k
          • //estimate alignment
          • //update co-occurence count for word-word pair
    • //update word-word pair translation probabilities

输出:

 

参考文献

  1. http://www.cs.columbia.edu/~mcollins/courses/nlp2011/notes/ibm12.pdf
  2. http://cpmarkchang.logdown.com/posts/245418-mt-ibm-model-1
  3. https://zh.wikipedia.org/wiki/%E7%BB%9F%E8%AE%A1%E6%9C%BA%E5%99%A8%E7%BF%BB%E8%AF%91

Information Cell Mixture Models 语义细胞混合模型

语义细胞混合模型是用于表示模糊概念的一种模型,我个人的理解嘛,是一种介于k-means与GMM之间的一个模型。具体论文可以看

Tang, Yongchuan, and Jonathan Lawry. “Information cells and information cell mixture models for concept modelling.” Annals of Operations Research195.1 (2012): 311-323.

下面做一些简要介绍。

基本概念及假设

一个语义细胞混合模型(Information Cell Mixture Model, ICMM)是由一组语义细胞构成的,每个语义细胞使用三元组表示,这三个符号分别表示原型,距离函数以及密度函数。其中原型的概念类似于k-means中的聚类中心,而距离、密度刻画了这个聚类中心的“势力范围”。下图就是一个例子,这个ICMM里面有两个语义细胞。

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8810-48-58

ICMM的概率密度

假设一个ICMM由个语义细胞构成,则可以根据每个语义细胞自身的概率密度函数及这个细胞的权重来界定整个ICMM的密度函数如下

而每个语义细胞自身的密度函数,由一个指定的距离函数(文中用欧氏距离)和一个概率密度函数(文中用高斯密度函数)一起界定,即

表示到X与原型的”距离”密度,而是一个高斯密度函数.

上面这堆都是密度函数,最后算出来是个距离(也可以称之为相似度)的密度,那如果要求真正点X到ICMM的“距离”,就需要求密度函数在范围的积分了。

目标函数

跟其他的生成模型类似,就是最大似然估计,目标函数也就变成了整个(对数)期望最大化了。

其中DB表示数据集,k是训练集的样本,i是第i个语义细胞。

但是上面这个对数似然函数很难优化,因此引入一个隐含变量并且有,它表示由某一个语义细胞“生成”了整个ICMM。

参数更新

语义细胞的概率分布更新

引入了隐变量,很容易想到用EM来更新参数… EM就是两个步骤:1.利用现有的参数去更新隐变量;2.利用隐变量来更新参数

在我们的问题中,用隐变量的最大似然估计来更新,即

这里的参数c, sigma, Pr, L全都是有hat的hypothesis值,鄙人不熟悉latex,没有加上。

然后,之前的那个目标函数就转变为了

这是一个带有约束条件(Pr权重加起来=1)最优化目标函数,所以引入Lagrange乘子来进行变换。变换后的目标函数求最值的问题,就可以转化为偏导数=0的问题了。

更新语义细胞的概率密度

没错,又是“退而求其次”。上面写的那个目标Q,展开来是有一个高斯分布函数项的(见原文公式9),这样对Q最优化又有难度了。作者退了一步,,因为高斯分布是个[0,1]的值,它的ln是负数,因此把这一项去掉,相当于加上了一个负数值的.

假设这个精简版的优化目标函数叫U,显然就有,相当于U就是个lower-bound

那如果能不断提高U的话,原有的目标函数也能得到优化。还是类似,求最值=偏导数为0,在本文中就是以及

解出来是这么两坨:

%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-48-39

参数更新算法

终于..可以更新参数了,具体算法如下

  1. 利用k-means算法找出k个语义细胞的原型,初始化每个语义细胞的权重
  2. 计算训练集到当前原型的距离,这里用的是欧氏距离;
  3. 初始化距离密度函数的参数%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-52-42
  4. 计算第一轮的隐变量%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-53-24
  5. 迭代更新(EM),直到目标函数J收敛
    1. 更新权重参数%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-55-40
    2. 更新密度函数的两个参数%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-56-24
    3. 利用更新后的参数,重新计算隐变量(的MLE)%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-10-09-%e4%b8%8b%e5%8d%8811-57-57
    4. 计算目标函数J

GMM与ICMM

GMM与ICMM长得比较像,我觉得ICMM算是GMM的一个简化版本。GMM求的是每个样例做高斯分布的参数,而ICMM事先就假定好了有k个“原型”,先做了一轮k-means固定下了原型,再来做密度函数的参数更新。假设有N个sample,GMM就相当于是k=N的ICMM。因此从计算复杂度上来说,ICMM比GMM简单,当然了ICMM能表示的模型复杂度还需要调参(k)才能进一步优化。

TensorFlow学习: 训练个ReLu神经网络(单隐层、双隐层)

其实是UdaCity上的深度学习公开课,感觉这个讲的最简洁明了。

下面的代码训练的是一个单隐层全连通的小小神经网络,隐层节点数量设定为1024,输入的图片是28*28的,label有’A’-‘J’共10个,所以最后用了softmax。数据使用nonMNIST的。参数更新用的mini-batch的SGD.

ReLu nonMNIST single hidden layer

下面是关键部分代码,这个课程的一个好处是用Docker+jupyter做的,给答案很方便,以前从未体验过这么流畅的哈哈哈。

输出如下:

随后又试了一下有两个隐层的ReLuNet,隐层节点数分别是1024,512,使用AdamOptimizer训练,似乎准确度又能提高一点点

迭代次数=5000,miniBatch的大小没有变

LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路

基本思路是,假设当前运行到nums[i]的位置,则需要往前看k个数,并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题(问题就转变为:找到第一个>=nums[i]-t的数,判断他是否<=nums[i]+t)。整个算法的时间复杂度是O(N * logk),N为数组长度。
下面代码中用set实现,set是用红黑树实现的。

代码