翻译:次梯度以及一阶最优性条件(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的值的过程,即。我们稍后再进一步介绍,但这个逆转次微分运算符的思路是非常重要的。 在继续之前,有必要提一下(并且这并不难理解)下述包含关系对于次微分的和是成立的: 对关注的大部分问题而言,上述关系可以强化为相等的关系, 但注意如果,则上述包含关系意味着,这对于证明是个极小值而言(这正是我们最感兴趣之处)足矣。  

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里面有两个语义细胞。 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,在本文中就是以及 解出来是这么两坨: 参数更新算法
Continue reading Information Cell Mixture Models 语义细胞混合模型

用于Sentence Embedding的DSSM与LSTM:管中窥豹

前置废话:感觉实习这两个月真是顶得上实验室半年,想想对不起我的导师,跟现在相比之前天天像是在打酱油啊。 相关文献 Huang, Po-Sen, et al. “Learning deep structured semantic models for web search using clickthrough data.” Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM, 2013. Palangi, Hamid, et al. “Deep sentence embedding using long short-term memory networks: Analysis and application to information retrieval.” IEEE/ACM Transactions on Audio,
Continue reading 用于Sentence Embedding的DSSM与LSTM:管中窥豹

Crowd-BT算法模型 Part III [在线学习]

转载请注明来自http://boweihe.me/?p=1524 本文内容源自 Chen, X., Bennett, P. N., Collins-Thompson, K., & Horvitz, E. (2013, February). Pairwise ranking aggregation in a crowdsourced setting. InProceedings of the sixth ACM international conference on Web search and data mining (pp. 193-202). ACM. 第二部分还在努力学习,先把第三部分贴上来…有部分理解不全我就假装没看到了(捂脸) 在线学习:这个方法似乎是借鉴了Crowd-BT模型,但是最后参数更新的方法用了另外一套东西,可以独立于Crowd-BT的最优化而计算。

Crowd-BT算法模型 Part I [Bradley-Terry的延伸-模型基础]

转载请注明来自http://boweihe.me/?p=1524 本文内容源自 Chen, X., Bennett, P. N., Collins-Thompson, K., & Horvitz, E. (2013, February). Pairwise ranking aggregation in a crowdsourced setting. InProceedings of the sixth ACM international conference on Web search and data mining (pp. 193-202). ACM. 第一部分是对Crowd-BT中采用的模型的中文翻译及理解,不涉及后面的主动学习算法(因为暂时没看懂,哈哈)。 因为没弄懂Wordpress的公式插件,所以暂时用Word文档的截图了..  

机器学习资源

本文汇编了一些机器学习领域的框架、库以及软件(按编程语言排序)。 C++ 计算机视觉 CCV —基于C语言/提供缓存/核心的机器视觉库,新颖的机器视觉库 OpenCV—它提供C++, C, Python, Java 以及 MATLAB 接口,并支持 Windows, Linux, Android and Mac OS 操作系统。 通用机器学习 MLPack DLib ecogg shark Closure 通用机器学习 Closure Toolbox—Clojure 语言库与工具的分类目录 Go 自然语言处理 go-porterstemmer—一个 Porter 词干提取算法的原生 Go 语言净室实现 paicehusk—Paice/Husk 词干提取算法的 Go 语言实现 snowball—Go 语言版的 Snowball 词干提取器 通用机器学习 Go Learn— Go 语言机器学习库 go-pr —Go 语言机器学习包. bayesian—Go 语言朴素贝叶斯分类库。 go-galib—Go
Continue reading 机器学习资源

UFLDL教程的中文翻译——深层网络4篇

从自我学习到深层网络 From Self-Taught Learning to Deep Networks 深层网络概览 Deep Networks: Overview 栈式自编码算法  Stacked Autoencoders 微调多层自编码算法 Fine-tuning Stacked AEs    摘录其中的一句话,觉得挺有道理(嗯嗯嗯一定要搞得我已经通读所有文章的样子!): 为什么我们要使用深度网络呢?使用深度网络最主要的优势在于,它能以更加紧凑简洁的方式来表达比浅层网络大得多的函数集合。正式点说,我们可以找到一些函数,这些函数可以用 层网络简洁地表达出来(这里的简洁是指隐层单元的数目只需与输入单元数目呈多项式关系)。但是对于一个只有 层的网络而言,除非它使用与输入单元数目呈指数关系的隐层单元数目,否则不能简洁表达这些函数。  

[机器学习相关的一些中文教程]Machine Learning for Graphics, Vision and Multimedia

找到了一个比较好的网站,里面是一些[机器学习相关的教程,重要的是都是中文的,读起来比较快。 Homepage: http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/ Topics Date Topic Tutorial References 03/16 Principal Component Analysis 姜任遠 文宗麟 PCA Max Wellings, Linear Models. Sam Roweis, EM Algorithms for PCA and SPCA, NIPS 1997. Michael Tipping, Christopher Bishop, Probabilistic Principal Component Analysis, Journal of the Royal Statistical Society, Series, 1999. Matthew Turk, Alex Pentland, Eigenfaces for recognition, Journal of Cognitive
Continue reading [机器学习相关的一些中文教程]Machine Learning for Graphics, Vision and Multimedia