强化学习观点下的社交推荐系统构建

testtest

强化学习观点下的社交推荐系统构建

在构建系统时存在着 exploration 和 Exploitation 的交替进行的两个过程,我们其实对数据本身的理解和掌握非常粗陋,随着不同侧面的观察增多,就能够掌握住新的认识。我们使用不同的算法就是一种探索,而对某个算法深入的改进和组装则是开发的过程。期望能够通过这个过程不断深化对系统的认识。

可以将自己的软件机器学习系统看成是一个 agent,整个项目(包括用户的行为)作为一个环境,那么系统是和环境不断地进行交互进行演化的。什么是好的,什么是不好的?都是需要时实验才会知道这些内容。

更加复杂的建模可以刻画出更加有趣丰富的场景,但也会带来难以处理的境况。所以,我们需要寻求探索和开发之间的平衡点。

算法是一些些分离的部分,通过数据流我们穿针引线地将这些算法赋予了生命力。其中就出现了动态性。不同的产品,其中流动的血液是不同的,也就形成不同的产品自身的特性。整个产品类似于一个人,其不同的部分则是人的各种组织和器官。

因此,我们就要像观察一个人那样去观察一个产品的整个系统。了解哪些是最为核心的部分,哪些可有可无,哪些能够给出惊喜。这个过程是一个试错的过程。既要保持一定的演变稳定性,也要保持系统的活力。

所以在系统的设计过程中,就应该给出一定的空间让其能够获得新鲜的血液和养料,让系统能够自然的生长和扩展。因此,我在这里给出一个开放式的设计架构,来满足推荐系统的动态生长和不断强化。

以人为本的架构理念

作为一款产品,必须具备人性化的设计感和体验感,你必须时时将用户的感受放在首位。因为现在的产品,太多的雷同,太多的硬推广告,已经失去的本性的美好。

所谓以人为本,就是关注用户产生的行为,关心用户的正常反馈。

数据的产生和收集

众所周知,数据是推荐系统的源动力,常常有人将数据比作是机器学习算法的燃料,这里是一个意思。

数据产生

产生的方式很多种,这些就需要产品设计的考究。设计什么样的数据入口方式,以多少的代价来产生一个数据点,应该是要结合算法和业务两个方面的考量来确定的。有些时候这不是简简单单的一个选择项或者文本框就能够解决的。更加有艺术感和美感的方式往往能够带来更多的用户行为(选择、点击或者输入等行为)。拿简书的场景来看,主要是阅读、喜欢、评论、打赏、加入专题或者分享等操作。这些设计的便利会有效提升用户操作的概率。从这里出发,数据就会如石油被开发那样,逐步地喷发出来。

  1. 忽略模型过程和细节
  2. 样本的精细化处理
  3. 过于依赖算法
  4. 核心数据控制
  5. 团队的全栈性
  6. 系统边界模糊/巨型系统
  7. 基础数据架构建设
  8. 总结

大数据和机器学习 缺一不可,所有的算法都要可并行化、分布化才是可接受的。我的经验在哪里。
我在小规模的数据下的习得经验是否可以推广出来,放在更大的数据集合上进行训练和预测。这是现在人们最为关心的问题,谷歌、华为、微软、脸书等等都在进行这样的工作。

因此,本文想要从问题的根本之处出发来摸清楚这条脉络。

计算机能够处理的问题是可以量化和抽象的。最终实际上就是对函数的各种角度的掌握。

从问题出发,到解决的大的方向,再到细致的小的方向,最后汇集成最终的解决方案。这个过程是一个封闭可以演化的。

演化指的是稳定的变化过程。数据本身的生命力背后是产生这些行为的人类的生活行为做出的支撑。

各个领域,各个行业有着不同的目标。终极的就是认识这个世界的背后规律。行业则次之,可能就是去赚得回报,创造好的产品和服务,再赚得回报。这些都是让我们的生活更加丰富和有生命力的创造。

整个社会的进步在不同的领域和行业之间的互相学习不断融合的过程。知识最终变成了自然的反应。

整个国家要解决的问题其实是个体自由放大和整体的稳定性之间的矛盾。如何解决是需要大智慧的。

大智慧如何获得?需要各种工具技术和方法思想的支持。

计算是一种重要的思想,量化的东西都可以拿过来算。一个方法的好坏也有评判的机制。最终给出一个排序。等等。

好了,现在开始来理清解决的思路。我们将要观察这个真实世界。但是如果用一种完全的思想来看她,你基本上得不到太好的指导。因为她真实太复杂了。

以强化学习为工具探索世界

Spark-Mllib-Matrix

MLlib 中的线性代数支持有 Breeze 和 jblas 两种。

Local vector 本地向量

根据存储单元的值分为两个类型:整数型和双精度数值,是存放在一台机器上的。MLlib 支持两种类型的本地向量:稠密和稀疏。稠密向量是由一个 Double 矩阵表示内部元素值的,而稀疏向量则是由两个平行的矩阵表示:索引数组和值数组。例如,向量 (1.0,0.0,3.0) 可以用稠密的方式 [1.0, 0.0, 3.0] 表示或者用稀疏的形式 (3, [0, 2], [1.0, 3.0]) 表示,其中 3 是向量的维度.

1
2
3
4
5
6
7
8
import org.apache.spark.mllib.linalg.{Vector, Vectors}

// Create a dense vector (1.0, 0.0, 3.0).
val dv: Vector = Vectors.dense(1.0, 0.0, 3.0)
// Create a sparse vector (1.0, 0.0, 3.0) by specifying its indices and values corresponding to nonzero entries.
val sv1: Vector = Vectors.sparse(3, Array(0, 2), Array(1.0, 3.0))
// Create a sparse vector (1.0, 0.0, 3.0) by specifying its nonzero entries.
val sv2: Vector = Vectors.sparse(3, Seq((0, 1.0), (2, 3.0)))

Labeled point 带标记点

Local matrix 本地矩阵

Distributed matrix 分布式矩阵

REINFORCE 算法

原文地址:https://rllab.readthedocs.io/en/latest/user/implement_algo_basic.html

本节,我们将学习一下经典 REINFORCE 算法的实现,这样被称为“基本”策略梯度方法。我们会从一个应用在固定策略和环境开始。下一节会实现进阶版本,使用框架提供的功能来让整个项目更加结构化并对命令行友好。

预备知识

首先,我们简要回顾一下算法和一些基本符号。我们采用定义为 (S,A,P,r,μ0,γ,T),其中S是状态集合,A 是行动集合,P:S×A×S[0,1] 是转移概率,P:S×AR 是奖励函数,γ[0,1] 是折扣因子,而 TN 是片段长度。REINFORCE 算法直接优化参数化的随机策略 πθ:S×A[0,1],通过执行在期望奖励目标函数的梯度上升:

η(θ)=E[Tt=0γtr(st,at)]

其中期望是隐式地覆盖所有可能的轨迹,按照采样过程 s0μ0,atπθ(˙|st),而 st+1P(˙|st,at)。通过似然比例技巧,目标函数关于 θ 的梯度如下式给出:

θη(θ)=E[(Tt=0γtr(st,at))(Tt=0θlogπθ(at|st))]

注意到对 t<t

E[r(st,at)θlogπθ(at|st)]=0

我们可以降低估计量方差。

因此,

θη(θ)=E[Tt=0θlogπθ(at|st)Tt=tγtr(st,at)]

通常,我们使用下面的估计代替:

θη(θ)=E[Tt=0θlogπθ(at|st)Tt=tγttr(st,at)]

其中,γtγtt 代替。我们将折扣因子看成是对无折扣目标函数的方差降低因子时,会得到更小偏差的梯度估计,会带来一定的方差增大。我们定义 Rt:=Tt=tγttr(st,at) 为经验折扣奖励。

上面的公式是我们实现的核心。整个算法的伪代码如下:

  1. 初始化参数为 θ1 的策略 π.
  2. 对迭代 k=1,2,:
    1. 根据当前策略 θk 采样 N 个轨迹 τ1,,τn,其中 τi=(sit,ait,Rit)T1t=0.注意到因为在观察到最后的状态时无行动了已经,所以最后的状态丢弃。
    2. 计算经验策略梯度:^θη(θ)=1NTNi=1T1t=0θlogπθ(ait|sit)Rit
    3. 进行一步梯度计算:θk+1=θk+α^θη(θ)

准备工作

作为开始,我们试着使用神经网络策略来解决 cartpole 平衡问题. 后面我们会推广算法来接受配置参数. 现在先看看最简单形式.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from __future__ import print_function
from rllab.envs.box2d.cartpole_env import CartpoleEnv
from rllab.policies.gaussian_mlp_policy import GaussianMLPPolicy
from rllab.envs.normalized_env import normalize
import numpy as np
import theano
import theano.tensor as TT
from lasagne.updates import adam

# normalize() makes sure that the actions for the environment lies
# within the range [-1, 1] (only works for environments with continuous actions)
env = normalize(CartpoleEnv())
# Initialize a neural network policy with a single hidden layer of 8 hidden units
policy = GaussianMLPPolicy(env.spec, hidden_sizes=(8,))

# We will collect 100 trajectories per iteration
N = 100
# Each trajectory will have at most 100 time steps
T = 100
# Number of iterations
n_itr = 100
# Set the discount factor for the problem
discount = 0.99
# Learning rate for the gradient update
learning_rate = 0.01

收集样本

现在,一次迭代中在我们当前的策略下收集样本.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
paths = []

for _ in xrange(N):
observations = []
actions = []
rewards = []

observation = env.reset()

for _ in xrange(T):
# policy.get_action() returns a pair of values. The second one returns a dictionary, whose values contains
# sufficient statistics for the action distribution. It should at least contain entries that would be
# returned by calling policy.dist_info(), which is the non-symbolic analog of policy.dist_info_sym().
# Storing these statistics is useful, e.g., when forming importance sampling ratios. In our case it is
# not needed.
action, _ = policy.get_action(observation)
# Recall that the last entry of the tuple stores diagnostic information about the environment. In our
# case it is not needed.
next_observation, reward, terminal, _ = env.step(action)
observations.append(observation)
actions.append(action)
rewards.append(reward)
observation = next_observation
if terminal:
# Finish rollout if terminal state reached
break

# We need to compute the empirical return for each time step along the
# trajectory
returns = []
return_so_far = 0
for t in xrange(len(rewards) - 1, -1, -1):
return_so_far = rewards[t] + discount * return_so_far
returns.append(return_so_far)
# The returns are stored backwards in time, so we need to revert it
returns = returns[::-1]

paths.append(dict(
observations=np.array(observations),
actions=np.array(actions),
rewards=np.array(rewards),
returns=np.array(returns)
))

根据经验策略梯度的公式,我们可以将所有搜集来的数据合在一起,这样可以帮助我们向量化实现.

1
2
3
observations = np.concatenate([p["observations"] for p in paths])
actions = np.concatenate([p["actions"] for p in paths])
returns = np.concatenate([p["returns"] for p in paths])

构造计算图

我们使用 Theano 来实现,假设读者已经对其有了了解。如果没有,请参考 some tutorials.

首先,我们构造输入数据的符号变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Create a Theano variable for storing the observations
# We could have simply written `observations_var = TT.matrix('observations')` instead for this example. However,
# doing it in a slightly more abstract way allows us to delegate to the environment for handling the correct data
# type for the variable. For instance, for an environment with discrete observations, we might want to use integer
# types if the observations are represented as one-hot vectors.
observations_var = env.observation_space.new_tensor_variable(
'observations',
# It should have 1 extra dimension since we want to represent a list of observations
extra_dims=1
)
actions_var = env.action_space.new_tensor_variable(
'actions',
extra_dims=1
)
returns_var = TT.vector('returns')

注意到,我们可以将策略梯度公式变换如下:

^θη(θ)=θ(1NTNi=1T1t=0logπθ(ait|sit)Rit)=θL(θ)

其中 L(θ)=1NTNi=1T1t=0logπθ(ait|sit)Rit 被称为 surrogate 函数. 因此,我们可以首先构造 L(θ) 的计算图,然后用其梯度获得经验策略梯度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# policy.dist_info_sym returns a dictionary, whose values are symbolic expressions for quantities related to the
# distribution of the actions. For a Gaussian policy, it contains the mean and (log) standard deviation.
dist_info_vars = policy.dist_info_sym(observations_var, actions_var)

# policy.distribution returns a distribution object under rllab.distributions. It contains many utilities for computing
# distribution-related quantities, given the computed dist_info_vars. Below we use dist.log_likelihood_sym to compute
# the symbolic log-likelihood. For this example, the corresponding distribution is an instance of the class
# rllab.distributions.DiagonalGaussian
dist = policy.distribution

# Note that we negate the objective, since most optimizers assume a
# minimization problem
surr = - TT.mean(dist.log_likelihood_sym(actions_var, dist_info_vars) * returns_var)

# Get the list of trainable parameters.
params = policy.get_params(trainable=True)
grads = theano.grad(surr, params)

梯度更新和诊断

我们基本上完成了!现在,你可以使用自己喜欢的随机优化算法来执行参数的更新。我们使用 ADAM:

1
2
3
4
5
6
7
f_train = theano.function(
inputs=[observations_var, actions_var, returns_var],
outputs=None,
updates=adam(grads, params, learning_rate=learning_rate),
allow_input_downcast=True
)
f_train(observations, actions, returns)

因为算法是同策略的,我们可以通过查看收集的样本来评价其性能:

1
print('Average Return:', np.mean([sum(path["rewards"]) for path in paths]))

完整的代码参考 examples/vpg_1.py.

策略梯度的方差可以通过增加基准函数的方式进一步降低。重新定义的公式如下

^θη(θ)=1NTNi=1T1t=0θlogπθ(ait|sit)(Ritb(sit))

由于 E[θlogπθ(ait|sit)b(sit)]=0 我们才能得到这个结果.

基准函数一般实现为 Vπ(s) 的估计。这里,RiTb(sit)Aπ(sit,ait) 的估计. 该框架实现了一些类基准函数的不同选择。通过使用状态特征的线性基准函数在性能和准确度方面进行了较好的平衡,可在 rllab/baselines/linear_feature_baseline.py 中查看. 使用这个实现的相关的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# ... initialization code ...
from rllab.baselines.linear_feature_baseline import LinearFeatureBaseline
baseline = LinearFeatureBaseline(env.spec)
# ... inside the loop for each episode, after the samples are collected
path = dict(observations=np.array(observations),actions=np.array(actions),rewards=np.array(rewards),)
path_baseline = baseline.predict(path)
advantages = []
returns = []
return_so_far = 0
for t in xrange(len(rewards) - 1, -1, -1):
return_so_far = rewards[t] + discount * return_so_far
returns.append(return_so_far)
advantage = return_so_far - path_baseline[t]
advantages.append(advantage)
# The advantages are stored backwards in time, so we need to revert it
advantages = np.array(advantages[::-1])
# And we need to do the same thing for the list of returns
returns = np.array(returns[::-1])

规范化回报

现在我们的学习率常会受到奖励的值范围的影响. 我们可以通过在计算梯度前进行白噪化 advantage 来降低这个依赖。用代码就是:

1
advantages = (advantages - np.mean(advantages)) / (np.std(advantages) + 1e-8)

训练基准函数

在每个迭代,我们使用最新获得的轨迹来训练基准函数:

1
baseline.fit(paths)

在计算基准函数之后执行本步骤的原因是在极端情形下,如果我们从每个状态仅仅有一个轨迹,并且基准函数能够完美地拟合数据,那么所有的advantages会变成 0,这样就没有梯度信号了。

现在,我们可以更快地训练策略(我们需要改变学习率因为重新规范化了). 完整的代码在 examples/vpg_2.py 可得.

Read More

Inverse Reinforcement Learning for Learning the Cost Function

动机. 现在已经有了离散时间,连续空间和行动的动态系统,其中动态规律已知,还有二次代价函数:

xt+1=f(xt,ut)

V(x1,,xN)=Ht=0xtQxt+utRut

通常假设代价/奖励函数已知的,如在 AlphaGo 中:很多时间的代价是 0,在比赛结束时才会出现 1+1. 然而,在很多情况下,关于代价函数自然的表达是非常难的,可能需要从数据中学习。从观测的行为中学习代价/奖励函数的问题被称为 inverse RL.

关键的假设是真实的奖励函数可以用一个已知特征的线性组合表示.

在直升机例子中,我们可以将代价矩阵 QR 看做是对角矩阵:

Q=[q1000q2000qn],R=[r1000r2000rn]

设计代价矩阵 QR 就成了权衡不同的状态和行动变量的系数选择问题. 代价函数定义如下:

xQx+uRu=wϕ(x,u) where w=[q1qnr1rm]Rm+n

未知向量 w 制定了不同的考量因素之间的相对权重.

学习目标. 策略 π 的期望值可以写成:
Ex0I[Vπ(x0)]=E[Ht=0R(xt,ut)]=E[Ht=0wϕ(xt,ut)]=wE[Ht=0ϕ(xt,ut)]=wμ(π)

其中 μ(π)=E[Ht=0ϕ(xt,ut)]

被称为特征期望. 因此值函数可以简洁地表示成 w 和策略特征期望的内积.

我们使用一些专家的策略 πE 的演示来学习参数 w,其中的特征期望为 μE=μ(πE). 假设受限参数 wRk 满足 ||w||11,则目标是找到策略 ˜π 使得 ||μ(˜π)μE||2ϵ,因为这样的策略 ˜π 会保证:

|E[Ht=0R(xt,ut)|˜π]E[Ht=0R(xt,ut)|~πE]|=|wμ(˜π)wμE|||w||2||μ(˜π)μE||21ϵ=ϵ

Inverse RL 算法. 算法主要过程如下:

  • 初始化:随机选择某个策略 π0,计算(或者通过 Monte Carlo 近似)μ0=μ(π0)
  • 主要循环:
    1. 对每个 i1,计算
      ti=maxw:||w||21minj0,,i1w(μEμj)

      wi 为达到最大值的 w 的值
    2. 如果 tiϵ,终止
    3. 否则,使用某个 RL 算法来计算最优策略 πi 使用奖励 R=wiϕ
    4. 计算(或者估计)μi=μ(πi)
    5. 设置 i=i+1,回到 step 1

注意到在 Step 1 中的优化等价于 SVM 的优化问题:
minimizet,wts.t.wμEwμj+t,j=1,,i1||w||21

假设算法在 n 步之后终止,tn+1ϵ,那么根据上面这个优化问题,我们有:
wwith||w||21is.t.wμiwμEϵ

特别地,因为 ||w||2||w||11,这意味着在 {π0,π1,,πn} 中存在至少一个策略其性能在 R 下至少和专家性能减去 ϵ 一样好.
分析. 算法保证在 n=O(kϵ2logkϵ) 次迭代后终止,其中 k 是特征映射 ϕ 的维度. 最后,尽管算法在专家特征期望 πE 上进行优化.
这个量常常是未知的,因此 m 个不同的专家轨迹的 Monte Carlo 样本需要拿来产生 πE 的估计 ˆπEm 个估计的经验均值). 1 中的定理 2 给出需要保证算法高概率正确的专家轨迹的充分数目. 参考 1 更详细的表述和证明.


1 P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2004.


Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Universality All Rights Reserved.

UV : | PV :