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是用红黑树实现的。

代码


 

LeetCode 223. Rectangle Area

题目

题目大意是给定两个长方形的坐标,计算他们一起覆盖的面积。

总的思路很简单,Area_A + Area_B – Overlap,具体求重合的面积则需要计算重合区域的两个坐标点。

那么就要分情况讨论,以重合区左下角点的横坐标为例,需要判断点E与横坐标AC的位置关系,即三种:E<A; A<E<C; C<E。

代码

 

 

LeetCode 40. Combination Sum II

思路

递归?呵呵

需要判断两个解是否相等,目前没有什么好办法,从boost库里抄了个hash函数过来。

代码

 

最长递增子串 (只能忽略m个元素)

记录一道碰到的笔试题。

题目

给定一个int数组,求其最长的连续递增子序列,但递增过程中可以忽略m个数组元素。在最优子序列长度相同时,以子序列元素之和较小的一个为最优解*。

即实现方法

思路

八成是动态规划,参考最长连续子序列。

需要存储状态:第i个元素的{最优序列,忽略元素个数}

从i向前寻找m个位置的最优解(因为最多只能忽略m个)。假设那个“之前的”元素是array[j],那如果array[i]>array[j]并且array[j]+1>=当前最优序列长度,则判断限制条件*以确定是否更新最优解。

整个方法的复杂度应该是,其中n为array的长度。

代码

 

 

线段树的递归实现 1 of 2: 构造、查询及更新(翻译)

本文翻译自https://leetcode.com/articles/recursive-approach-segment-trees-range-sum-queries-lazy-propagation/,如有侵权请直接Email我

简介

什么是线段树(Segment Tree)

线段树是一种二叉树,树中的每一个节点代表一段区间。通常一个节点储存这个区间的一个或多个属性用于后续查询。

What is a Segment Tree
What is a Segment Tree

为什么要使用线段树(它的特点是什么)?

许多问题需要我们给出数据集在某个区间或者片段内的查询结果。特别是当出现大量、重复的查询时,这类操作会变得冗长或缓慢。一个线段树可以让我们在对数级时间复杂度内得到这类问题的查询结果。

线段树在计算集合学、GIS等领域有相关应用。例如,我们可能会在距离某个中心点/原点附近一段距离的空间范围内有大量的参考点。假设我们需要查询距离原点指定距离范围内的相关参考点。一个普通的查询表需要线性阶的时间来扫描所有的点或所有可能的距离(想一下hash map)。线段树允许我们在对数时间内解决这个问题,并且拥有更少的空间消耗。这类问题被称作 Planar Range Searching。高效解决这类问题是至关重要的,特别是在处理那些快速变换、无法预知的动态数据时(例如,一个空管雷达系统)。

本文稍后会解决区间和查询问题(Range Sum Query Problem)作为一个例子,借此说明线段树是如何节省空间及实时代价。

我们将会使用上图作为一个实例来介绍用于“区间和查询”的线段树它长什么样,以及有何特性。

如何生成一个线段树

我们将数据保存在大小为的数组 arr[] 中。

  1. 线段树树的根通常表示整个数据的区间范围,即 arr[0:n-1] ;
  2. 树的每一个叶节点表示单个元素(或只有一个元素的区间)。因此叶节点表示的数值为 arr[0] , arr[1] 直至 arr[n-1] ;
  3. 树的非叶节点表示其子节点合并(merge/union)后的结果;
  4. 每一个子节点都能表示其父节点一半的区间范围;

一个包含个元素范围的线段树可以用一个大小的数组表示。(其原因在StackOverflow上有详尽的讨论。如果你仍不相信,没关系,我们稍后会进一步讨论。)

怎么(用数组)存呢?

思路很简单:一个索引号为的节点,他的子节点的索引号为以及.

在使用递归方法构建时,线段树非常直观且容易使用。

线段树的递归方法

我们将使用数组 tree[] 来保存线段树(用0值初始化)的节点属性。以下是具体的存储方案(使用以0开始的索引号):

  • 树的根节点索引为0,即 tree[0]
  • 节点 tree[i] 的子节点存储在 tree[2*i+1] 及 tree[2*i+2] 中
  • 当数组元素数量不是2的k次方(如2,4,8,16,32…)时,用  0  或 null 填充不足的元素值
我们真的需要用0填充么?

不完全是。只是需要保证tree[]足够大,并且初始值都是0,而且不需要担心额外的叶节点没有被处理过。

  • 叶节点的索引范围是

我们只需要下列三个方法:

1.根据给定数据构造线段树

该方法自下而上地构造整个 tree 。当满足条件时,我们处理的区间只包含单个元素(即 arr[lo] )。这就是树的叶节点。余下的非叶节点通过合并其子节点的结果构造而成。 treeIndex 是当前正在处理的线段树的索引号。

举个例子,上图中的树可以由下面的输入数据构造出:(本文通篇都会使用这个例子)

你能猜到本例中的 merge 操作是什么吗?在构造完毕后, tree[] 数组看起来是这样的:

注意到 tree[] 数组末尾的那些0了么?这些就是我们用来填充树,使之成为完全树的 null 值(因为我们只有10个叶节点。假若我们有16个叶节点,我们就不需要用 null 填充了。你能证明为什么吗?)

注意:对于不同的问题, merge 操作是不同的。在构造线段树之前,你需要仔细考虑到底在线段树的节点中需要存什么数据,以便在合并的时候能够给出最终的结果。

2. 读取/查询数据区间或片段

在查询的范围完全匹配当前节点的范围时,该方法返回一个结果。否则,它将深入树的下一层来寻找满足(部分)查询范围的节点。

这就是线段树的美丽所在

在上述例子中,我们试图找到范围内的节点值的和。没有一个区间能直接满足搜索范围。然而,我们发现范围可以由几个小范围来表示。验证一下,我们可以看到索引范围在的节点值,他们的和是。而刚才提到的那些小区间,他们所对应的节点的和是.

3.更新元素的值

这个操作类似于 buildSegTree 。我们根据更新请求来更新对应的叶子节点。随后这些变更向上传递到其父节点。

在这个例子中,位于(输入数据中)索引1,3和6的元素,他们的值对应增加了+3, -1与+2。从图中可以看出这些值是如何向上传递更新,直至根节点的。

复杂度分析

我们来看一下 build 过程。我们会访问线段树的每个叶节点(对应到输入数组 arr[] 中的每个元素)。这就形成了个叶节点。此外我们还有个非叶节点。因此总共会有约个节点。这样说来整个构造树的过程的会在即线性时间内完成。

update 过程在达到目标叶节点的过程中,在递归的每一层都会丢弃一半的范围。这个过程类似于二分搜索,需要对数级的时间。在叶节点更新过后,它的每一个直系父节点也都将被更新,这个过程耗费的时间是树的高度的线性级别。

read/query 过程按照深度优先遍历树,寻找符合搜索条件的节点范围。在最优情况下,我们的范围大于或等于根节点的范围,此时直接能从根节点得到结果。最差情况下,我们搜索一个长度为1的范围(对应于线段树中的一个叶节点),此时我们访问的节点个数等于树的高度;即搜索的时间复杂度和树的高度线性相关。

这就是之前说过的:

一个含有个元素范围的线段树可以用一个大小约为的数组表示

这保证了我们我们生成的线段树是一个完全二叉树,进一步又保证了这棵树高度的上界是输入规模的对数级。

Viola! 不论是 read 还是 update 的查询都只需要对数级的时间,这正是我们想要的。

LeetCode 78. Subsets

思路

换个方法想问题。

有n个数,每个数是否作为输出用0/1状态来表示,比如[1,2,3]全出现就是(1,1,1) => 7,那n个元素的子数组的生成就是以下过程:[0, 2^n)里的每个数i,看这个数i里第[0,n)位是否为1,若为1则表示nums[i]被选中了,否则不选。

比如[1,2,3]的所有子集:

代码