幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

请贾
5 years ago
Views:

1 Poisson Distribution Poisson Process Poisson Factorization Ruizhi Wu, Big Data Research Center, UESTC

2 Abstract This slide will briefly introduce poisson distribution, poisson process and poisson factorization by using some realistic example and simple math methods. Then we will introduce event model by poisson point process and recommend system by poisson factorization. Content Poisson Distribution Poisson Process Poisson Factorization Two examples Poisson distribution Poisson Process Event model Basic Model Extension Model 2

3 Poisson Distribution---Two examples 已知某家小杂货店, 平均每周售出 2 个水果罐头请问该店水果罐头的最佳库存量是多少?( 暂时不考虑水果罐头的保质期 ) 3

4 Poisson Distribution---Two examples 1982 年至 2012 年, 美国共发生 62 起 ( 大规模 ) 枪击案其中,2012 年发生了 7 起, 是次数最多的一年 2012 年有这么多枪击案, 这是巧合, 还是表明美国治安恶化了? 4

5 Poisson Distribution---Two examples 以上的两个例子中, 我们可以做出如下的近似假设 : 发生枪击案和顾客购买水果罐头都是小概率事件 ; 发生枪击案或者购买水果罐头的顾客, 各个事件之间是独立的, 不会互相影响 ; 发生枪击案件或顾客购买水果罐头的概率是相对稳定的在统计学中, 满足上述三个条件的事件, 服从泊松分布 PP(XX = kk) = ee λλ λλ kk kk! 5

6 Poisson Distribution Siméon Denis Poisson 1781~1840 Life is good for only two things: to study mathematics and to teach it. 6

7 Poisson Distribution 泊松分布 : PP(XX = kk) = ee λλ λλ kk kk! P: 随机变量 X 发生 k 次的概率 ; X: 随机变量 ; k:x 的取值 (0,1,2,3...); λ: 是单位时间 ( 或单位面积 ) 内随机事件的平均发生率泊松分布的期望和方差均为 λλ 泊松分布适合于描述单位时间 ( 或空间 ) 内随机事件发生的次数如某一服务设施在一定时间内到达的人数, 电话交换机接到呼叫的次数, 汽车站台的候客人数, 由于泊松分布天然的特性, 适合对人类行为进行建模 7

8 Poisson Distribution PP(XX = kk) = ee λλ λλ kk kk! 罐头的例子中, λ = 2 如果存货 4 个罐头, 95% 的概率不会缺货 ( 平均每 19 周发生一次 ); 如果存货 5 个罐头,98% 的概率不会缺货 ( 平均 59 周发生一次 ) 8

9 Poisson Distribution 发生枪击案和顾客购买水果罐头都是小概率事件 ; 发生枪击案或者购买水果罐头的顾客, 各个事件之间是独立的, 不会互相影响 ; 发生枪击案件或顾客购买水果罐头的概率是相对稳定的判断美国治安是否发生恶化, 关键是判断枪击案的发生概率是否稳定, 如果稳定, 则治安没有恶化, 如果枪击案的概率增大, 则治安恶化严重 ( 既假设 3 是否成立 ) 9

10 Poisson Distribution 根据资料, 年枪击案的分布情况如下表所示 : 平均每年发生 2 起枪击案, 所以 λ = 2 10

11 Poisson Distribution 11

12 Poisson Distribution λ = 2 PP(XX = kk) = ee λλ λλ kk kk! 12

13 Poisson Distribution 卡方统计量 = Σ [ ( 观察值 - 期望值 ) ^ 2 / 期望值 ] 结论 : 卡方统计量等于 9.82 查表后得到, 置信水平 0.90 自由度 7 的卡方分布临界值为因此, 卡方统计量小于临界值, 这表明枪击案的观察值与期望值之间没有显著差异可以接受 " 发生枪击案的概率是稳定的 " 假设, 也就是说, 从统计学上无法得到美国治安正在恶化的结论 13

14 Brief summary Poisson Distribution 泊松分布的概率函数为 : 特征函数 : k e P(X = k) =, k = 0,1,2... k! λ λ it ψ( t) = exp( λ( e 1)) ( 在概率论中, 任何随机变量的特征函数完全定义了它的概率分布 ) 期望与方差 : λλ 14

15 Poisson Distribution 不同 λλ: P(X) λ = positive X P(X) λ = positive x 0.3 P(X) λ = 3 P(X) λ = positive X positive X 15

16 Poisson Distribution 泊松分布与二项分布 : 当二项分布的 n 很大而 p 很小时, 泊松分布可作为二项分布的近似, 其中 λ 为 np 事实上, 泊松分布正是由二项分布推导而来的具体推到请向度娘打听, 此处不多说 ~ 假设 : 事件发生的概率是相对稳定的各个事件之间是独立的, 不会互相影响 ; 16

17 Poisson Process 人类很多行为可以视作在一定单位时间内的一个事件, 同样类型的事件发生的次数整体可以通过泊松过程进行刻画, 因为在随机过程中, 泊松过程能够很好的刻画计数过程 k e P(X = k) =, k = 0,1,2... k! λ λ 通过泊松过程刻画事件主要是刻画单位时间或单位空间内, 时间发生的强度或次数分析事件各种因素与发生次数 λλ 的关系, 构建表达式 λ 上面构建的表达式通常称作 Intensity function 19

18 Poisson Process 假设 : 事件发生的概率是相对稳定的各个事件之间是独立的, 不会互相影响 ; 假设 1 确定了 λλ 是一个常量在早期的研究中, 认为人类活动是均匀的 2005 年 Nature 一篇文章直指人类活动是非均匀的 λ time location item... preference social 20

19 Poisson Process 时间维度是恒定且无限延长的 Intensity function: λ(t) 构建单位时间内的概率密度假设 : 事件发生的概率是相对稳定的各个事件之间是独立的, 不会互相影响 ; 人类活动既然随着时间偏好社交以及其他影响, 事件之间必然会产生影响, 所以构建事件之间的影响也是建模需要考虑的因素 19

20 Poisson Process Model location time itme group λ(t) preference Recurrent Influence social 预测 : tt ff tt = λλ tt eeeeee( λλ(ττ) ddττ) 00 20

21 Poisson Process 过去的影响, 偏好, 时间等与发生频率是一个黑箱模型直接在 RNN 中进行学习, 过去的影响用这种循环神经网络进行学习 Recurrent Marked Temporal Point Processes: Embedding Event History to Vector[C] KDD 21

22 Poisson Process h = max{ W y + Wt + W h + b,0} y t h j j j j 1 h Recurrent Marked Temporal Point Processes: Embedding Event History to Vector[C] KDD 22

23 Poisson Process 认为用户 (user), 商品 (product) 是线性关系, 单独加一个时间核函数, 对过去事件的影响进行模拟 Recurrent Poisson Factorization for Temporal Recommendation[C]. KDD

24 Poisson Process λ ( tlc,, ) = λ ( tc, ) f ( l tc, ) * * * u L 代表 location, t 为时间, c 为 location 的类别, 下表 u 代表 user,intensity function 采用条件分布的方法进行构建, 认为三元组 (t,l,c) 为联合分布的关系周期性 Spatio-Temporal Modeling of Check-ins in Location-Based Social Networks[J]

25 Brief summary Poisson Process Motivation: 分析事件发生次数的影响因素, 构建基于时间的 Intensity function 建立非均匀有记忆性的泊松过程, 学术名次 Marked Point Process Model: 分析事件发生次数的影响因素 ; 时间记忆性, 既过去事件发生对未来时间产生的影响方法 : 各种因素的黑箱模型, 采用循环神经网络产生记忆效应 ; 采用分解的方法, 单独加核函数构成时间上影响 ; 采用联合分布的方法, 在分布中加周期函数, 构成记忆效应 25

26 SVD SVD 是一种矩阵分解方法, 从本质上说是一种特殊的 PMF 评分矩阵 : RR UU II = U UU KK VV KK II rr uuuu = UU uu TT VV ii 损失 : ee uuuu = rr uuuu rr uuuu SSSSSS = 1 2 uu,ii ee 2 uuuu uu uu vv ii 2 KK KK KK = 1 2 uu,ii (rr uuuu kk=1 uu uuuu vv kkkk ) λλ uu,ii kk=1 uu 2 uuuu λλ uu,ii kk=1 2 vv kkkk 26

27 Probabilistic Matrix Factorization 用贝叶斯的观点看,R 是观测到的值,U,V 描述了系统的内部特征, 是需要估计的对一个近似矩阵进行分解 R = UU TT VV 要求近似矩阵 RR 在观测到的评分部分和观测矩阵 R 尽量相似为了防止过拟合, 需要对 U,V 做某种形式的约束 PMF Model 观测噪声 ( 观测评分矩阵 R 和近似评分矩阵 RR 之差 ) 为高斯分布用户属性 U 和电影属性 V 均为高斯分布 27

28 Probabilistic Matrix Factorization 评分矩阵的条件概率的先验也服从高斯分布 : pp RR UU, VV, δδ 2 = MM uu=1 NN ii=1 [NN(RR uu,ii U TT uu VV ii, δδ 2 RR )] II RR uu,ii RR 其中 I uu,ii 是指示函数, 当用户 u 对物品 v ii 有评分时, 为 1, 否则为 0 假设商品 V 与用户 U 的特征矩阵都服从高斯分布 : pp UU σσ uu 2 = MM uu=1 NN(UU uu 0, σσ 2 uu II) pp VV σσ 2 ii = NN ii=1 NN(VV ii 0, σσ 2 ii II) 28

29 Probabilistic Matrix Factorization 利用贝叶斯推导, 可得到用户和物品的隐式特征的后验概率 : PP UU, VV RR, δδ RR 2, δδ uu 2, δδ vv 2 = pp RR UU, VV, δδ 2 pp UU σσ uu 2 pp VV σσ ii 2 = MM uu=1 NN ii=1 [NN(RR uu,ii U TT uu VV ii, δδ 2 RR )] II uu,ii RR MM uu=1 NN(UU uu 0, σσ 2 uu II) NN ii=1 NN(VV ii 0, σσ 2 ii II) 对上式取对数求极大, 就可以得到在已知参数 δδ R 2, δδ VV 2, δδ UU 2, 和评分矩阵的前提下得到最有可能的 U 和 V 的隐式特征矩阵最大化后验概率 : 29

30 Probabilistic Matrix Factorization 高斯分布和其对数形式 : pp xx = 1 2ππππ exp( (xx μμ)2 2δδ 2 ) lnn pp(xx) = lnn( 2ππππ) (xx μμ)2 2δδ 2 等同于优化 : 最终优化目标 : 30

31 Probabilistic Matrix Factorization Graph Model: 31

32 Hierarchical Poisson Factorization Motivation: 不能保证推荐出的评分为非负的, 这是由于假设高斯分布的先天缺陷 (NMF 已经解决 ); 只对评分项进行拟合, 把非评分项忽略, 但 PF 会将用户没有评分的项也作为观测数据, 隐式地把矩阵中的零作为用户资源的一个限制 ; PF 只在用户观测矩阵中的已经观看过的数据中循环这样可以利用用户产品矩阵的稀疏性, 可以运用在大型的数据集上 32

33 Hierarchical Poisson Factorization The hierarchical Poisson factorization graph model: 33

34 Hierarchical Poisson Factorization XX ii,jj ~PPPPPPPPPPPPPP θθ ii TT φφ jj 泊松分布和其对数形式 : pp(xx ii,jj θθ ii TT, φφ jj ) = (θθ ii TT φφ jj ) XX ii,jj exp{ θθ ii TT φφ jj } XX ii,jj! 避免了其他方法所需要的复杂的子采样近似或随机优化的需要 34

35 Hierarchical Poisson Factorization 求后验!!! 模型中的隐变量是 θθ uk ββ ik zz uuuu 各个参数独立 35

36 Hierarchical Poisson Factorization 求后验!!! 36

37 Dynamic Poisson Factorization 37

38 Poisson Trust Factorization 38

39 Poisson Trust Factorization 39

40 Brief summary Poisson Factorization Basic Model SVD Probabilistic Matrix Factorization Hierarchical Poisson Factorization SVD PMF HPF PMF 是从概率生成过程的角度来解释 user 和 item 的 latent factor, SVD 是从优化目标出发, 如何确定 user 和 item 的 latent factor 可以使得 loss 最少两者解释的方式不一样, 但 PMF 的 MLE 与优化带正则项的 svd 的 loss function 是等价的 40

41 Brief summary SVD PMF HPF HPF 是为了解决 PMF 非负只对观测数据拟合和无法适应大规模数据的缺点提出的方法 Extension Model Dynamic Poisson Factorization Poisson Trust Factorization 41

42 Summary Poisson distribution: 基本的泊松分布和两个简单的小例子 Poisson process: 分析事件发生次数的影响因素, 构建基于时间的 Intensity function 建立非均匀有记忆性的泊松过程, 学术名次 Marked Point Process Poisson factorization: 从 SVD PMF HPF, 最后拓展了两个模型 42

43 References Hosseini S A, Alizadeh K, Khodadadi A, et al. Recurrent Poisson Factorization for Temporal Recommendation[J] Du N, Dai H, Trivedi R, et al. Recurrent Marked Temporal Point Processes: Embedding Event History to Vector[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016: Zarezade A, Jafarzadeh S, Rabiee H R. Spatio-Temporal Modeling of Check-ins in Location-Based Social Networks[J] Probability and Statistics (4th Edition) by Morris H. DeGroot. 随机过程及应用 Salakhutdinov R, Mnih A. Probabilistic Matrix Factorization[C]// International Conference on Neural Information Processing Systems. Curran Associates Inc. 2007: Gopalan P. Bayesian Nonparametric Poisson Factorization for Recommendation Systems[J]. 2014: Gopalan P, Hofman J M, Blei D M. Scalable recommendation with hierarchical Poisson factorization[c]// Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2015: Charlin L, Ranganath R, Mcinerney J, et al. Dynamic Poisson Factorization[C]// ACM Conference on Recommender Systems. ACM, 2015:

44 Q & A 44

勤學 * 卓越 * 快樂成長本校在老師群策群力共同討論下, 型塑了學校願景 : 勤學卓越快樂成長 ( 一 ) 勤學運用真的力量培養勤學, 以語文教為基礎紮根 ( 二 ) 卓越利用美的感

勤學 * 卓越 * 快樂成長本校在老師群策群力共同討論下, 型塑了學校願景 : 勤學卓越快樂成長 ( 一 ) 勤學運用真的力量培養勤學, 以語文教為基礎紮根 ( 二 ) 卓越利用美的感桃園市復旦國民小學 104 學年度學校課程計畫壹依據貳目的一教基本法第 13 條, 國民教法第 4 條二教部 92 公佈之國民中小學九年一貫課程綱要三桃園市政府推動國民中小學九年一貫課程實施計畫四桃園市政府 97.5.29 府教數字第