Category Archives: 推荐系统

DeepMind Could Bring The Best News Recommendation Engine

February 15, 2017 zr9558 Leave a comment

Reinforcement Learning, a key Google DeepMind algorithm, could overhaul news recommendation engines and greatly improve users stickiness. After beating a Go Grand Master, the algorithm could become the engine of choice for true personalization.

My interest for DeepMind goes back to its acquisition by Google, in January 2014, for about half a billion dollars. Later in California, I had conversations with Artificial Intelligence and deep learning experts; they said Google had in fact captured about half of the world’s best A.I. minds, snatching several years of Stanford A.I. classes, and paying top dollar for talent. Acquiring London startup Deep Mind was a key move in a strategy aimed at cornering the A.I. field. My interlocutors at Google and Stanford told me it could lead to major new iterations of the company, with A.I. percolating in every branch of Google (now Alphabet), from improving search to better YouTube recommendations, to more advanced projects such as predictive health care or automated transportation.

Demis Hassabis, DeepMind’s founder and CEO, a great communicator, gives captivating lectures, this Oxford University one among the best, delivered on February 24th. The 40-year old PhD in Cognitive Neuroscience, and Computer Science graduate from MIT and Harvard, offers this explanation of his work:

“The core of what we do focuses around what we call Reinforcement Learning. And that’s how we think about intelligence at DeepMind.

[Hassabis then shows the following diagram]

We start with the agent system, the A.I. That agent finds itself in some kind of environment, trying to achieve a goal. In a real-world environment, the agent could be a robot or, in a virtual environment, an avatar.

The agent interacts with the environment in two ways. Firstly against observations through its sensory operators. We currently use vision but we start to think about other modalities.

One of the jobs of the agent system is to build the best possible model of the environment out there, just based on these incomplete and noisy observations that [the agent] is receiving in real time. And it keeps updating its model in the face of new evidences.

Once it built this model, the second job of the agent is to make predictions of what is going to happen next. If you can make predictions, you can start planning about what to do. So if you try to achieve a goal, the agent will have a set of actions available. The decision making problem is to pick which action would be the best to take toward your goal.

Once the agent has decided that based on its model, and its planned trajectories, it executes actions that may or may not make some changes in the environment, and that drives the observations…”

Reinforcement Learning is a highly complex process. First, the observed environment is very noisy, incomplete and largely consists of unstructured pieces of data. When DeepMind decided to tackle basic Atari games like Breakout and Pong, the input was nothing but raw pixels, and the output was predictions — likely target position — and then actions — racket placement. All of the above aimed at maximizing the subsequent reward: survival and score. After a few hundreds games, the machine was able to devise on its own creative strategies that would surprise even its creators (read here, or view this video, time code 10:27).

Over time, the tests will migrate to more complex environment such as 3D games in which it becomes harder to distinguish the pattern of a wall from a useful piece of information.

A rather challenging signa-to-noise environment

DeepMind’s future goals involves dealing with very large and complex sets of data such as genomics, climate, energy or macroeconomics.

Regardless of the nature of the input stream, the principle is roughly the same. The A.I. system relies on a deep neural network to filter raw sensory data and form meaningful patterns to be analyzed. It then builds an optimized statistical model, updates it in real time, and derives the best possible actions from the set of observations available at a given moment. Then the whole system loops back.

How does this connect to improving news production?

Before we get into this, let’s roll back a little bit.

For a news production system, recommending related stories or videos is the most efficient way to increase reader engagement. For media who rely on advertising, sold on CPM or on a per-click basis, raising the number of page views per reader has a direct impact on ad revenue. Paid-for media are less sensitive to page views, but reminding readers of the breadth and depth of an editorial production is a key contributor to a news brand’s status — and a way to underline its economic value.

But there is a problem: today’s news recommendation systems are often terrible.

To display related stories or videos, publishers unwilling to invest in smart, fine-tuned systems have settled for engines based on crude semantic analysis of content. Hence embarrassing situations arise. For example, a piece about a major pedophile cover-up by the French clergy will trigger suggestions about child care. Or another where the state of an intellectual debate will suggest a piece on spelling, or an another one about waste management. The worst are stories automatically proposed by Outbrain or Taboola and picked up all over the web: not only are they the same everywhere, but they tap into the same endless field of click-bait items. The only virtue of these two systems is the direct cash-back for the publisher.

Something needs to be done to improve recommendation systems. A.I. and Reinforcement Learning offer a promising path.

In Demis Hassabis’ demonstration, the important words are : Environment, Observations, Models, Predictions and Actions. Let’s consider these keywords in the context of news production and consumption.

The Environment is dual. The external side is built on the general news cycle. At any given moment, automatically assessing a topic’s weight is reasonably easy, but even though they’re critical to predicting how the news cycle will evolve, detecting low-noise signals is much trickier. As for the internal news environment, it is simply the output of various contents produced (or curated) by the newsroom.

Observations are multiple: they include the vast range of available analytics, again at two levels: how a piece of contents is faring in general (against the background noise or the competition), and how each individual reader behaves. Here, things become interesting.

Models are then fed with a mix of statistical and behavioral data such as: “Stories [x] containing [semantic footprint] perform well against context [of this type of information].” Or: Reader #453.09809 is currently interested by [topics], but she has on her radar this [low-noise topic] that is small but growing.

Predictions detect both contents and topics that have the best lift in the news cycle and pique the reader’s interest, dynamically, in real time.

Actions will then range form putting stories or videos in front of the audience and, more specifically, at the individual level. Personalization will shift from passive (the system serves stories based of the presumed and generally static reader profile) to dynamic, based on current and predicted interest.

Demis Hassabis makes clear that enhanced personalization is on DeepMind’s roadmap:

“Personalization doesn’t work very well. It currently sums up to averaging the crowd as opposed to adapting to the human individual”

It would be unrealistic to see a news outlet developing such A.I.-based recommendation engine on its own, but we could easily foresee companies already working on A.I. selling it as SaaS (Software as a Service.)

A new generation of powerful recommendation engines could greatly benefit the news industry. It would ensure much higher reader loyalty, reinforce brand trust (it recommends stories that are both good and relevant), and help build deeper and more consistent news packages while giving a new life to archives.

Who will jump on the opportunity? Probably those who are the most prone to invest in tech. I would guess Buzzfeed and the Jeff Bezos-owned Washington Post.

— frederic.filloux@mondaynote.com

推荐系统

Follow the Regularized Leader (FTRL) 算法

May 16, 2016 zr9558 2 Comments

（一）FTRL 的算法原理：

FTRL 算法综合考虑了 FOBOS 和 RDA 对于梯度和正则项的优势和不足，其特征权重的更新公式是：

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

上面的公式出现了 L2 范数，不过这一项的引入不会影响 FTRL 的稀疏性，只是使得求解结果更加“平滑”。通过数学计算并且放弃常数项可以得到上面的优化问题相当于求使得下面式子的最小的参数 W：

$(G^{(1:t)}-\sum_{s=1}^{t}\sigma^{(s)}W^{(s)})\cdot W + \lambda_{1}||W||_{1}+\frac{1}{2}(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})||W||_{2}^{2}$

如果假设 $Z^{(t)}=G^{(1:t)}-\sum_{s=1}^{t}\sigma^{(s)}W^{(s)}=Z^{(t-1)}+G^{(t)}-\sigma^{(t)}W^{(t)},$ 上式等价于

$W^{(t+1)}=argmin_{W}\{Z^{(t)}\cdot W + \lambda_{1}||W||_{1}+\frac{1}{2}(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})||W||_{2}^{2}\}$

写成分量的形式就是：

$argmin_{w_{i}}\{z_{i}^{(t)}w_{i}+\lambda_{1}|w_{i}|+\frac{1}{2}(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})w_{i}^{2}\}$

通过计算可以直接得到：

$w_{i}^{(t+1)}=0, \text{ if } |z_{i}^{(t)}|<\lambda_{1}$

$w_{i}^{(t+1)}=-(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})^{-1}\cdot(z_{i}^{(t)}-\lambda_{1}\cdot sgn(z_{i}^{(t)})) \text{ otherwise }$

由此可以证明：引入 L2 正则化并没有对 FTRL 的稀疏性产生影响。

（二）学习率

在 SGD 的算法里面使用的是一个全局的学习率 $\eta^{(t)}=O(t^{-0.5})$ ，意味着学习率是一个正数并且逐渐递减，对每一个维度都是一样的。而在 FTRL 算法里面，每个维度的学习率是不一样的。如果特征 A 比特征 B变化快，那么在维度 A 上面的学习率应该比维度 B 上面的学习率下降得更快。在 FTRL 中，维度 i 的学习率是这样定义的：

$\eta_{i}^{(t)}=\alpha/(\beta+\sqrt{\sum_{s=1}^{t}(g_{i}^{(s)})^{2}})$

按照之前的定义 $\sigma^{(1:t)}=1/\eta^{(t)}$ , 所以

$\sum_{s=1}^{t}\sigma^{(s)}=\eta_{i}^{(t)}=\alpha/(\beta+\sqrt{\sum_{s=1}^{t}(g_{i}^{(s)})^{2}})$

（三）FTRL 算法

FTRL Algorithm

（1）输入 ，初始化 

（2）for 
        
        for 
         
          // equals to 
         
         
         
         
        end
     end

（四）Logistic Regression 的 FTRL 形式

在 Logistic Regression 中，假设 $\sigma(a)=1/(1+\exp(-a))$ 是 sigmoid 函数， $y_{t} \in \{0,1\}$ ，需要预估 $p_{t}=\sigma(w_{t}\cdot w_{t})$ ，那么 LogLoss 函数是

$\ell_{t}(w_{t})=-y_{t}log(p_{t})-(1-y_{t})log(1-p_{t})$ ，

直接计算可得 $\nabla\ell(w)=(\sigma(w\cdot x_{t})-y_{t})x_{t}=(p_{t}-y_{t})x_{t}$ ，所以 Logistic Regression 的 FTRL 算法就是：

FTRL Algorithm (Logistic Regression)

（1）输入 ，初始化 

（2）for 
        for 
          // gradient of loss function
         
          // equals to 
         
         
         
         
        end
     end

推荐系统

分类模型的正负样本

February 2, 2016 zr9558 2 Comments

在机器学习，数据挖掘和推荐系统这几个大领域中，用支持向量机模型（Support Vector Machines）或者逻辑回归模型（Logistic Regression）做模型的预估是十分常见的事情。既然是分类模型，那么就需要确定正负样本，以便模型进行合理而有效的分类，因此如何根据具体的业务来确定正负样本就是一个十分关键的问题。

点击率预测的正负样本如何产生：

对于视频或者音频节目而言，分成几个种类：

喜欢的节目：用户当天播放过的节目；

历史的节目：用户在过去的一段时间内播放过所有节目；

曝光的节目：一段时间内对用户曝光的节目。

由此，正样本可以定义为用户当天播放过的节目，也就是“喜欢”。负样本则有两种选择方案：

（1）负样本指的是对用户曝光过的节目，但是用户至始至终都没有播放过，也就是说该节目并不在“历史”和“喜欢”两个分类里面。

（2）负样本指的是在整个抽样的池子里面，但是用户至始至终都没有播放过，也就是说该节目并不在“历史”和“喜欢”这两个分类里面。

此时还需注意抽样比例，一般来说负样本的个数/正样本的个数 = 1：1 或者 2：1。

但是视频类节目和广告有区别，有可能该节目只是因为标题取得好或者图片配的好，才会吸引用户进去点击，但是用户观看了很短的时间就发现不喜欢该节目。所以在选择正样本的时候，从某种层面上来说需要考虑用户的观看时间，设定一定的阀值或者一定的观看比例才能够反映用户是否喜欢该节目。比如YouTube的视频节目，不止有“订阅”，“添加到”，“分享”，还有能够反映用户喜好的“like”（顶一下），“dislike”（踩一下）。有的时候顶一下可能不足以反映用户是否喜欢，但是踩一下基本上可以确定该用户不喜欢这个视频节目。除了“like”和“dislike”，对于其余的一些APP或者视频网站，还会有其余的操作，比方说评论，分享，收藏，下载等操作。这些操作从某些层面上也会看出用户是否喜欢该节目。

推荐系统

特征工程简介

January 26, 2016 zr9558 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］上线测试：

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

Computer Science, 推荐系统

转行数据挖掘和机器学习

January 19, 2016 zr9558 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) 算法简介

January 12, 2016 zr9558 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 的算法：

输入 ，初始化 
for t = 1,2,3,... 计算 
按照下面规则更新 W,

    （i）当 t/k 不是整数时，采用标准的 SGD (Stochastic Gradient Descent) 进行迭代。，并且  for all .

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

     , if 

     , else if 

     , 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) 算法简介

January 12, 2016 zr9558 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）输入 ，初始化 
（2）for , 计算 
     按照公式更新 ， 
     for all 
（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)

January 12, 2016 zr9558 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\}$ 是一个非负递增序列。

从公式中可以看出：

$\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W$ 包括了之前所有梯度的平均值。
具有正则项 $\Psi(W)$ 。
额外项 $\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）输入 ，初始化 
（2）for  
         
         更新 ：
         
     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} \}$

可以看出：

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

推荐系统

点击率(CTR)融入物品相似度

October 9, 2015 zr9558 Leave a comment

假设物品 $A$ 与其余三个物品1，2，3的相似度分别是 $S_{A1}, S_{A2}, S_{A3}.$ 物品1，2，3的点击率（click through rate）分别是 $CTR(1), CTR(2), CTR(3).$ 此刻如果物品3的点击率过低，那么需要把第3个物品与物品 $A$ 的相似度降低，使得第4个物品与A的相似度 $S_{A4}>S_{A3},$ 从而使得第4个物品能够取代第3个物品。

定义物品 $A$ 与物品1，2，3的相似度如下：

$S_{Aj}^{'}(x)=\frac{S_{Aj}\cdot(x+CTR(j))}{x+(\sum_{k=1}^{3}S_{Ak}\cdot CTR(k))/(\sum_{k=1}^{3}S_{Ak})} \text{ for all }1\leq j\leq 3.$

其中 $x\geq 0$ 是待定的系数。下面就来研究新的相似度满足的性质。

性质1. 相似度的总和没有变化。i.e. $\sum_{j=1}^{3}S_{Aj}^{'}(x)=\sum_{j=1}^{3}S_{Aj}$ 对任何的实数 $x\geq 0$ 都成立。

性质2. 如果 $CTR(1)=\max_{1\leq k\leq 3}CTR(k),$ i.e. 第1个物品的点击率最高，那么

(i) $S_{A1}^{'}(x)\geq S_{A1}$ 对于任何 $x\geq 0$ 都成立。

(ii) $S_{A1}^{'}(x)$ 对于 $x$ 是非增函数，i.e. 导数 $DS_{A1}^{'}(x)\leq 0.$

(iii) $\lim_{x\rightarrow \infty}S_{A1}^{'}(x)=S_{A1}.$ 换句话说，随着 $x$ 的增大， $S_{A1}^{'}(x)$ 是递减趋向于原始的相似度 $S_{A1}.$

性质3. 如果第3个物品的点击率最低，i.e. $CTR(3)=\min_{1\leq k\leq 3} CTR(k),$ 那么

(i) $S_{A3}^{'}(x)\leq S_{A3}$ 对于任何 $x\geq 0$ 都成立。

(ii) $S_{A3}^{'}(x)$ 对于 $x$ 是非减函数，i.e. 导数 $DS_{A3}^{'}(x)\geq 0.$

(iii) $\lim_{x\rightarrow \infty}S_{A3}^{'}(x)=S_{A3}.$ 换句话说，随着 $x$ 的增大， $S_{A3}^{'}(x)$ 逐渐增大趋向于原始的相似度 $S_{A3}.$

(iv) 特别的，如果 $CTR(3)=0,$ 那么 $S_{A3}^{'}(0)=0,$ 通过选择合适的 $x_{0}\geq 0,$ 可以使得 $S_{A3}^{'}(x_{0})<S_{A4}.$ 在这里的 $S_{A4}$ 指的是物品 $A$ 与第4个物品的相似度。

推荐系统

物质扩散模型

September 27, 2015 zr9558 Leave a comment

引言

在推荐系统中，常常用二部图来表示用户和物品的关系：把用户（Users）看成一类点，把物品（Objects）看成另一类点。如果用户购买了某种物品，那么用户和物品之间就存在一条连线，也就是一条边。如果用户没有购买某种物品，那么用户和物品之间就没有连线。但是用户和用户之间，物品和物品之间是不存在连线的。换句话说就是同一类点之间是不存在连线的。这样的图结构就叫做二部图。电子商务中间的物品推荐，可以看成是二部图的边的挖掘问题。扩散过程可以用来寻找二部图中两个节点的关联强度。经典的扩散过程分成两类：一种叫做物质扩散（Probabilistic Spreading），它满足能量守恒定律；另一种叫做热传导（Heat Spreading），一般由一个或多个热源（物品）驱动，不一定满足能量守恒定律。

物质扩散（Probabilistic Spreading）算法流程

如图所示，用黄色的点来表示用户，用红色的点表示物品。用户有三位，物品有四个。第一个用户和第一个物品有连线表示第一个用户购买了第一个物品，而与第二个物品没有连线表示第一个用户没有购买第二个物品。根据图像(a)所示，第一个物品和第三个物品有能量1，第二个物品和第四个物品有能量0.对于物质扩散过程，第一个物品需要把自己的能量1平均分配给购买过它的用户一和用户二。第三个物品也需要把自己的能量1平均分配给购买过它的用户一和用户三。用户的能量就是所有用物品得到的能量的总和。正如图像(b)所示，第一个用户此时具有能量1，第二个和第三个用户都具有能量1/2.接下来，每个用户再把自身的能量平均分配给所有购买过的物品，物品的能量则是从所有用户得到的能量的总和。所以第一个物品的能量就是第一个用户的能量乘以0.5加上第二个用户的能量乘以1/3，所得的能量则是2/3.其他物品的能量用类似的方法计算。

物质扩散（Probabilistic Spreading）数学模型

假设有m个用户（Users）和n个物品（Objects），可以构造矩阵 $A_{m\times n},$ 如果 $a_{ij}=1$ ，那么表示用户i购买了物品j；如果 $a_{ij}=0$ , 那么表示用户i没有购买物品j。用 $(c_{1},\cdot\cdot\cdot, c_{n})$ 来表示物品1到物品n的能量。用 $k(U_{\alpha})=\sum_{j=1}^{n}a_{\alpha j}$ 表示用户 $\alpha$ 的度，也就是该用户购买的物品数量。用 $k(O_{j})=\sum_{i=1}^{m}a_{ij}$ 表示物品j的度，也就是该物品被多少个用户购买过。根据物质扩散的算法描述，第一步需要计算出用户从物品那里得到的能量，此时用户 $i$ 得到的能量用 $b_{i}$ 表示，那么

$b_{i}=\sum_{\ell=1}^{n} a_{i\ell}\cdot c_{\ell}/k(O_{\ell}) \text{ for all } 1\leq i\leq m.$

后面需要通过用户的能量来更新物品的能量，假设物品 $j$ 的新能量用 $c_{j}^{'}$ 表示，那么

$c_{j}^{'}=\sum_{i=1}^{m}a_{ij}\cdot b_{i}/ k(U_{i}) \text{ for all } 1\leq j \leq n.$

把 $b_{i}$ 的公式带入上面可以得到对于 $1\leq j\leq n,$ 我们有

$c_{j}^{'}=\sum_{\ell=1}^{n}\left(\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}\right)\cdot c_{\ell}=\sum_{\ell=1}^{n}w_{j\ell}^{P}\cdot c_{\ell}.$

在这里对于 $1\leq j\leq n, 1\leq \ell \leq n,$

$w_{j\ell}^{P}=\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}.$

假设 $n\times n$ 矩阵 $W^{P}=(w_{j\ell}^{P}),$ 列向量 $\vec{C}=(c_{1},\cdot\cdot\cdot,c_{n})^{T}$ 和 $\vec{C^{'}}=(c_{1}^{'},\cdot\cdot\cdot,c_{n}^{'})^{T}$ ，那么 $\vec{C^{'}}=W^{P}\vec{C}.$

性质1. 矩阵每列的和都是1，i.e. 对于所有的都成立。

证明. $\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{j=1}^{n}\sum_{i=1}^{m}\frac{1}{k(O_{\ell})}\cdot\frac{a_{ij}a_{i\ell}}{k(U_{i})}=\sum_{i=1}^{m}\frac{a_{i\ell}}{k(O_{\ell})}=1.$

性质2. 对于所有的都成立。换言之，矩阵不一定是对称矩阵，只有在所有物品的度都完全一致的情况下才是对称矩阵。

证明. 根据 $w_{j\ell}^{P}$ 和 $w_{\ell j}^{P}$ 的定义可以得到结论。

性质3. 矩阵对角线上的元素是该列的最大值。i.e. 对于所有的都成立。

证明. 根据矩阵 $A$ 的定义，对于所有的 $1\leq j,\ell\leq n,$ 可以得到

$w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}\geq\frac{1}{k(O_{j})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}=w_{\ell j}^{P}.$

性质4. 能量守恒定律：

证明. 根据前面的性质，已经知道 $W^{P}$ 矩阵每一列的和都是1，i.e. $\sum_{j=1}^{n}w_{j\ell}^{P}=1.$ 可以直接计算得到： $\sum_{j=1}^{n}c_{j}^{'}=\sum_{j=1}^{n}\sum_{\ell=1}^{m}w_{j\ell}^{P}c_{\ell}=\sum_{\ell=1}^{n}c_{\ell}\cdot\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{\ell=1}^{m}c_{\ell}.$

性质5. 如果物品的用户都是物品的用户，换句话说，如果 则有那么对于所有的都成立。反之，如果那么物品的用户都是物品的用户。

证明. 根据 $w_{j\ell}^{P}$ 的定义，可以得到

$w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{\{1\leq i\leq m, a_{ij}=1\}}\frac{1}{k(U_{i})},$

$w_{\ell j}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{i\ell}a_{ij}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{1\leq i\leq m, a_{ij}=1}\frac{a_{i\ell}}{k(U_{i})}.$

根据条件，如果 $a_{ij}=1,$ 则有 $a_{i\ell}=1,$ 那么上面两个式子相等。i.e. $w_{jj}^{P}=w_{\ell j}^{P}$ 对于所有的 $1\leq \ell \leq n$ 都成立。

根据上面性质，可以定义变量

$I_{j}=\sum_{\ell=1}^{n}(w_{\ell j}^{P}/w_{jj}^{P})^{2},$

其中 $w_{\ell j}^{P}/w_{jj}^{P}$ 可以看成物品 $O_{j}$ 与物品 $O_{j}$ 的独立程度。如果 $w_{\ell j}^{P}/w_{jj}^{P}=1,$ 那么说明物品 $O_{j}$ 的用户都是物品 $O_{\ell}$ 的用户。如果 $w_{\ell j}^{P}/w_{jj}^{P}=0,$ 那么说明物品 $O_{j}$ 的用户与物品 $O_{\ell}$ 的用户则没有交集。换言之，物品 $O_{j}$ 与物品 $O_{\ell}$ 则相对独立。根据这个性质，如果 $I_{j}$ 越小，那么物品 $O_{j}$ 与其他物品就相对独立。

性质6. 对于所有的都是成立的。

证明. 根据以上性质可以得到 $w_{\ell j}^{P}\leq w_{jj}^{P}$ 对于 $1\leq \ell \leq n$ 都成立，并且 $I_{j}\geq (w_{jj}^{P}/w_{jj}^{P})^{2}=1,$ 所以上面性质成立。

基于物质扩散算法的用户相似度

回顾一下基于用户的协同过滤算法：用户 $U_{\alpha}, U_{\beta}$ 的相似度是

$S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\min\{k(U_{\alpha}),k(U_{\beta})\}$

或者使用余弦表达式

$S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\sqrt{k(U_{\alpha})\cdot k(U_{\beta})}.$

如果用户 $U_{i}$ 并没有选择物品 $O_{j},$ 那么预测分数则是

$v_{ij}=(\sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}\cdot a_{j\ell}) / \sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}.$

这里的求和指的把除了用户 $i$ 的其他用户做相似度的加权，看用户 $U_{\ell}$ 是否购买了物品 $O_{j}.$ 然后对于任意的用户和物品组成的对 $(i,j),$ 只要 $a_{ij}=0$ （意思是用户 $U_{i}$ 并没有购买过物品 $O_{j}$ ），根据预测分数 $v_{ij}$ 从大到小对 $1\leq j\leq n$ 排序，推荐 $v_{ij}$ 值大的物品给用户 $U_{i}$ 即可。以上就是基于用户的协同过滤算法。

下面来介绍基于物质扩散方法的算法。与上面的方法类似，第一步就是定义用户相似度 $S_{\alpha \beta}^{P}$ 如下：

$S_{\alpha \beta}^{P}=\frac{1}{k(U_{\beta})}\cdot \sum_{j=1}^{n}\frac{a_{\alpha j}\cdot a_{\beta j}}{k(O_{j})}.$

上面定义表示物品 $O_{j}$ 购买的人越多，用户的相似度 $S_{\alpha \beta}^{P}$ 就会减少。原因就是比方说像新华字典这种购买的人非常多的物品，并不能说明大多数人都是相似的，反而是购买数学分析这种物品的人相似性比较大。也就是说物品的热门程度 $k(O_{j})$ 对计算用户相似度的时候有抑制作用。此时的评分系统则是：如果用户 $U_{\alpha}$ 之前没有购买物品 $O_{i},$ 那么其预测分数则是

$v_{\alpha i}=(\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}\cdot a_{\beta i})/\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}$

对于物质扩散的算法，可以用以下简单方法进行推广。增加参数 $d>0,$ 定义用户 $U_{\alpha}$ 和用户 $U_{\beta}$ 的相似度 $S_{\alpha \beta}^{P}(d)$ 如下：

$S_{\alpha \beta}^{P}(d)=\frac{1}{k(U_{\beta})}\cdot \sum_{j=1}^{n}\frac{a_{\alpha j}\cdot a_{\beta j}}{(k(O_{j}))^{d}}.$

当 $d>1$ 时，减弱了热门物品对用户相似度的影响；当 $d\in (0,1)$ 时，增加了热门物品对用户相似度的影响。某篇论文显示基于某些数据， $d=1.9$ 是最佳的参数。

（一）FTRL 的算法原理：

（二）学习率

（三）FTRL 算法

（四）Logistic Regression 的 FTRL 形式

点击率预测的正负样本如何产生：

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

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

（III）特征有用性的预估

（IV）特征的构造过程

［1］任务的确定：

［2］数据的选择：

［3］预处理数据：

［4］特征的构造：

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

［6］模型的使用：

［7］上线的效果：

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

［1］选择特征：

［2］设计特征：

［3］判断特征：

［4］计算模型：

［5］上线测试：

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

2.编程语言

3.操作系统

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

5. 统计学：

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

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

等价条件：

损失函数：

传统算法（Gradient Descent）

传统算法（Stochastic Gradient Descent）

Truncated Gradient 算法简介

（1）L1 正则化法

（2）简单截断法

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

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

Truncated Gradient -> 简单截断法

Truncated Gradient -> L1 正则化

FOBOS 算法简介

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

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

L1-FOBOS 的算法：

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

Regularized Dual Averaging Algorithm 算法介绍

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

（二）RDA 的 L1 正则化

RDA 的算法

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

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

引言

物质扩散（Probabilistic Spreading）算法流程

物质扩散（Probabilistic Spreading）数学模型

基于物质扩散算法的用户相似度

zr9558's Blog