Monthly Archives: January 2016

One Dimensional Dynamical System

低维动力系统

Leave a comment

One Dimensional Real and Complex Dynamics需要学习的资料：

复分析基础：本科生课程

(1) Complex Analysis, 3rd Edition, Lars V. Ahlfors

(2) Complex Analysis, Elias M. Stein

进阶复分析：研究生课程

(1) Lectures on Riemann Surfaces (GTM 81), Otto Forster

(2) Lectures on Quasiconformal Mappings, Lars V. Ahlfors

实分析基础：本科生课程

(1) Real Analysis, Rudin

(2) Real Analysis, Elias M. Stein

专业书籍：

实动力系统：

(1) One Dimensional Dynamics, Welington de Melo & Sebastian VanStrien

(2) Mathematical Tools for One-Dimensional Dynamics (Cambridge Studies in Advanced Mathematics), Edson de Faria / Welington de Melo

复动力系统：

(3) Dynamics in One Complex Variable, John Milnor

(4) Complex Dynamics, Lennart Carleson

(5) Complex Dynamics and Renormalization, Curtis T. McMullen

(6) Renormalization and 3-Manifolds Which Fiber over the Circle, Curtis T. McMullen

(7) Iteration of rational functions (GTM 132), Alan F. Beardon

遍历论：

(8) An Introduction to Ergodic Theory (GTM 79), Walters Peter

推荐系统

特征工程简介

1 Comment

（I）特征工程可以解决什么样的问题？

特征工程是一个非常重要的课题，是机器学习中不可缺少的一部分，但是它几乎很少出现于机器学习书本里面的某一章。在机器学习方面的成功很大程度上在于如果使用特征工程。在机器学习中，经常是用一个预测模型（线性回归，逻辑回归，SVD等）和一堆原始数据来得到一些预测的结果，人们需要做的是从这堆原始数据中去提炼较优的结果，然后做到最优的预测。这个就包括两个方面，第一就是如何选择和使用各种模型，第二就是怎么样去使用这些原始的数据才能达到最优的效果。那么怎么样才能够获得最优的结果呢？贴上一句经典的话就是：

Actually the sucess of all Machine Learning algorithms depends on how you present the data.
—— Mohammad Pezeshki

直接翻译过来便是：事实上所有机器学习算法上面的成功都在于你怎么样去展示这些数据。由此可见特征工程在实际的机器学习中的重要性，从数据里面提取出来的特征好坏与否就会直接影响模型的效果。从某些层面上来说，所使用的特征越好，得到的效果就会越好。所需要的特征就是可以借此来描述已知数据的内在关系。总结一下就是：

Better feature means flexibility. Better feature means simpler models. Better feature means better results.

有的时候，可以使用一些不是最优的模型来训练数据，如果特征选择得好的话，依然可以得到一个不错的结果。很多机器学习的模型都能够从数据中选择出不错的结构，从而进行良好的预测。一个优秀的特征具有极强的灵活性，可以使用不那么复杂的，运算速度快，容易理解和维护的模型来得到不错的结果。

（II）什么才是特征工程？

Feature Engineering is the process of transforming raw data into features that better represent the underlying problem to the predictive models, resulting in improved model accuracy on unseen data.
—— Jason Brownlee

Feature Engineering is manually designing what the input x’s should be.
—— Tomasz Malisiewicz

从这个概念可以看出，特征工程其实是一个如何展示和表现数据的问题，在实际工作中需要把数据以一种“良好”的方式展示出来，使得能够使用各种各样的机器学习模型来得到更好的效果。如何从原始数据中去除不佳的数据，展示合适的数据就成为了特征工程的关键问题。

（III）特征有用性的预估

每次构造了一个特征，都需要从各个方面去证明该特征的有效性。一个特征是否重要主要在于该特征与要预测的东西是否是高度相关的，如果是高度相关，那么该特征就是十分重要的。比如常用的工具就是统计学里面的相关系数。

（IV）特征的构造过程

在实际工作中首先肯定要确定具体的问题，然后就是数据的选择和准备过程，再就是模型的准备和计算工作，最后才是展示数据的预测结果。构造特征的一般步骤：

［1］任务的确定：

根据具体的业务确定需要解决的问题。

［2］数据的选择：

整合数据，收集数据。这个时候需要对这些数据的可用性进行评估，可以分成几个方面来考虑。获取这批数据的难易程度，比方说有的数据非常隐私，这批数据获得的难度就很大。其次就是这批数据的覆盖率。比方说要构造某个年龄的特征，那么这些用户中具有年龄特征的比例是多少就是一个关键的指标。如果覆盖率低，那么最后做出的特征可以影响的用户数量就会有限制。如果覆盖率高，那么年龄特征做得好，对最后的模型训练结果都会有一个明显的提升。再就是这批数据的准确率，因为从网上或者其他地方获取的数据，会由于各种各样的因素（用户的因素，数据上报的因素）导致数据不能够完整的反映真实的情况。这个时候就需要事先对这批数据的准确性作出评估。

［3］预处理数据：

设计数据展现的格式，清洗数据，选择合适的样本使得机器学习模型能够使用它。比方说一些年龄特征是空值或者负数或者大于200等，或者说某个页面的播放数据大于曝光数据，这些就是数据的不合理，需要在使用之前把这一批数据排除掉。这个时候清洗异常样本就显得至关重要。

［4］特征的构造：

转化数据，使之成为有效的特征。常用的方法是标准化，归一化，特征的离散化等。
（4.1）标准化（Standardization）：
比方说有一些数字的单位是千克，有一些数字的单位是克，这个时候需要统一单位。如果没有标准化，两个变量混在一起搞，那么肯定就会不合适。
（4.2）归一化（Normalization）：
归一化是因为在特征会在不同的尺度下有不同的表现形式，归一化会使得各个特征能够同时以恰当的方式表现。比方说某个专辑的点击播放率一般不会超过0.2，但是专辑的播放次数可能会达到几千次，所以说为了能够在模型里面得到更合适结果，需要先把一些特征在尺度上进行归一化，然后进行模型训练。进行比例缩放或者归一化的时候，通常采取的方案有线性（linearization）最大最小归一化，对数（logarithm）归一化，或者 z-score 的归一化。其中 z-score 的归一化指的是 (x-\mu)/\sigma，这里 \mu 是这个特征的均值，\sigma 是这个特征的方差。这里的归一化的关键之处在于数据的变化（Data Transforming）。对于处理一些大尺度数据（比方说某个视频被所有用户观看的次数之类的），一般会使用对数来处理数据，或者双曲线函数。例如：
f(x)=\log(1+x):[0,+\infty)\rightarrow [0,+\infty),
或者
f(x)=x/(x+1):[0,+\infty)\rightarrow [0,1).
（4.3）特征的离散化（Discretization）：
离散化是指把特征进行必要的离散处理，比方说年龄特征是一个连续的特征，但是把年龄层分成5－18岁（中小学生），19－23岁（大学生），24－29岁（工作前几年），30－40岁（成家立业），40－60岁（中年人）从某些层面来说比连续的年龄数据（比如说某人年龄是20岁1月3日之类的）更容易理解不同年龄层人的特性。这里可以根据特征的分布图像做出不同的分割，比方说通过等频率分割（Equal-Frequency）得到的特征比等区间分割（Equal-Interval）得到的特征具有更好的区分性。典型的离散化步骤：对特征做排序－> 选择合适的分割点－> 作出对整体的分割 －> 查看分割是否合理，是否能够达到停止条件。
（4.4）特征的二值化（Binarization）：
二值化指的是把某个特征映射成 0 或者 1 两个值，比方说判断某个用户是否收听某个节目，用 1 表示该用户收听这个节目，否则用 0 表示该用户没有收听这个节目。
（4.5）特征的交叉：
比方说，某个男性用户在一级分类新闻资讯的取值是1，那么他在这个新闻咨询下的所有专辑和节目的取值都是1。对娱乐新闻的取值也是1，对八卦头条的取值也是1，对NBA战况直播的取值还是1。也就是说（男性，娱乐新闻），（男性，八卦头条），（男性，NBA战况直播）这三个分类的取值都是1。这样看起来就不符合常理，照理说男性用户对NBA的兴趣应该是远大于娱乐新闻的。比较合理的做法是男性在某个专辑的取值是所有男性在这个专辑的点击率，也就是说（男性，娱乐新闻）的取值是男性对娱乐新闻的点击率，（男性，NBA战况直播）的取值是男性对NBA战况的点击率。此时的值不再是 0 或者 1，而是 [0,1] 之间的某个实数，可以对这个实数进行加减乘除等运算操作。除了性别和点击率的交叉特征，还可以进行年龄，地域，收入等特征和点击率的交叉。

  [5] 选择特征的常用方法：

（5.1）过滤（Filter）：

过滤这种方法是选定一个指标来评估这个特征的可行性，根据指标值来对已经构造的特征进行排序工作，去掉无法达到要求的特征。这个时候，选择一个合适的指标来判断特征是否有效就是关键所在。从统计学的角度来看，相关系数（Correlation Coefficient）是一个评价两个随机变量 X 和 Y 是否线性相关的一个重要指标。

\rho_{XY}=cov(X,Y)/(\sigma_{X}\sigma_{Y})\in [-1,1]

就是相关系数的计算方法。如果 \rho_{XY}<0，那么说明两个变量是线性反相关的；如果 \rho_{XY}>0，那么说明两个变量是线性相关的。不过需要主要的是，即使 \rho_{XY}=0，也只是说明两个变量是线性无关的，并不能推出它们之间是独立的。此时知道的就是一个线性分类器并不能把这个特征的正负样本分开，需要把该特征和其他特征交叉或者做其余的特征运算，形成一个或者多个新的特征，让这些新的特征发挥新的价值，做好进一步的分类工作。

（5.2）包装（Wrapper）：

包装这种方法和前面的过滤方法不一样。包装方法需要首先选定一种评估模型效果的方法，比方说 AUC（Area Under the Curve），MAE（Mean Absolute Error），Mean Squared Error（MSE）等。此时有两个不同的方案，分别是前向特征选择（Forward Feature Selection）和后向特征选择（Backward Feature Selection）。前向特征选择是从空集（Empty Set）开始，使用一种贪心算法，每次在现有特征的基础上逐渐添加一个使得模型效果更好的特征。反之，后向特征选择是从（Full Set）开始，每次去掉一个让模型效果提升最多的特征。或者可以使用增 L 去 R 算法（Plus-L Minus-R Selection），也就是说从空集开始，每次增加 L 个，同时减去 R 个，选择最优的特征，其中 L>R。或者从全集开始，每次减去 R 个，同时增加 L 个，选择最优的特征，其中 L<R。

（5.3）嵌入（Embedding）：

嵌入特征选择方法和算法本身紧密结合，在模型训练的过程中完成特征的选择。例如：决策树（Decision Tree）算法每次都是优先选择分类能力最强的特征；逻辑回归（Logistic Regression）算法加上 L1 和 L2 等惩罚项之后，也会使得某些信号比较弱的特征权重很小甚至为 0。至于 Logistic Regression 的一些算法，可以参考 TG（Truncated Gradient Algorithm），FOBOS（Forward and Backward Splitting），RDA（Regularized Dual Averaging Algorithm）， FTRL（Follow-the-Regularized-Leader Algorithm） 算法，参考文献：Ad Click Prediction: a View from the Trenches。

［6］模型的使用：

创造模型，选择合适的模型（LR，SVM，SVD等），用合适的模型来进行预测，用各种统计指标来判断该特征是否合适。

［7］上线的效果：

通过在线测试来看效果。数据的转换（Transforming Data）就是把数据从原始的数据状态转换成适合模型计算的状态，从某些层面上来说，“数据转换“和”特征构造“的过程几乎是一致的。

（V）特征工程的迭代过程

特征工程的迭代步骤：

［1］选择特征：

需要进行头脑风暴（brainstorm）。通过分析具体的问题，查看大量的数据，从数据中观察出数据的关键之处；

［2］设计特征：

这个需要具体问题具体分析，可以自动进行特征提取工作，也可以进行手工进行特征的构造工作，甚至混合两种方法；

［3］判断特征：

使用不同的特征构造方法，来从多个层面来判断这个特征的选择是否合适；

［4］计算模型：

通过模型计算得到模型在该特征上所提升的准确率。

［5］上线测试：

通过在线测试的效果来判断特征是否有效。监控重要特征，防止特征的质量下滑，影响模型的效果。

Complex Analysis

Complex Analysis

Leave a comment

学习复分析也已经很多年了，七七八八的也读了不少的书籍和论文。略作总结工作，方便后来人学习参考。 复分析是一门历史悠久的学科，主要是研究解析函数，亚纯函数在复球面的性质。下面一一介绍这些基本内容。

300px-Mandel_zoom_00_mandelbrot_set

（1）提到复变函数，首先需要了解复数 (Complex Numbers) 的基本性质和四则运算规则。怎么样计算复数的平方根，极坐标与xy坐标的转换，复数的模之类的。这些在高中的时候基本上都会学过。

（2）复变函数自然是在复平面上来研究问题，此时数学分析里面的求导数之类的运算就会很自然的引入到复平面里面，从而引出解析函数 (Holomorphic Functions / Analytic Functions) 的定义。那么研究解析函数的性质就是关键所在。最关键的地方就是所谓的Cauchy—Riemann公式，这个是判断一个函数是否是解析函数的关键所在。

（3）明白解析函数的定义以及性质之后，就会把数学分析里面的曲线积分 (Line Integrals) 的概念引入复分析中，定义几乎是一致的。在引入了闭曲线和曲线积分之后，就会有出现复分析中的重要的定理：Cauchy积分公式 (Cauchy’s Integral Formula)。这个是复分析的第一个重要定理。

（4）既然是解析函数，那么函数的定义域 (Domain) 就是一个关键的问题。可以从整个定义域去考虑这个函数，也可以从局部来研究这个函数。这个时候研究解析函数的奇点 (Singularity) 就是关键所在，奇点根据性质分成可去奇点 (Removable Singularity)，极点 (Pole)，本性奇点 (Essential Singularity) 三类，围绕这三类奇点，会有各自奇妙的定理。

（5）复变函数中，留数定理 (Residue Theorem) 是一个重要的定理，反映了曲线积分和零点极点的性质。与之类似的幅角定理也展示了类似的关系。

（6）除了积分，导数也是解析函数的一个研究方向。导数加上收敛 (Convergence) 的概念就可以引出 Taylor 级数 (Taylor Series) 和 Laurent 级数 (Laurent Series) 的概念。除此之外，正规族 (Normal Families) 里面有一个非常重要的定理，那就是Arzela定理。

（7）以上都是从分析的角度来研究复分析，如果从几何的角度来说，最重要的定理莫过于 Riemann 映照定理 (Riemann Mapping Theorem)。这个时候一般会介绍线性变换，就是 Mobius 变换 (Mobius Transforms)，把各种各样的单连通区域映射成单位圆。研究 Mobius 变换的保角和交比之类的性质。

（8）椭圆函数 (Elliptic Functions)，经典的双周期函数 (Double Periodic Functions)。这里有 Weierstrass 理论，是研究 Weierstrass 函数的，有经典的微分方程，以及该函数的性质。 以上就是复分析或者复变函数的一些课程介绍，如果有遗漏或者疏忽的地方请大家指教。

推荐书籍：

（1）Complex Analysis，3rd Edition，Lars V.Ahlfors

ahlfors.jpg

（2）Complex Analysis，Elias M. Stein

stein.jpg

Classical and Modern Fourier Analysis

调和分析

Leave a comment

之前在北京大学学了整整一个学期的调和分析，是由BICMR的苗老师主讲。在这门课上我受益匪浅，故写一篇文章来感激下这位老师，同时写一下自己学习调和分析的感受。

调和分析起源于 Fourier 这位数学家的研究，故也可以称为 Fourier 分析。其主要内容包括算子插值方法，Hardy-Littlewood 极大算子，Fourier变换，Calderon-Zygmund’s Inequality, 函数空间，Ap 权等等。下面一一介绍这些基本内容。

(1) 算子插值方法

里面主要有 Marcinkiewicz Interpolation Theorem 和 Riesz Thorin Interpolation Theorem两个定理，分别是用实变方法和复变方法证明的。这两个定理则是研究算子的 L^p 有界性的关键定理，是整个调和分析的基础。

(2) Hardy—Littlewood Maximal Operator

这个是一个相当重要的拟线性算子，利用 Vitali Covering Theorem 和 Marcinkiewicz Interpolation Theorem 可以证明该算子是 L^p 有界的。证明过程不超过10行，但是证明过程相当的漂亮。

(3) Fourier Transformation

调和分析的主要工具，这个工具不仅仅在调和分析上有用，在 PDE 和随机过程中，这也是一个相当重要的工具。它把一个物理空间上的函数，转换成频率空间上的函数，从而获得了很多很好的性质。

(4) Calderon-Zygmund’s Inequality

这个定理是调和分析的经典定理之一，是处理卷积型的奇异积分的。可以看成是 Minkowskii 不等式的推广。Zygmund 把定理的条件放的很弱，只需要加上 Hormander 条件就可以得到算子的 L^p 有界性。然后也可以考虑其条件的充要条件。

(5) 函数空间

调和分析里面提到的函数空间包括 Sobolev space, Lipschitz space, Hardy space, Besov space 等等。 其中 Sobolev space 在 PDE 上面用处广泛，其代表作就是 Adams 的 Sobolev Space. Besov Space 里面有一个插值定理，也相当的重要，差不多5页吧，当时苗老师让我们全部背下来，嘿嘿。另外， Hardy Space里面有一个相当重要的定理，就是所谓的 Duality of BMO and H^1 Space. 其证明过程大概有10页吧，是由 C.Fefferman 和 Elias.M.Stein 在上个世纪70年代给出的，方法太经典了，看完之后甚至会觉得自己没有必要学数学了。

(6) Ap weight

这个也是调和分析的分支之一，其中周民强老先生的书上有详细记载，就不一一阐述了。

以上的这些内容就是之前一个学期在北大学习所学到的东西，学了调和分析之后，基本上就不怕所谓的硬分析了。总之收获还是蛮多的，非常欣赏那位老师，一个学期讲了那么多东西。其实以上我提到的只是他讲的东西的一半内容，他后面还讲了很多 Schrodinger 方程的内容，由于本人实力有限，实在是没有能力再学后面的内容了。

ps：这是2009年的事情了，一晃眼7年过去了。

参考文献：
Loukas Grafakos GTM249 Classical Fourier Analysis
Loukas Grafakos GTM250 Modern Fourier Analysis
(上面这两本书是调和分析的经典之作，几乎涵盖了实变方法的所有内容。不过有点厚，差不多1100页。)

Computer Science, 推荐系统

转行数据挖掘和机器学习

4 Comments

半年前从数学专业转行到了互联网行业做数据挖掘和推荐系统，在做具体的业务的时候遇到了一些知识点，于是自己整理出来。如果有后来人需要转行的话，可以用这份资料来参考一下。大牛请忽视以下的内容，小白可以参考下。

从数学专业转行到工业界做数据挖掘需要的知识储备：

1. Hadoop，HIVE，SQL数据库操作。

Hive用于提取数据，做基本的数据分析。hive的基本函数，比如聚合函数，数学函数，字符串的函数，连接表格函数等。hive的各种语句，比如if else，case等语句。

EXCEL的基本操作需要掌握，可以进行各种数据的处理、统计分析和辅助决策操作，用熟悉了其实挺方便的。

2.编程语言

编程语言最好会python，c/c++，或者java，至少一种。做机器学习的话感觉用python会多一些。

3.操作系统

Linux系统，脚本语言Shell。

4. 数据挖掘和机器学习的基础知识和算法

逻辑回归算法 Logistic Regression（LR），

支持向量机算法 Support Vector Machine（SVM），

物质扩散和热传导算法（Heat Spreading），

Gradient Boosting Decision Tree（GBDT），

聚类算法，神经网络算法，决策树，随机森林，异常值检测等常用算法需要掌握。

特征工程的基础知识：根据相应的产品进行必要的特征构造，物品特征，交叉特征等。

其中LR使用广泛：由于LR是使用线性方法来处理非线性的问题，导致特征工程十分复杂，交叉项多（二维或者三维的交叉）。

工程上的最优化论文推荐：
Ad Click Prediction a View from the Trenches
需要了解的是相关论文的背景SGD算法，Truncated Gradient算法，RDA算法，FOBOS算法，FTRL算法等。

5. 统计学：

时间序列模型，变量的相关系数，ROC曲线和AUC，交叉验证，主成分分析。

6. 大数据，推荐系统，计算广告学的科普书籍

推荐系统

Truncated Gradient (TG) 算法简介

1 Comment

现在做在线学习和 CTR 常常会用到逻辑回归（ Logistic Regression），而传统的批量（batch）算法无法有效地处理超大规模的数据集和在线数据流，美国的 Google 公司先后三年时间（2010年-2013年）从理论研究到实际工程化实现的 FTRL（Follow-the-regularized-Leader）算法，在处理诸如逻辑回归之类的带非光滑正则化项（例如 L1 范数，做模型复杂度控制和稀疏化）的凸优化问题上性能非常出色。

通常，优化算法中的 gradient descent 等解法，是对一批样本进行一次求解，得到一个全局最优解。但是，实际的互联网广告应用需要的是快速地进行模型的更新。为了保证快速的更新，训练样本是一条一条地过来的，每来一个样本，模型的参数对这个样本进行一次迭代，从而保证了模型的及时更新，这种方法叫做在线梯度下降法（Online gradient descent）。

在应用的时候，线上来的每一个广告请求，都提取出相应的特征，再根据模型的参数，计算一个点击某广告的概率。在线学习的任务就是学习模型的参数。所谓的模型的参数，其实可以认为是一个目标函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是，解这个问题只能扫描一次样本，而且样本是一条一条地过来的。

当然这会有误差，所以为了避免这种误差，又为了增加稀疏性，有人又想到了多个版本的算法，Google 公司有人总结了其中几种比较优秀的，例如 FOBOS，AOGD 和微软的 RDA，同时提出了Google自己的算法 FTRL-Proximal。其中，FTRL-Proximal 在稀疏性和精确度等方面表现都比较好。

问题描述（最小化目标函数）

等价条件：

（1）约束优化（convex constraint formulation）：

\hat{w}=argmin_{w}\sum_{i=1}^{n}L(w,z_{i}) subject to ||w||_{1}\leq s

（2）无约束优化描述（soft regularization formulation）：

\hat{w}=argmin_{w}\sum_{i=1}^{n}L(w,z_{i})+\lambda ||w||_{1}

注：当选择合适的常数 \lambda 时，这两种描述是等价的。

损失函数：

Linear Regression：

h(W,X_{j})=W^{T}X_{j}, \ell(W,Z)=\sum_{j=1}^{M}(y_{j}-W^{T}X_{j})^{2}

Logistic Regression：

h(W,X_{j})=1/(1+\exp(-W^{T}X_{j})), \ell(W,Z)=\sum_{j=1}^{M}\log(1+\exp(-y_{j}W^{T}X_{j}))

传统算法（Gradient Descent）

Batch Gradient Descent: Repeat Until Convergence

{ W^{(t+1)}=W^{(t)}-\eta^{(t)}\nabla\ell_{W}(W^{(t)},Z) }

这里的 Gradient Descent 是一种批量处理的方式（Batch），每次更新 W 的时候都需要扫描所有样本来计算一个全局梯度 \nabla\ell_{W}\ell(W^{(t)},Z).

传统算法（Stochastic Gradient Descent）

Stochastic Gradient Descent 是另外一种权重更新方法：

Loop{

for j=1 to M { W^{(t+1)}=W^{(t)}-\eta^{(t)}\nabla\ell_{W}(W^{(t)},Z_{j}) }

}

这里每次迭代仅仅根据单个样本更新权重 W，这种算法称为随机梯度下降法（Stochastic Gradient Descent）。

Truncated Gradient 算法简介

为了得到稀疏的特征权重 W，最简单粗暴的方式就是设定一个阈值，当 W 的某维度上系数小于这个阈值时将其设置为 0（称作简单截断）。这种方法实现起来很简单，也容易理解。但实际中（尤其在OGD里面）W 的某个系数比较小可能是因为该维度训练不足引起的，简单进行截断会造成这部分特征的丢失。

截断梯度法（TG, Truncated Gradient）是由John Langford，Lihong Li 和 Tong Zhang 在2009年提出，实际上是对简单截断的一种改进。下面首先描述一下 L1 正则化和简单截断的方法，然后我们再来看TG对简单截断的改进以及这三种方法在特定条件下的转化。

（1）L1 正则化法

由于 L1 正则项在 0 处不可导，往往会造成平滑的凸优化问题变成非平滑凸优化问题，因此在每次迭代中采用次梯度计算 L1 正则项的梯度。权重更新方式为：

W_{(t+1)}=W_{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t)}\lambda sgn(W^{t})

注意，这里 \lambda \in \mathbb{R} 是一个标量，且 \lambda\geq 0，为 L1 正则化参数。sgn(v) 是符号函数，如果 V=(v_{1},...,v_{N})\in \mathbb{R}^{N} 是一个向量，那么 sgn(V)=(sgn(v_{1}),...,sgn(v_{N}))\in\mathbb{R}^{N}。\eta^{(t)}是学习率，通常假设为 t^{-0.5} 的函数。G^{(t)}=\nabla \ell(W^{(t)},Z^{(t)}) 代表了第 t 次迭代中损失函数的梯度，由于 OGD 每次仅根据观测到的一个样本进行权重更新，因此也不再使用区分样本的下标 j。

（2）简单截断法

以 k 为窗口，当 t/k 不为整数时采用标准的SGD进行迭代，当 t/k 为整数时，采用如下权重更新方式：这里的 T_{0}(v_{i},\theta) 是分段函数，

W^{(t+1)}=T_{0}(W^{(t)}-\eta^{(t)}G^{(t)},\theta)

T_{0}(v_{i},\theta)=0 \text{ if } |v_{i}|\leq \theta,

T_{0}(v_{i},\theta)=v_{i} \text{ otherwise}.

这里 \theta\in \mathbb{R} 并且 \theta\geq 0。如果 V=(v_{1},...,v_{N})\in \mathbb{R}^{N} 是一个向量，那么 T_{0}(V,\theta)=(T_{0}(v_{1},\theta),...,T_{0}(v_{N},\theta))\in \mathbb{R}^{N}。

（3）截断梯度法（Truncated Gradient）

上面的简单截断法看上去十分 aggressive，因此截断梯度法在此基础上进行了改进工作。

W^{(t+1)}=T_{1}(W^{(t)}-\eta^{(t)}G^{(t)},\eta^{(t)}\lambda^{(t)},\theta)

 这里的方程 T_{1} 定义为：

T_{1}(v_{i},\alpha,\theta)=\max(0,v_{i}-\alpha) \text{ if } v_{i}\in [0,\theta]

T_{1}(v_{i},\alpha,\theta)=\min(0,v_{i}+\alpha) \text{ else if } v_{i}\in [-\theta,0)

T_{1}(v_{i},\alpha,\theta)=v_{i} \text{ otherwise }

其中 \lambda^{(t)}\in \mathbb{R}，并且 \lambda^{(t)}\geq 0。Truncated Gradient 方法同样是以 k 作为窗口，每进行 k 步就进行一次截断操作。当 t/k 不是整数时，\lambda^{(t)}=0，当 t/k 是整数时，\lambda^{(t)}=k\lambda。从上面的公式可以看出，\lambda, \theta 决定了 W 的稀疏程度，如果 \lambda 和 \theta都很大，那么稀疏性就会越强。特别的，当 \lambda=\theta 时，此时只需要控制一个参数就可以控制稀疏性。

Truncated Gradient 的算法：

输入 \theta，初始化 W\in\mathbb{R}^{N}
for t = 1,2,3,... 计算 G=\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
按照下面规则更新 W,

    （i）当 t/k 不是整数时，采用标准的 SGD (Stochastic Gradient Descent) 进行迭代。\lambda^{(t)}=0，并且 w_{i}^{(t)}=w_{i}^{(t)}-\eta^{(t)}g_{i} for all i \in \mathbb{R}^{N}.

    （ii）当 t/k 是整数时，采取截断技术。

     w_{i} = \max(0,w_{i}-\eta^{(t)}g_{i}-\eta^{(t)}\lambda^{(t)}), if (w_{i}-\eta^{(t)}g_{i})\in[0,\theta]

     w_{i} = \min(0,w_{i}-\eta^{(t)}g_{i}+\eta^{(t)}\lambda^{(t)}), else if (w_{i}-\eta^{(t)}g_{i})\in[-\theta,0]

     w_{i}=w_{i}-\eta^{(t)}g_{i}, otherwise
return W.

（4）Truncated Gradient，简单截断法，L1 正则化之间的关系。

简单截断法和截断梯度法的区别在于选择了不同的截断公式 T_{0} 和 T_{1}。如下图所示：

T0 and T1

Truncated Gradient -> 简单截断法

从上图可以直接看出：选择 \alpha=\theta，截断梯度法就可以变成简单截断法。从公式上也可以通过计算直接得出。

Truncated Gradient -> L1 正则化

貌似有一点问题，需要重新推导。

推荐系统

Forward-Backward Splitting (FOBOS) 算法简介

Leave a comment

 

FOBOS 算法简介

（1）FOBOS（Forward Backward Splitting）算法原理

前向后向切分（FOBOS，Forward Backward Splitting）是 John Duchi 和 Yoran Singer 提出的。在该算法中，权重的更新分成两个步骤：

W^{(t+0.5)}=W^{(t)}-\eta^{(t)}G^{(t)}

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

第一个步骤实际上是一个标准的梯度下降（SGD），第二个步骤是对第一个步骤的结果进行局部调整。写成一个公式那就是：

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

假设 F(W)=\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)，如果 W^{(t+1)} 存在一个最优解，那么可以推断 0 向量一定属于 F(W) 的次梯度集合：

0 \in \partial F(W)=W-W^{(t)}+\eta^{(t)}G^{(t)}+\eta^{(t+0.5)}\partial\Psi(W).

因为 W^{(t+1)}=argmin_{W}F(W), 那么可以得到权重更新的另外一种形式：

W^{(t+1)}=W^{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t+0.5)}\partial\Psi(W^{(t+1)})

从上面的公式可以看出，更新后的 W^{(t+1)} 不仅和 W^{(t)} 有关，还和自己 \Psi(W^{(t+1)}) 有关。这也许就是”前向后向切分”这个名称的由来。

（2）FOBOS（Forward Backward Splitting）的 L1 正则化

假设 \Psi(W) 是 L1 范数，中间向量是 W^{(t+0.5)}=(v_{1},...,v_{N})\in\mathbb{R}^{N}, 并且参数 \tilde{\lambda}=\eta^{(t+0.5)}\lambda，那么公式就可以展开得到

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}

=argmin_{W}\sum_{i=1}^{N}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|).

所以，可以对特征权重 W 的每一个维度进行单独求解：

w^{(t+1)}_{i}=argmin_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|) for all $latex 1\leq i \leq N$.

Claim. 如果 w_{i}^{*} 是 \min_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|) 的最优解，那么 w_{i}^{*}v_{i}\geq 0.

证明：反证法，如果 w_{i}^{*}v_{i}<0，那么 \frac{1}{2}v_{i}^{2}<\frac{1}{2}(w_{i}^{*}-v_{i})^{2}+\tilde{\lambda}|w_{i}^{*}|， 这与条件矛盾。

通过数学计算可以证明：在 L1 正则化下，FOBOS 的特征权重的各个维度的更新公式是：

w_{i}^{(t+1)}=sgn(v_{i})\max(0,|v_{i}|-\tilde{\lambda})

= sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\} for all 1\leq i \leq N,

其中 g_{i}^{(t)} 是梯度 G^{(t)} 在第 i 个维度的分量。

从公式上看，

如果 |w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\leq\eta^{(t+0.5)}\lambda， 则有 w_{i}^{(t+1)}=0. 意思就是如果这次训练产生梯度的变化不足以令权重值发生足够大的变化时，就认为在这次训练中该维度不够重要，应该强制其权重是0.

如果 |w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\geq\eta^{(t+0.5)}\lambda，那么则有

w_{i}^{(t+1)}=(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})-\eta^{(t+0.5)}\lambda \cdot sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})

L1-FOBOS 的算法：

（1）输入 \lambda，初始化 W\in\mathbb{R}^{N}
（2）for t=1,2,3..., 计算 G=\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
     按照公式更新 W，w_{i} = sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\} 
     for all 1\leq i \leq N
（3）Return W

（3）L1-FOBOS 与 Truncated Gradient 的关系

令 \theta=+\infty, k=1, \lambda_{TG}^{(t)}=\eta^{(t+0.5)}\lambda，可以得到 L1-FOBOS 与 Truncated Gradient 完全一致，换句话说 L1-FOBOS 是 Truncated Gradient 在一些特定条件下的形式。

 

推荐系统

Regularized Dual Averaging Algorithm (RDA)

Leave a comment

Regularized Dual Averaging Algorithm 算法介绍

（一）RDA（Regularized Dual Averaging Algorithm）算法原理

RDA（Regularized Dual Averaging Algorithm）叫做正则对偶平均算法，特征权重的更新策略是：

W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \Psi(W) +\frac{\beta^{(t)}}{t}h(W)\}

其中 G^{(t)}\cdot W 指的是向量 G^{(t)} 和 W 的内积，\Psi(W) 是正则项，h(W) 是一个严格凸函数，\{\beta^{(t)}|t\geq 1\} 是一个非负递增序列。

从公式中可以看出：

  1. \frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W 包括了之前所有梯度的平均值。
  2. 具有正则项 \Psi(W)。
  3. 额外项 \frac{\beta^{(t)}}{t}h(W)。

 （二）RDA 的 L1 正则化

假设 \Psi(W)=||W||_{1}；h(W)=\frac{1}{2}||W||_{2}^{2}，i.e. h(W) 是一个严格凸函数；\beta^{(t)}=\gamma\sqrt{t} \text{ with } \gamma>0 是一个非负递增序列。那么 RDA 算法就可以写成：

W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \lambda||W||_{1}+\frac{\gamma}{2\sqrt{t}}||W||_{2}^{2}\}

此时可以采取同样的策略，把各个维度拆分成 N 个独立的问题来处理。也就是：

w_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}

其中，\lambda>0, \gamma>0,  \overline{g}_{i}^{(t)}=\frac{1}{t}\sum_{r=1}^{t}g_{i}^{(r)}.

通过数学推导可以证明：

w_{i}^{(t+1)}=0, if |\overline{g}_{i}^{(t)}|<\lambda

w_{i}^{(t+1)}=-\frac{\sqrt{t}}{\gamma}(\overline{g}_{i}^{(t)}-\lambda\cdot sgn(\overline{g}_{i}^{(t)})), otherwise

意思就是：当某个维度的累加平均值 |\overline{g}_{i}^{(t)}| 小于 \lambda 时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA 的算法

（1）输入 \gamma, \lambda，初始化 W\in \mathbb{R}^{N}, G=0\in\mathbb{R}^{N}
（2）for t=1,2,3... 
         G=\frac{t-1}{t}G+\frac{1}{t}\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
         更新 W：
         w_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}
     end
     return W

（三）L1-RDA 与 L1-FOBOS 的对比

从截断方式来看，在 RDA 的算法中，只要梯度的累加平均值小于参数 \lambda，就直接进行截断，说明 RDA 更容易产生稀疏性；同时，RDA 中截断的条件是考虑梯度的累加平均值，可以避免因为某些维度训练不足而导致截断的问题，这一点与 TG，FOBOS 不一样。通过调节参数 \lambda 可以在精度和稀疏性上进行权衡。

（四）L1-RDA 与 L1-FOBOS 形式上的统一

在 L1-FOBOS 中，假设 \eta^{(t+0.5)}=\eta^{(t)}=\Theta(t^{-0.5})，可以得到：

W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t)}\lambda||W||_{1}\}

通过计算可以把 L1-FOBOS 写成：

W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-W^{(t)}||_{2}^{2}

同时 L1-RDA 可以写成：

W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-0||_{2}^{2} \}

其中 G^{(1:t)}=\sum_{s=1}^{t}G^{(s)}。如果令 \sigma^{(s)}=\frac{1}{\eta^{(s)}}-\frac{1}{\eta^{(s-1)}}, \sigma^{(1:t)}=\frac{1}{\eta^{(t)}}, \sigma^{(1:t)}=\sum_{s=1}^{t}\sigma^{(s)}, 上面的公式可以写成：

L1-FOBOS：

W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-W^{(t)}||_{2}^{2}\}

L1-RDA ：

W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-0||_{2}^{2} \}

可以看出：

  1. L1-FOBOS 考虑了梯度和当前模的 L1 正则项，L1-RDA 考虑的是累积梯度。
  2. L1-FOBOS 的第三项限制 W 不能够距离已经迭代过的 W^{(t)} 值太远，L1-RDA 的第三项限制的是 W 不能够距离 0 太远。