Category Archives: 推荐系统

DeepMind Could Bring The Best News Recommendation Engine

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]

409_reiforcmt_lrng

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.

409_starcraft

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.

409_AI_main

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

Advertisements

Follow the Regularized Leader (FTRL) 算法

(一)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)输入 \alpha, \beta, \lambda_{1},\lambda_{2},初始化 W\in\mathbb{R}^{N}, Z=0\in\mathbb{R}^{N}, Q=0\in\mathbb{R}^{N}

(2)for t=1,2,3,.....
        G=\nabla_{W}\ell(W,X^{(t)},Y^{(t)})
        for i=1,2,...,N
         \sigma_{i}=\alpha^{-1}(\sqrt{q_{i}+g_{i}^{2}}-\sqrt{q_{i}})
         q_{i}=q_{i}+g_{i}^{2} // equals to (\eta^{(t)})^{-1}-(\eta^{(t-1)})^{-1}
         z_{i}=z_{i}+g_{i}-\sigma_{i}w_{i}
         \text{if } |z_{i}^{(t)}|<\lambda_{1}, w_{i}=0
         \text{otherwise, }
         w_{i}^{(t+1)}=-(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})^{-1}\cdot(z_{i}^{(t)}-\lambda_{1}\cdot sgn(z_{i}^{(t)}))
        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)输入 \alpha, \beta, \lambda_{1},\lambda_{2},初始化 W\in\mathbb{R}^{N}, Z=0\in\mathbb{R}^{N}, Q=0\in\mathbb{R}^{N}

(2)for t=1,2,3,.....
        for i=1,2,...,N
         g_{i}=(p_{t}-y_{t})x_{i} // gradient of loss function
         \sigma_{i}=\alpha^{-1}(\sqrt{q_{i}+g_{i}^{2}}-\sqrt{q_{i}})
         q_{i}=q_{i}+g_{i}^{2} // equals to (\eta^{(t)})^{-1}-(\eta^{(t-1)})^{-1}
         z_{i}=z_{i}+g_{i}-\sigma_{i}w_{i}
         \text{if } |z_{i}^{(t)}|<\lambda_{1}, w_{i}=0
         \text{otherwise, }
         w_{i}^{(t+1)}=-(\lambda_{2}+\sum_{s=1}^{t}\sigma^{(s)})^{-1}\cdot(z_{i}^{(t)}-\lambda_{1}\cdot sgn(z_{i}^{(t)}))
        end
     end

 

分类模型的正负样本

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

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

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

喜欢的节目:用户当天播放过的节目;

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

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

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

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

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

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

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

特征工程简介

(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]上线测试

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

转行数据挖掘和机器学习

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

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

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

现在做在线学习和 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) 算法简介

 

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)})
     按照公式更新 Ww_{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 在一些特定条件下的形式。