数学之美
2016-08-25 09:45:01 1 举报AI智能生成
数学之美
作者其他创作
大纲/内容
分词
隐马尔可夫模型
重要假设
马尔可夫假设
各个状态的分布只与其前一个状态有关
独立输出假设
输出仅与当前状态有关
三个主要问题
给定一个模型，计算某个特定输出序列的概率
前向算法
给定模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列。
维特比算法
给定足够量的观测数据，如何估计隐含马尔科夫模型参数
Baum-Welch算法
马尔可夫过程
符合马尔可夫假设的过程
状态
隐藏的状态
观察到的状态数目
可观察状态序列和隐藏状态序列是概率相关的
初始向量
状态转移矩阵
马尔可夫链
每个状态只与其直接相连的状态有关
扩展
贝叶斯网络
状态取决于前面有限个状态
拓扑结构相比马尔可夫链的链式结构更为灵活。
训练过程复杂：是NP完备问题
扩展
条件随机场
与贝叶斯不同是无向图
概率图模型：联合概率分布
信息的度量与作用
信息熵：信息的不确定性
互信息：两个随机事件"x相关性"的量化度量
消除歧义性
相对熵：衡量两个取值为正数的函数的相似性。
布尔代数与搜索引擎
布尔代数将逻辑与数学结合在一起，提供一个看待世界的新视角
布尔代数将对世界的认识从连续状态扩展到离散状态。
抓取网页时，判断网页内容是否与关键词相关
建立索引，用二进制序列表示关键字是否出现在每篇文献中。
图论与网络爬虫
网络爬虫的遍历：图论的搜索问题
网页搜索技术
网页搜索排名
PageRank算法
网页Y的排名应该来自于所有指向这个网页的其他网页....的权重之和
二维矩阵相乘迭代
网页与查询的相关性
TF-IDF
TF(Term Frequency)词频
IDF：实质是一个特定条件下关键词的概率分布的交叉熵
主要问题
下载：尽可能多的下载网页
索引：建立快速有效的索引
排序：根据相关性对网页进行公平准确的排序
有限自动机与动态规划
有限自动机 ：地址识别
动态规划
全局最优转化为局部最优问题
拼音输入法
香农第一定理：任何编码长度都不小于它的信息熵
拼音转汉字本质和GPS一致，都是寻找最短路径问题
文本分类
余弦定理
将关键词列表，用TF-IDF值填充。。将新闻内容根据表形成特征向量，放到空间中，以向量在空间中的夹角判断新闻的相似度
自底向上上的聚合
根据余弦相似性，把大于某个阈值的新闻合并成一个小类
将小类作为整体，计算特征向量，继续上一步。直至相似性小于某个值
矩阵
奇异值分解
将矩阵分解成为3个矩阵的成绩
大矩阵为m*n，m篇文章，n个词，每个元素表示加权词频即TF-IDF值
相比特征向量，他可以比较快的得到结果
信息指纹
以一个不太长的随机数来区别信息
关键算法
伪随机数产生器算法
梅森旋转算法
基于加密的伪随机数产生器
基本应用
判断集合是否相同//是否基本相同
音频视频反盗版
相似哈希
扩展
收缩
孪生：密码学
不可逆
密码学：大素数的乘除加减
最大熵模型
保留最大的不确定性，将风险降到最小
最大熵原理
对一个随机事件的概率分布进行预测时，预测应满足所有已知条件，对未知情况不做任何主观建设
训练方法
通用迭代算法（GIS）
1.假设0次迭代的初始模型为等概率的均匀分布
2.用第N次迭代的模型来估算每种信息特征在训练数据中的分布，若超出实际就将相应模型参数变小，否则将其变大
3.重复2直至收敛
改进迭代算法（IIS）
简化模型：线性插值
布隆过滤器
原理：两个完全随机的数字冲突的概率很小
本质是一个很长的二进制向量和一系列随机函数
可用于建立网址黑名单：相比散列表空间使用要少得多
缺点：有一定的误识别率
EM期望最大化算法
E过程
根据现有模型，计算各个观测输入到模型中的计算结果
M过程
重新计算模型参数，以最大化参数值
若模型为凸函数可保证最优，反之则可能为局部最优而不是全局最优
算法举例：Baum-welch GIS
人工神经网络
特殊的有向图
解决问题：多维空间进行模式分类
0 条评论
下一页
