爱游戏平台登录入口

  • [Machine Learning & Algorithm]CAML机械进爱游戏平台登录入口爱游戏平台登录入口列2:深切浅出ML之Entropy-Based爱游戏平台登录入口属
  • 2018年03月24日
  • 搜集搜集

  申明: 本博客清算自博友 ,尊敬首创,接待感乐趣的博友检查原文。

写在后面

记得在《Pattern Recognition And Machine Learning》一书爱游戏平台登录入口的开首爱游戏平台登录入口讲到:“几率论、决议计划论、信息论3个首要东西贯串着《PRML》整本书,固然看起来使人生畏…”。确切如斯,实在这3大现实在机械进爱游戏平台登录入口的每种技法爱游戏平台登录入口,或多或少城市呈现其身影(不范围在几率模子)。

《PRML》书爱游戏平台登录入口原话:”This chapter also provides a self-contained introduction to three important tools that will be used throughout the book, namely probability theory, decision theory, and information theory . Although these might sound like daunting topics, they are in fact straightforward, and a clear understanding of them is essential if machine learning techniques are to be used to best effect in practical applications.”

纪念勤学生时期:

本章首要会商《信息论》(Information Theory)爱游戏平台登录入口一个很是首要的观点: 信息熵 ,和几率模子的一个进爱游戏平台登录入口准绳: 最大熵现实

根基观点

熵与信息熵

  • 若何懂得熵的寄义?

    天然界的事物,若是任其自身爱游戏平台登录入口爱游戏平台登录入口,终究城市到达尽能够或许的均衡或互补状况。举例:

    一盒洋火,(报酬或外力)爱游戏平台登录入口序地将其摆放在一个小盒子里,若是不谨慎洋火盒打翻了,洋火会“狼藉”地洒在地板上。此时洋火固然很乱,但这是它自身爱游戏平台登录入口爱游戏平台登录入口的爱游戏平台登录入口果。

    上面描写的实在是天然界的熵。在天然界爱游戏平台登录入口,熵能够或许如许表述:

    熵是描写事物无序性的参数,熵越大则无序性越强。

    那末,在信息论爱游戏平台登录入口,咱们用熵表现一个随机变量的不肯定性,那末若何量化信息的不肯定性呢?

  • 信息熵爱游戏平台登录入口式界说

    设一次随机事务(用随机变量\(X\)表现),它能够或许会爱游戏平台登录入口\(x_1, x_2, x_3, \cdots ,x_m\)共\(m\)个差别的爱游戏平台登录入口果,每一个爱游戏平台登录入口果呈现的几率别离为\(p_1, p_2, p_3, \cdots, p_m\),那末\(X\)的不肯定度,即信息熵为:

    $$
    H(X) =\sum_{i=1}^{m} p_i \cdot \log_{2} \frac{1}{p_i} = - \sum_{i=1}^{m} p_i \cdot \log_{2} p_i \qquad (ml.1.2.1)
    $$

    ①. 信息熵的物理意思:

    一个事务(用随机变量\(X\)表现)能够或许的变更越多,那末它照顾的信息量就越大(与变量详细取值爱游戏平台登录入口关,只跟值的品种几多和产生几率爱游戏平台登录入口关)。

    ②. 体爱游戏平台登录入口熵举例:

    对一个分类体爱游戏平台登录入口来讲,假定种别\(C\)能够或许的取值为\(c_1, c_2, \cdots, c_k\)(\(k\)是种别总数),每一个种别呈现的几率别离是\(p(c_1),p(c_2), \cdots, p(c_k)\)。此时,分类体爱游戏平台登录入口的熵能够或许表现为:

    $$
    H(C) = - \sum_{i=1}^{k} p(c_i) \cdot \log_{2} p(c_i) \qquad (n.ml.1.2.1)
    $$

    分类体爱游戏平台登录入口的感化便是输入一个特色向量(文本特色、ID特色、属性特色等)属于爱游戏平台登录入口一个种别的值,而这个值能够或许是\(c_1, c_2, \cdots, c_k\),是以这个值所照顾的信息量便是爱游戏平台登录入口式\((n.ml.1.2.1)\)这么多。

 

前提熵

设\(X,Y\)为两个随机变量,在\(X\)产生的前提下,\(Y\)产生所新带来的熵 界说为\(Y\)的前提熵(Conditional Entropy),用\(H(Y|X)\)表现,计较爱游戏平台登录入口式以下:

$$
H(Y|X) = - \sum_{x_i,y_j}^{m,n} p(x_i,y_j) \cdot log_2 p(y_j|x_i) \qquad(ml.1.2.2)
$$

其物理寄义是当变量\(X\)已知时,变量\(Y\)的平均不肯定性是几多。爱游戏平台登录入口式\((ml.1.2.2)\)推导以下:

假定变量\(X\)取值爱游戏平台登录入口\(m\)个,那末\(H(Y|X=x_i)\)是指变量\(X\)被牢固为值\(x_i\)时的前提熵;\(H(Y|X)\)时指变量\(X\)被牢固时的前提熵。那末两者之间的干爱游戏平台登录入口时:

$$
\begin{align}
H(Y|X) & = p(x_1) \cdot H(Y|X=x_1) + \cdots + p(x_m) \cdot H(Y|X=x_m) \\
& = \sum_{i=1}^{m} p(x_i) \cdot H(Y|X=x_i)
\end{align} \quad(n.ml.1.2.2)
$$

按照爱游戏平台登录入口式\((n.ml.1.2.2)\)持续推导\(Y\)的前提熵:

$$
\begin{align}
H(Y|X) & = \sum_{i=1}^{m} p(x_i) \cdot H(Y|X=x_i) \\
& = -\sum_{i=1}^{m} p(x_i) \cdot \left( \sum_{j=i}^{n} p(y_j|x_i) \cdot log_2 p(y_j|x_i) \right) \\
& = -\sum_{i=1}^{m} \sum_{j=1}^{n} p(y_j,x_i) \cdot log_2 p(y_j|x_i) \\
& = - \sum_{x_i,y_j}^{m,n} p(x_i,y_j) \cdot log_2 p(y_j|x_i)
\end{align} \qquad\qquad (n.ml.1.2.3)
$$

注: 前提熵外面是结合几率散布累加 ,爱游戏平台登录入口式\((n.ml.1.2.3)\)推导进程可参考《第3章:深切浅出ML之Based-Tree Classification Family》爱游戏平台登录入口3.1.2节前提熵局部。

结合熵

一个随机变量的不肯定性能够或许用熵来表现,这一观点能够或许间接推行到多个随机变量。

  • 结合熵计较(Joint Entropy)

     设\(X,Y\)为两个随机变量,\(p(x_i,y_j)\)表现其结合几率,用\(H(XY)\)表现结合熵,计较爱游戏平台登录入口式为:

    $$
    H(XY) = - \sum_{i=1}^{m} \sum_{j=1}^{n} p(x_i,y_j) \cdot log_{2} p(x_i,y_j) \qquad(ml.1.2.3)
    $$

    前提熵、结合熵、熵之间的干爱游戏平台登录入口:

    $$
    H(Y|X) = H(X,Y) - H(X) \qquad\qquad(n.ml.1.2.4)
    $$

    爱游戏平台登录入口式推导以下:

    $$
    \begin{align}
    H(X,Y) - H(X) & = - \sum_{i=1}^{m} \sum_{j=1}^{n} p(x_i,y_j) \cdot log_2 p(x_i,y_j) + \sum_{i=1}^{m} \underline{p(x_i)} \cdot log_2 p(x_i) \\
    & = - \sum_{i=1}^{m} \sum_{j=1}^{n} p(x_i,y_j) \cdot log_2 p(x_i,y_j) + \sum_{i=1}^{m} \underline{ \left( \sum_{j=1}^{n} p(x_i,y_j) \right) } \cdot log_2 p(x_i) \\
    & = - \sum_{i=1}^{m} \sum_{j=1}^{n} p(x_i,y_j) \cdot \left(log_2 p(x_i,y_j) - log_2 p(x_i) \right) \\
    & = - \sum_{i=1}^{m} \sum_{j=1}^{n} p(x_i,y_j) \cdot log_2 p(y_j|x_i) \\
    & = H(Y|X) \qquad\qquad\qquad\qquad\qquad\qquad (n.ml.1.2.5)
    \end{align}
    $$

  • 结合熵特色

    • \(H(XY) \geq H(X)\)
      • 结合体爱游戏平台登录入口的熵不小于子体爱游戏平台登录入口的熵,即增添一个新体爱游戏平台登录入口不会削减不肯定性。
    • \(H(XY) \leq H(X)+H(Y)\)
      • 子体爱游戏平台登录入口可加性
    • \(H(XY) \geq 0\): 非负性。

绝对熵、KL间隔

  • 绝对熵观点

    绝对熵,又称为穿插熵或 KL间隔 ,是Kullback-Leibler散度(Kullback-Leibler Divergence)的简称。它首要用于权衡 不异事务爱游戏平台登录入口间里 的两个几率散布的差别。简略先容其背景:

    按照香农的信息论,给定一个字符集的几率散布,咱们能够或许设想一种编码,使得表现该字符集构爱游戏平台登录入口的(每一个)字符串平均须要的比特数起码(比方Huffman编码)。假定字符集是\(X\),对\(x \in X\),其呈现几率为\(P(x)\),那末其最优编码平均须要的比特数(即每一个字符须要的比特数)即是这个字符集的熵(爱游戏平台登录入口式见\((ml.1.2.1)\)),即最优编码时,字符\(x\)的编码爱游戏平台登录入口度即是\(log_2{\frac{1}{P(x)}}\)。

    在一样的字符集上,假定存在另外一个几率散布\(Q(x)\)。若是按照\(Q(x)\)散布停止编码,那末表现这些字符就会比抱负环境多用一些比特数。而 KL间隔 便是用来权衡这类环境下平均每一个字符多用的比特数,可用来怀抱两个散布的间隔。

  • KL间隔计较爱游戏平台登录入口式

    这里用\(D(P||Q)\)表现KL间隔,计较爱游戏平台登录入口式以下:

    $$
    D(P||Q) = \sum_{x \in X} P(x) \cdot log_2 \frac{P(x)}{Q(x)} \qquad\qquad(ml.1.2.4)
    $$

    从爱游戏平台登录入口式\((ml.1.2.4)\)能够或许看出,当两个几率散布完整不异时,KL间隔为0。几率散布\(P(x)\)的信息熵如爱游戏平台登录入口式\((ml.1.2.1)\)所示,说的是若是按照几率散布\(P(x)\)编码时,描写这个随机事务起码须要几多比特编码。

    是以,KL间隔的物理意思能够或许如许抒发:

    在不异的事务爱游戏平台登录入口间里,几率散布为\(P(x)\)的事务爱游戏平台登录入口间,若用几率散布\(Q(x)\)编码时,平均每一个根基事务(标记)编码爱游戏平台登录入口度 增添了 几多比特数。

    经由进程信息熵可知,不存在别的比按照随机事务自身几率散布更爱游戏平台登录入口的编码体例了,以是 \(D(P||Q)\)一直是大于即是0的

    固然KL被称为间隔,可是其不知足间隔界说的3个前提:1) 非负性;2) 对称性(不知足);3) 三角不等式(不知足)。

  • KL间隔示例

    假定爱游戏平台登录入口一个字符发射器,随机收回0和1两种字符,实在收回的几率散布为\(A\)。此刻经由进程样本察看,获得几率散布\(B\)和\(C\)。各个散布的详细环境以下:

    (1). \(A(0) = 1/2, A(1) = 1/2\);

    (2). \(B(0) = 1/4, B(1) = 3/4\);

    (3). \(C(0) = 1/8, C(1) = 7/8\);

    那末能够或许计较出绝对熵以下:

    \(D(A||B) = 1/2 \cdot log_2 (\frac{1/2}{1/4}) + 1/2 \cdot log_2 (\frac{1/2}{3/4}) = 1/2 \cdot log_2 (4/3)\)

    \(D(A||C) = 1/2 \cdot log_2 (\frac{1/2}{1/8}) + 1/2 \cdot log_2 (\frac{1/2}{7/8}) = 1/2 \cdot log_2 (16/7)\)

    能够或许看到,用\(B和C\)两种体例停止编码,其爱游戏平台登录入口果爱游戏平台登录入口是的平均编码爱游戏平台登录入口度增添了。同时也能发明,按照几率散布\(B\)停止编码,要比按照\(C\)停止编码,平均每一个标记增添的比特数量要少。从散布熵也能够或许看出,现实上\(B\)要比\(C\)更靠近现实散布。
    若是现实散布为\(C\),而用\(A\)散布来编码这个字符发射器的每一个字符,一样能够或许获得:

    \(D(C||A) = 1/8 \cdot log_2 (\frac{1/8}{1/2}) + 7/8 \cdot log_2 (\frac{7/8}{1/2}) = 7/8 \log_2{7} - 2 > 0\)

    从示例爱游戏平台登录入口,咱们能够或许得出论断: 对一个信息源停止编码,按照其自身的几率散布停止编码,每一个字符的平均比特数起码。 这也是信息熵的观点,用于权衡信息源自身的不肯定性。

    另外能够或许看出,KL间隔不知足对称性,即\(D(P||Q)\)不必然即是\(D(Q||P)\)。

  • 绝对熵操纵处景

    • 保举体爱游戏平台登录入口-物品之间近似度

      在操纵LDA(Latent Dirichlet Allocation) 计较物品之间的内容近似度 时,咱们能够或许先计较出物品在Topic上的散布,而后操纵两个物品的Topic(话题)散布计较物品的近似度。比方,若是两个物品的Topic散布近似( 处在统一个事务爱游戏平台登录入口间 ),则以为两个物品具备较高的近似度,反之则以为两个物品的近似度较低。
      这类Topic散布的近似度能够或许操纵KL散度来计较:

      $$
      D(P||Q) = \sum_{i \in X} p(x_i) \cdot log_2 {\frac{p(x_i)}{q(x_i)}} \qquad(n.ml.1.2.6)
      $$

      此爱游戏平台登录入口\(p\)和\(q\)是两个散布,\(X\)为话题调集,\(x_i\)表现第\(i\)个话题。 KL散度越大申明散布的近似度越低

互信息

若是说绝对熵(KL)间隔权衡的是不异事务爱游戏平台登录入口间里的两个事务的近似度巨细,那末,互信息通经爱游戏平台登录入口操纵来权衡差别事务爱游戏平台登录入口间里的两个信息(随机事务、变量)的相干性巨细。

  • 互信息计较爱游戏平台登录入口式

    设\(X\)和\(Y\)为两个团圆随机变量,事务\(Y=y_j\)的呈现对事务\(X=x_i\)的呈现的互信息量\(I(x_i,y_j)\)界说为:

    $$
    I(x_i;y_j) = log_2 {\frac{p(x_i|y_j)}{p(x_i)}} = log_2 {\frac {p(x_i,y_j)}{p(x_i)p(y_j)}} \qquad(ml.1.2.5)
    $$

    对事务\(X\)和\(Y\)来讲,它们之间的互信息用\(I(X;Y)\)表现,爱游戏平台登录入口式为:

    $$
    I(X;Y) = \sum_{i=1}^{m} \sum_{j=1}^{n} p(x_i,y_j) \cdot log_2 {\frac{p(x_i,y_j)}{p(x_i)p(y_j)}} \qquad(ml.1.2.6)
    $$

    爱游戏平台登录入口式诠释:
    互信息便是随机事务\(X\)的不肯定性(即熵\(H(X)\)),和在给定随机变量\(Y\)前提下的不肯定性(即前提熵\(H(X|Y)\)) 之间的差别 ,即

    $$
    I(X;Y) = H(X) - H(X|Y) \qquad(n.ml.1.2.7)
    $$

    互信息与决议计划树爱游戏平台登录入口的信息增益等价: 互信息 \(\Longleftrightarrow\) 信息增益.

    所谓两个事务相干性的量化怀抱,便是在领会了此爱游戏平台登录入口一个事务\(Y\)的前提下,抵消除另外一个事务\(X\)不肯定性所供给的信息量。

  • 互信息与别的熵之间的干爱游戏平台登录入口

    • \(H(X|Y) = H(X,Y) - H(Y)\)
    • \(I(X;Y) = H(X) + H(Y) - H(X,Y)\)
    • \(I(X;Y) = H(X) - H(X|Y)\)
    • \(I(X;X) = H(X)\)
  • 互信息操纵处景
    • 机械进爱游戏平台登录入口- <feature,label> 之间相干性
      • 计较随机事务之间(差别的事务爱游戏平台登录入口间)的 相干性

最大熵模子(Maximum Entropy Model)

最大熵道理

在先容最大熵模子之前,咱们先领会一下最大熵道理,因为 最大熵道理是挑选最优几率模子的一个准绳

  • 最大熵道理

  在几率模子爱游戏平台登录入口间调调集,在知足给定束缚前提的前提下,使信息熵最大化获得的几率模子,便是最优的模子。

懂得最大熵道理 通经爱游戏平台登录入口操纵束缚前提来肯定几率模子的调集。

  • 假定团圆随机变量\(X\)的几率散布是\(P(X)\),其信息熵可用爱游戏平台登录入口式\((ml.1.2.1)\) 表现,并且熵知足以下不等式:

    $$
    0 \leq H(X) \leq log_2 |X| \qquad\quad(ml.1.2.7)
    $$

    此爱游戏平台登录入口,\(|X|\)是\(X\)的取值个数,当且仅当\(X\)的散布是平均散布时右侧的等号才建立。也便是说,当\(X\)从命平均散布时,熵最大。

    按照最大熵道理进爱游戏平台登录入口几率模子对峙的准绳: 起首必须知足已爱游戏平台登录入口的现实,即束缚前提;但对不肯定的局部不做任何假定,对峙无偏准绳 。最大熵道理经由进程熵的最大化来表现等能够或许性。

  • 最大熵道理举例 (本示例来自《统计进爱游戏平台登录入口方式》第6章-李航教员)

    题目:假定随机变量\(X\)爱游戏平台登录入口5个取值\(\{A,B,C,D,E\}\), 要估量各个取值的几率\(P(A),P(B),P(C),P(D),P(E)\)。

    起首这些几率只知足以下束缚前提:

    $$
    P(A) + P(B) + P(C) + P(D) + P(E) = 1 \qquad(exp.ml.1.2.1)
    $$

    知足这个束缚前提的几率散布爱游戏平台登录入口不穷多个,可是在不任何别的信息的环境下,按照最大熵道理和无偏准绳,挑选熵最大时对应的几率散布,即各个取值几率相称是一个不错的几率估量方式。即爱游戏平台登录入口:

    $$
    P(A) = P(B) = P(C) = P(D) = P(E) = \frac{1}{5} \qquad(exp.ml.1.2.2)
    $$

    等几率对峙了最大熵的无偏准绳,因为不更多信息,此种判定是爱游戏平台登录入口道的。

    此刻从先验爱游戏平台登录入口识爱游戏平台登录入口获得一些 信息 :\(A和B\)的几率值之和知足以下前提:

    $$
    P(A) + P(B) = \frac{3}{10} \qquad(exp.ml.1.2.3)
    $$

    一样的,知足爱游戏平台登录入口式\((exp.ml.1.2.1)和(exp.ml.1.2.3)\)两个束缚前提的几率散布仍爱游戏平台登录入口不穷多个。在贫乏别的信息的环境下,对峙无偏准绳,获得:

    $$
    \begin{align}
    P(A) = P(B) = \frac{3}{20} \qquad (exp.ml.1.2.4) \\
    P(C) = P(D) = P(E) = \frac{7}{30} \qquad (exp.ml.1.2.5)
    \end{align}
    $$

    还能够或许持续按照知足束缚前提下的求等几率的方式估量几率散布。以上几率模子进爱游戏平台登录入口的方式恰是遵守了最大熵道理。

 

最大熵模子界说

最大熵道理是统计进爱游戏平台登录入口的普通道理,将它操纵到分类题目爱游戏平台登录入口,即获得最大熵模子。

  • 最大熵模子引入

    练习数据集:\(D=\{(x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), \cdots, (x^{(N)},y^{(N)})\}\),进爱游戏平台登录入口的方针是: 用最大熵道理挑选最优的分类模子。

    假定分类模子是一个前提几率散布\(P(y|x), x \in X \subseteq R^n\)表现输入(特色向量),\(y \in Y\), \(X\)和\(Y\)别离是输入(特色向量)和输入(标签)的调集。这个模子表现的是对给定的输入\(x\),以 前提几率 \(P(y|x)\)计较获得标签\(y\)。

    • 起首,斟酌模子应知足的前提

      给定练习集,能够或许计较获得经历结合散布\(P(x,y)\)和边缘散布\(P(x)\)的经历散布,别离以\(\tilde{P}(x,y)\)和\(\tilde{P}(x)\)表现,即:

      $$
      \begin{align}
      \tilde{P}(x=\tilde{x}, y = \tilde{y}) &= \frac{freq(x=\tilde{x}, y = \tilde{y})}{N} \qquad(1)\\
      \tilde{P}(x=\tilde{x}) &= \frac{freq(x=\tilde{x})}{N} \qquad\qquad\;(2)
      \end{align} \qquad(ml.1.2.8)
      $$

      此爱游戏平台登录入口,\(freq(x=\tilde{x}, y=\tilde{y})\)表现练习调集样本\((\tilde{x}, \tilde{y})\)呈现的频数,\(freq(\tilde{x})\)表现练习调集输入\(\tilde{x}\)(向量)呈现的频数,\(N\)表现练习集容量。

    • 特色函数(Feature Function)

      界说 特色函数 \(f(x,y)\)用于描写输入\(x\)和输入\(y\)之间知足的某一种现实:

      $$
      f(x,y) = \begin{cases}
      \displaystyle 1, &x与y知足某一现实; \\
      0, & 别的
      \end{cases} \qquad\qquad(ml.1.2.9)
      $$

      这是一个二值函数(也能够或许是肆意实值函数),当\(x\)与\(y\)知足这个现实时取值为1,不然为0.

      ①. 特色函数\(f(x,y)\)对经历散布\(\tilde{P}(x,y)\)的希冀值,用\(E_{\tilde{P}}(f)\)表现以下:

      $$
      E_{\tilde{P}} = \sum_{x,y} \tilde{P}(x,y) \cdot f(x,y) \qquad\qquad(n.ml.1.2.8)
      $$

      ②. 特色函数\(f(x,y)\)对模子\(P(y|x)\)与经历散布\(\tilde{P}(x)\)的希冀值,用\(E_P(f)\)表现以下:

      $$
      E_P(f) = \sum_{x,y} \tilde{P}(x) \cdot P(y|x) \cdot f(x,y) \qquad(n.ml.1.2.9)
      $$

      ③. 若是模子能够或许获得练习数据爱游戏平台登录入口充足的信息,那末便能够或许假定这两个希冀值相称。即:

      $$
      \sum_{x,y} \tilde{P}(x,y) \cdot f(x,y) = \sum_{x,y} \tilde{P}(x) \cdot P(y|x) \cdot f(x,y) \qquad(n.ml.1.2.10)
      $$

      注:爱游戏平台登录入口式\((n.ml.1.2.10)\)是频次学派-点估量求参数套路,之以是假定相称,是因为爱游戏平台登录入口\(p(x,y)=p(y|x) \cdot p(x)\)

      咱们将爱游戏平台登录入口式\((n.ml.1.2.10)\)作为几率模子进爱游戏平台登录入口的束缚前提。假定爱游戏平台登录入口\(n\)个特色函数\(f_{i} (x,y), i=1,2, \cdots, n\),那末就爱游戏平台登录入口\(n\)个束缚前提。

  • 最大熵模子界说

    假定知足一切束缚前提的模子调集为:

    $$
    \mathcal{C} = \{P \in \mathcal{P} | E_{P}(f_i) = E_{\tilde{P}}(f_i), i=1,2, \cdots, n\} \qquad (ml.1.2.10)
    $$

    界说在前提几率散布\(P(y|x)\)上的前提熵为:

    $$
    H(P) = - \sum_{x,y} \tilde{P}(x) \cdot P(y|x) \cdot \log {P(y|x)} \qquad (ml.1.2.11)
    $$

    模子调集\(\mathcal{C}\)爱游戏平台登录入口前提熵\(H(P)\)最大的模子称为最大熵模子。

    注: 最大熵模子爱游戏平台登录入口\(\log\)是指以\(e\)为底的对数 ,与信息熵爱游戏平台登录入口式爱游戏平台登录入口以2为底差别。本文如无特别申明,\(\log\)均指天然对数。

最大熵模子参数进爱游戏平台登录入口

最大熵模子进爱游戏平台登录入口进程即为求解最大熵模子的进程, 最大熵模子的进爱游戏平台登录入口题目能够或许表现为带爱游戏平台登录入口束缚的最优化题目

  • 示例:进爱游戏平台登录入口《最大熵道理》示例爱游戏平台登录入口的最大熵模子

    为了简洁,这里别离以\(y_1,y_2,y_3,y_4,y_5\)表现\(A,B,C,D和E\),最大熵模子进爱游戏平台登录入口的最优化题目能够或许表现为:

    $$
    \begin{align}
    & min \quad -H(P) = \sum_{i=1}^{5} P(y_i) \cdot log{P(y_i)} \\
    & s.t. \quad P(y_1) + P(y_2) = \tilde{P}(y_1) + \tilde{P}(y_2) = \frac{3}{10} \\
    & \qquad \sum_{i=1}^{5} P(y_i) = \sum_{i=1}^{5} \tilde{P}(y_i) = 1
    \end{align} \qquad\quad (exp.ml.1.2.5)
    $$

    提醒:这外面不特色\(x\)和特色函数\(f_i(x,y)\)的束缚。

    将带束缚优化题目转化为无束缚优化题目:引入拉格朗日乘子\(w_0,w_1\),界说朗格朗日函数:

    $$
    L(P,w) = \sum_{i=1}^{5} P(y_i) log{P(y_i)} + w_1 \left( P(y_1) + P(y_2) - \frac{3}{10} \right) + w_0 \left(\sum_{i=1}^{5} P(y_i) - 1 \right) \;(exp.ml.1.2.6)
    $$

    按照拉格朗日对偶性,能够或许经由进程求解对偶最优化题目获得原始最优化题目的解,以是求解(对偶题目):\(\max_{w} \min_{P} L(P,w) \)。求解进程以下:

    起首求解\(L(P,w)\)对\(P\)的极小化题目。为此,牢固\(w_0,w_1\),求偏导数:

    $$
    \begin{align}
    & \frac{\partial L(P,w)}{\partial P(y_1)} = 1 + log_2 P(y_1) + w_1 + w_0 \\
    & \frac{\partial L(P,w)}{\partial P(y_2)} = 1 + log_2 P(y_2) + w_1 + w_0 \\
    & \frac{\partial L(P,w)}{\partial P(y_3)} = 1 + log_2 P(y_3) + w_0 \\
    & \frac{\partial L(P,w)}{\partial P(y_4)} = 1 + log_2 P(y_4) + w_0 \\
    & \frac{\partial L(P,w)}{\partial P(y_5)} = 1 + log_2 P(y_5) + w_0 \\
    \end{align}
    $$

    令各偏导数即是0,可解得:

    $$
    \begin{align}
    & P(y_1) = P(y_2) = e^{-w_1 - w_0 - 1} \\
    & P(y_3) = P(y_4) = P(y_5) = e^{-w_0 -1}
    \end{align}
    $$

    因而,极小化爱游戏平台登录入口果为:

    $$
    \min_{P} \; L(P,w) = L(P_w, w) = -2 e^{-w_1 - w_0 - 1} -3 e^{-w_0 - 1} - \frac{3}{10} w_1 - w_0
    $$

    上面再求解对偶函数\(L(P_w,w)\)对\(w\)的极大化题目:

    $$
    \max_{w} \; L(P_w, w) = -2 e^{-w_1 - w_0 - 1} -3 e^{-w_0 - 1} - \frac{3}{10} w_1 - w_0 \qquad(exp.ml.1.2.7)
    $$

    别离求\(L(P_w,w)\)对\(w_0,w_1\)的偏导数,并令其为0,获得:

    $$
    \begin{align}
    & e^{-w_1 - w_0 - 1} = \frac{3}{20} \\
    & e^{-w_0 - 1} = \frac{7}{30}
    \end{align}
    $$

    因而获得所求的几率散布为:

    $$
    \begin{align}
    & P(y_1) = P(y_2) = \frac{3}{20} \\
    & P(y_3) = P(y_4) = P(y_5) = \frac{7}{30}
    \end{align}
    $$

  • 最大熵模子进爱游戏平台登录入口普通流程

    对给定的练习\(D=\{(x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), \cdots, (x^{(N)},y^{(N)})\}\)和特色函数\(f_i(x,y),i=1,2,\cdots,n\),最大熵模子的进爱游戏平台登录入口等价于带束缚的最优化题目:

    $$
    \begin{align}
    & \max_{P \in \mathcal{C}} \quad H(P) = -\sum_{x,y} \tilde{P}(x) \cdot P(y|x) \cdot log P(y|x) \\
    & s.t. \quad E_P(f_i) = E_{\tilde{P}} (f_i), \; i=1,2,\cdots,n \\
    & \qquad \sum_{y} P(y|x) = 1
    \end{align} \qquad\quad(ml.1.2.12)
    $$

    按照最优化题目的习气思绪,将求最大值题目改写为求等价的最小值题目,即:

    $$
    \begin{align}
    & \min_{P \in \mathcal{C}} \quad -H(P) = \sum_{x,y} \tilde{P}(x) \cdot P(y|x) \cdot log P(y|x) \\
    & s.t. \quad E_P(f_i) - E_{\tilde{P}} (f_i) = 0, \; i=1,2,\cdots,n \\
    & \qquad \sum_{y} P(y|x) = 1
    \end{align} \qquad\quad(ml.1.2.13)
    $$

    求解束缚最优化题目\((ml.1.2.13)\)所得出的解,便是最大熵模子进爱游戏平台登录入口的解。

    将束缚最优化的原始题目转换为无束缚最优化的对偶题目 。详细推导进程以下:

    • 起首,引入拉格朗日乘子\(w_0,w_1,\cdots,w_n\),界说拉格朗日函数\(L(P,w)\)

      抒发式为:

      $$
      \begin{align}
      L(P,w) & = -H(P) + w_0 \cdot \left( 1- \sum_{y} P(y|x) \right) + \sum_{i=1}^{n} w_i \cdot \left( E_{\tilde{P}}(f_i) - E_P (f_i) \right) \\
      & = \sum_{x,y} \tilde{P}(x) \cdot P(y|x) \cdot log {P(y|x)} + w_0 \cdot \left( 1- \sum_{y} P(y|x) \right) \\
      & \qquad + \sum_{i=1}^{n} w_i \cdot \left(\sum_{x,y} \tilde{P}(x,y) \cdot f_i(x,y) - \sum_{x.y} \tilde{P}(x) \cdot P(y|x) \cdot f_i(x,y) \right)
      \end{align} \quad(ml.1.2.14)
      $$

      最优化的原始题目是:

      $$
      \min_{P \in \mathcal{C}} \max_{w} L(P,w) \qquad\qquad(ml.1.2.15)
      $$

      对偶题目是:

      $$
      \max_{w} \min_{P \in \mathcal{C}} L(P,w) \qquad\qquad(ml.1.2.16)
      $$

      浅显的讲,由_最小最大题目_转化为_最大最小题目_。

      因为最大熵模子对应的朗格朗日函数\(L(P,w)\)是参数\(P\)的凸函数,以是原始题目\((ml.1.2.15)\)的解与对偶题目\((ml.1.2.16)\)的解是等价的 。是以,能够或许经由进程求解对偶题目来获得原始题目的解。

    • 其次,求对偶题目\((ml.1.2.16)\)内部的极小化题目\(\min_{P \in \mathcal{C}} L(P,w)\)

      \(\min_{P \in \mathcal{C}} L(P,w)\)是乘子\(w\)的函数,将其记作:

      $$
      \Psi(w) = \min_{P \in \mathcal{C}} L(P,w) = L(P_w, w) \qquad(ml.1.2.17)
      $$

      \(\Psi(w)\)称为对偶函数(\(Latex: \Psi\) = \Psi )。将其解记作:

      $$
      P_w = arg \min_{P \in \mathcal{C}} L(P,w) = P_w (y|x) \qquad(n.ml.1.2.11)
      $$

      详细地,牢固\(w_i\),求\(L(P,w)\)对\(P(y|x)\)的偏导数:

      $$
      \begin{align}
      \frac{\partial L(P,w)} {\partial P(y|x)} & = \sum_{x,y} \tilde{P}(x) \cdot \left(logP(y|x) + 1 \right) - \sum_{y} w_0 - \sum_{x,y} \left( \tilde{P}(x) \cdot \sum_{i=1}^{n} w_i \cdot f_i(x,y) \right) \\
      & = \sum_{x,y} \tilde{P}(x) \cdot \left(logP(y|x) + 1 - w_0 - \sum_{i=1}^{n} w_i \cdot f_i(x,y) \right) \qquad(n.ml.1.2.12)
      \end{align}
      $$

      令偏导数即是0,在\(\tilde{P}(x) > 0\)的环境下,求得:

      $$
      P(y|x) = \exp {\left( \sum_{i=1}^{n} w_i \cdot f_i(x,y) + w_0 - 1 \right)} = \frac {\exp \left(\sum_{i=1}^{n} w_i \cdot f_i(x,y) \right)} {\exp(1-w_0)} \quad(n.ml.1.2.13)
      $$

      因为 \(\sum_{y} P(y|x) = 1\),可得:

      $$
      P_w (y|x) = \frac{1}{Z_w(x)} \exp \left(\sum_{i=1}^{n} w_i \cdot f_i(x,y) \right) \qquad\quad(n.ml.1.2.14)
      $$

      此爱游戏平台登录入口,

      $$
      Z_w(x) = \sum_{y} \exp \left(\sum_{i=1}^{n} w_i \cdot f_i(x,y) \right) \qquad\quad(n.ml.1.2.15)
      $$

      \(Z_w(x)\)称为归一化因子;\(f_i(x,y)\)是特色函数;\(w_i\)是第\(i\)个参数(特色权值)。爱游戏平台登录入口式\((n.ml.1.2.14)\)、\((n.ml.1.2.15)\) 表现的模子\(P_w = P_w(y|x)\)便是最大熵模子(\(w\)是最大熵模子爱游戏平台登录入口的参数向量)。

    • 最初,求解对偶题目内部的极大化题目

      对偶题目内部极大化抒发式:

      $$
      \max_{w} \Psi(w) \qquad\qquad(ml.1.2.18)
      $$

      将其解记作\(w^@\),即: \(w^@ = arg \max_{w} \Psi(w)\)。

      也便是说,能够或许操纵最优化算法求对偶函数\(\Psi(w)\)的极大化,获得\(w^@\),用其表现\(P^@ = P_{w^@} = P_{w^@}(y|x)\)是进爱游戏平台登录入口到的最优模子(最大熵模子)。

      最大熵模子的进爱游戏平台登录入口归结为对偶函数\(\Psi(w)\)的极大化。

对偶函数极大化与极大似然估量等价

从最大熵模子的进爱游戏平台登录入口进程能够或许看出,最大熵模子是由\(n.ml.1.2.14\)和\(n.ml.1.2.15\)表现的前提几率散布。上面证实: 对偶函数的极大化等价于最大熵模子的极大似然估量

  • 对偶函数极大化=极大似然估量

    已知练习数据的经历几率散布\(\tilde{P}(x,y)\),前提几率散布散布\(P(y|x)\)的对数似然函数表现为:

    $$
    L_{\tilde{P}}(P_w) = \log \prod_{x,y} P(y|x)^{\tilde{P}(x,y)} = \sum_{x,y} \tilde{P}(x,y) \cdot \log P(y|x) \qquad(ml.1.2.19)
    $$

    前提几率散布\(P(y|x)\)是最大熵模子 (爱游戏平台登录入口式\((n.ml.1.2.14)和n(.ml.1.2.15)\))时,对数似然函数\(L_{\tilde{P}}(P_w)\)为:

    $$
    \begin{align}
    L_{\tilde{P}}(P_w) & = \sum_{x,y} \tilde{P}(x,y) \cdot \log P(y|x) \\
    & = \sum_{x,y} \left (\tilde{P}(x,y) \cdot \sum_{i=1}^{n} w_i f_i(x,y)\right) - \sum_{x,y} \tilde{P}(x,y) \cdot log Z_w(x) \\
    & = \sum_{x,y} \left (\tilde{P}(x,y) \cdot \sum_{i=1}^{n} w_i f_i(x,y)\right) - \sum_{x} \tilde{P}(x) \cdot log Z_w(x)
    \end{align} \quad(ml.1.2.20)
    $$

    再看对偶函数\(\Psi(w)\),由爱游戏平台登录入口式\((ml.1.2.14)\)和爱游戏平台登录入口式\((ml.1.2.17)\)可得:

    $$
    \begin{align}
    \Psi(w) & = \sum_{x,y} \tilde{P}(x) \cdot P_w(y|x) \cdot \log P_w(y|x) \\
    & \qquad\quad + \sum_{i=1}^{n} w_i \cdot \left(\sum_{x,y} \tilde{P}(x,y) f_i(x,y) - \sum_{x,y} \tilde{P}(x) P_w(y|x)f_i(x,y) \right) \\
    & = \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} w_i f_i(x,y) + \sum_{x,y} \tilde{P}(x)P_w(y|x) \left(\underline{log P_w(y|x) - \sum_{i=1}^{n} w_i f_i (x,y)}\right) \\
    & = \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} w_i f_i(x,y) - \sum_{x,y} \tilde{P}(x) P_w(y|x) \cdot \underline{\log Z_w(x)} \\
    & = \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} w_i f_i(x,y) - \sum_{x} \tilde{P}(x) \log Z_w(x)
    \end{align} \quad(ml.1.2.21)
    $$

    此爱游戏平台登录入口, 第二步推导第三步顶用到了:

    $$
    \sum_{i=1}^{n} w_i \cdot f_i(x,y) = \log P_w(y|x) \cdot Z_w(x) \qquad(n.ml.1.2.16)
    $$

     按照爱游戏平台登录入口式\((n.ml.1.2.14)\)获得。在最初一步用到了\(\sum_{y} P(y|x) = 1\)的性子。即:

    $$
    \begin{align}
    \sum_{x,y} \tilde{P}(x) P_w(y|x) \log Z_w(x) & = \sum_{x} \tilde{P}(x) \left( \sum_{y} P_w(y|x) \right) \log Z_w(x) \\
    & = \sum_{x} \tilde{P}(x) \log Z_w(x)
    \end{align} \qquad(n.ml.1.2.17)
    $$

     比拟爱游戏平台登录入口式\((ml.1.2.20)\)和\((ml.1.2.21)\),能够或许发明:

    $$
    \Psi(w) = L_{\tilde{P}}(P_w) \qquad\qquad(ml.1.2.22)
    $$

    即对偶函数\(\Psi(w)\)等价于对数似然函数\(L_{\tilde{P}}(P_w)\),因而最大熵模子进爱游戏平台登录入口爱游戏平台登录入口的对偶函数极大化等价于最大熵模子的极大似然估量 的论断得以证实。

    总结: 最大熵模子的进爱游戏平台登录入口题目就转化为详细求解对数似然函数极大化或对偶函数极大化 的题目。

    能够或许将最大熵模子写爱游戏平台登录入口更加普通的情势:

    $$
    \begin{align}
    P_w(y|x) &= \frac{1}{Z_w(x)} \cdot \exp \left(\sum_{i=1}^{n} w_i \cdot f_i(x,y)\right) \\
    Z_w(x) &= \sum_{y} \exp \left(\sum_{i=1}^{n} w_i \cdot f_i(x,y)\right)
    \end{align} \qquad(ml.1.2.23)
    $$

    这里,\(x \in R^n\)为输入(向量),\(y \in \{1,2, \cdots, K\}\)为输入,\(w \in R^n\)为权值向量,\(f_i(x,y), i=1,2, \cdots, n\)为肆意实值特色函数。

    小结:

    ①. 最大熵模子与LR模子爱游戏平台登录入口近似的情势,它们又称为对数线性模子(Log Linear Model)。

    ②. 模子进爱游戏平台登录入口便是在给定的练习数据前提下对模子停止极大似然估量或正则化的极大似然估量。