《数学之美》读书笔记

爱被打了一巴掌 2023-08-17 16:15 139阅读 0赞

# 雅格布森通信模型：  #

通信六要素

*  发送者（信息源）
 *  信道
 *  接收者
 *  信息
 *  上下文
 *  编码

![938105-20190816000351996-1523743302.png][]

# HMM：隐马尔可夫模型 #

![938105-20190816000358080-2017206907.png][]

s是可见的 - 信源

o是不可见的（输出） - 信宿

通信就是要根据观测到的o恢复出s

对于翻译问题，汉译英：英语是s，汉语是o，根据s推断o

# TF-IDF  #

TF：词频

IDF：逆文本频率指数

IDF就是关键词的权重，越能表示一个文档主题的词，其权重越高

# 最大熵原则  #

以条件随机场为例，希望找到一个符合所有边缘分布的概率分布函数。

根据最大熵原则：希望找到一个符合所有边缘分布并使熵达到最大的模型，数学上可以证明，这个模型就是指数函数。

详见：[https://www.cnblogs.com/sddai/p/11346872.html][https_www.cnblogs.com_sddai_p_11346872.html]

最大熵模型、逻辑回归模型都是指数模型，训练方法类似：EM算法（通用迭代算法GIS、改进的迭代算法IIS）

**最大熵模型的数学推导（参考\[2\]）**

对于给定的训练数据集T=\{（x1，y1）,（x2，y2）,(x3，y3)...(xn，yn)\}以及特征函数fi(x,y),i=1,2,3...n，最大熵模型的学习等价于约束的最优化问题：

![938105-20190816000404591-880227461.png][]

引入朗格朗日算子W，定义拉格朗日函数L(P,w)

![938105-20190816000411421-2044562888.png][]

最优化的原始问题：

![938105-20190816000418240-793914659.png][]

对偶问题是：

![938105-20190816000423774-1112312632.png][]

由于L(P,W)是P的凸函数，原始问题的解与对偶问题的解是等价的。这里通过求对偶问题的解来求原始问题的解。

**第一步求解内部极小化问题**，记为：

![938105-20190816000430196-215798869.png][]

通过微分求导，得出P的解是：

![938105-20190816000438826-708360114.png][]

**第二步求外部的极大化问题：**

![938105-20190816000444848-517811897.png][]

最后的解记为：

![938105-20190816000450705-873518974.png][]

**第三步可以证明对偶函数的极大化等价于第一步求解出的P的极大似然估计**，所以将最大熵模型写成更一般的形式.

![938105-20190816000456891-909252169.png][]

*From <[https://www.cnblogs.com/sddai/p/11346872.html][https_www.cnblogs.com_sddai_p_11346872.html]>*

# 对EM算法的理解  #

类比K-Means算法：

![938105-20190816000502703-1366717157.png][]

![938105-20190816000508165-666017456.png][]

![938105-20190816000514017-1431512578.png][]

# 条件随机场  #

HMM和CRF的区别

![938105-20190816000520178-795842300.png][]

![938105-20190816000526146-1911913521.png][]

![938105-20190816000532077-942402730.png][]

上述模型参数众多，因此只能找出其中一些边缘分布，例如P(x\_1), P(x\_2, y\_3)等，再根据最大熵原则找到一个满足所有边缘分布并且使熵最大的模型。

这个模型就是指数函数

# 计算复杂度  #

P问题：

![938105-20190816000538176-1610525390.png][]

![938105-20190816000543977-1964853213.png][]

非多项式问题：

![938105-20190816000549831-1829153128.png][]

在非多项式问题中，有一类称之为非确定的多项式问题（NP问题）

P不等于NP

如果一个问题，能在***多项式复杂度***的时间内证实一个答案正确与否，则称为NP问题（无论当前是否有多项式复杂度算法）

NPC：NP-complete问题，所有NP问题都可以在多项式时间内规约到NPC问题，如果NPC问题找到了多项式算法，则NP=P

计算复杂度至少是NPC甚至是更大的问题，称之为NP-Hard问题

![938105-20190816000556807-1689868992.png][]

# 篱笆网络（lattice）和维特比算法  #

![938105-20190816000603772-1638641609.png][]

![938105-20190816000609869-181431173.png][]

![938105-20190816000615762-715921697.png][]

# SVD的物理含义  #

矩阵A：用来表示文章和词的关联性，A的一行对应一篇文章，A的一列对应一个词

A中元素为去加权词频（例如TF-IDF）

![938105-20190816000621667-267190935.png][]

![938105-20190816000627085-1658472129.png][]

![938105-20190816000635184-1342721959.png][]

![938105-20190816000641539-564565099.png][]

--------------------

2019年8月15日 夜

于南湖畔

转载于:https://www.cnblogs.com/sddai/p/11361357.html

[938105-20190816000351996-1523743302.png]: /images/20230810/1b47d18fe373415d90e4bedf07bd9ef1.png
[938105-20190816000358080-2017206907.png]: /images/20230810/f93287129ce548bba61088c2c95ccaea.png
[https_www.cnblogs.com_sddai_p_11346872.html]: https://www.cnblogs.com/sddai/p/11346872.html
[938105-20190816000404591-880227461.png]: /images/20230810/5e30b74ac22d439a9d7775c4b344d678.png
[938105-20190816000411421-2044562888.png]: /images/20230810/ec15b1d4e19b4f899b7d83c3f23c854c.png
[938105-20190816000418240-793914659.png]: /images/20230810/9813456c1243456b804e6b52e26893dd.png
[938105-20190816000423774-1112312632.png]: /images/20230810/e0a912ee665d4d8582385e5b7bd73687.png
[938105-20190816000430196-215798869.png]: /images/20230810/fd2eb48b9a6d456996eecc3009bc9a30.png
[938105-20190816000438826-708360114.png]: /images/20230810/c8d11e2cc2404ca38cd269288d5a38cf.png
[938105-20190816000444848-517811897.png]: /images/20230810/c87259c710ed4641b4262d58149529e3.png
[938105-20190816000450705-873518974.png]: /images/20230810/b1cc7ee79cd2442c85eaac72115955c0.png
[938105-20190816000456891-909252169.png]: /images/20230810/94f9fcf24bd64270baece594688723dd.png
[938105-20190816000502703-1366717157.png]: /images/20230810/2fba882f3c0a40c9a1506bfb43d78c26.png
[938105-20190816000508165-666017456.png]: /images/20230810/7492368c2cb04602926c3d75e6e68803.png
[938105-20190816000514017-1431512578.png]: /images/20230810/08507326f51d449ca28d845ce09ba517.png
[938105-20190816000520178-795842300.png]: /images/20230810/3b10e6f3cb2d443bba7414fa6cfabe45.png
[938105-20190816000526146-1911913521.png]: /images/20230810/708cb350d9fc4aef998727041a2a1a3c.png
[938105-20190816000532077-942402730.png]: /images/20230810/226394fd520943c885063ab1879b002c.png
[938105-20190816000538176-1610525390.png]: /images/20230810/fa7a9fa836644f8e81cbae6a2972573c.png
[938105-20190816000543977-1964853213.png]: /images/20230810/8698297bc4264ca0aea77129e8d80656.png
[938105-20190816000549831-1829153128.png]: /images/20230810/398f3fa515e94a93bf2804e0bc320331.png
[938105-20190816000556807-1689868992.png]: /images/20230810/b14a5df921b2451394b1ed3c19fe5210.png
[938105-20190816000603772-1638641609.png]: /images/20230810/417730420669432493a407cc6380790e.png
[938105-20190816000609869-181431173.png]: /images/20230810/451cca581b0c4a7aa71c2f7019a932e4.png
[938105-20190816000615762-715921697.png]: /images/20230810/46f14d9855f54847b64e5ea182ee9c46.png
[938105-20190816000621667-267190935.png]: /images/20230810/d3bd739d83c94e91807d4c8cf8c002e6.png
[938105-20190816000627085-1658472129.png]: /images/20230810/1379daab2a724e1bae99c430692d6ef4.png
[938105-20190816000635184-1342721959.png]: /images/20230810/e7bef0b59a9442b2859abff034434574.png
[938105-20190816000641539-564565099.png]: /images/20230810/be923cc5c0ca48a0aa2d3bf806f619e9.png