清华机器学习讲授课件.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 统计学习三要素\n",
    "* 策略\n",
    "* 损失函数：一次预测的好坏\n",
    "* 风险函数：平均意义下模型预测的好坏\n",
    "* 0-1损失函数\n",
    "* 平方损失函数\n",
    "* 绝对损失函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 求解最优模型就是求解最优化问题\n",
    "* 算法：\n",
    "* 如果最优化问题有显式的解析式，算法比较简单\n",
    "* 但通常解析式不存在，就需要数值计算的方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 模型评估与模型选择\n",
    "* 训练误差，训练数据集的平均损失\n",
    "* 测试误差，测试数据集的平均损失\n",
    "* 损失函数是0-1损失时：\n",
    "* 测试数据集的准确率："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二分类问题评价指标\n",
    "* 精确率\n",
    "* 召回率\n",
    "* F1值\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### KNN工作原理\n",
    "* 存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。\n",
    "* 输入没有标签的新数据后，将新数据的每个特征与样本中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。\n",
    "* 一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择K个中出现次数最多的分类，作为新数据的分类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K值的选择\n",
    "* 如果选择较小的K值\n",
    "   * 学习的近似误差会减小，但学习的估计误差会增大。\n",
    "   * 噪声敏感\n",
    "   * K值的减小就意味着整体模型变得复杂，容易发生过拟合。\n",
    "* 如何选择较大的值\n",
    "   * 减少学习的估计误差，但缺点学习的近似误差会增大。\n",
    "   * K值增大就意味着整体的模型变得简单。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 分类算法的流程\n",
    "* 对未知类别的数据集中的每个点依次执行以下操作\n",
    "  * 计算已知类别数据集众多点与当前点之间的距离\n",
    "  * 按照距离递增次序排序\n",
    "  * 选取与当前点距离最小的K个点\n",
    "  * 群定有Ｋ个点所在类别出现的频率\n",
    "　* 返回前K个点出现频率最高的类别作为当前点的预测分类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 决策树-解决分类问题的一般方法\n",
    "*　通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：\n",
    "*  模型构建（归纳）通过对训练集合的归纳，建立分类模型。\n",
    "*  预测应用（推论）根据建立的分类模型，对测试集合进行测试。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 决策树和归纳算法\n",
    "* 决策树技术发现数据模型和规则的核心是归纳算法。\n",
    "* 归纳是从特殊到一般的过程。\n",
    "* 归纳推理从若干个事实中表征出来的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。\n",
    "* 归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述，即从特殊事实到普遍性规律的结论。\n",
    "* 归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要是来源于归纳学习。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 决策树CLS算法\n",
    "* CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础。\n",
    "* CLS的思想\n",
    "* 从一棵空决策树开始，选择某一属性作为测试属性，该测试属性对应决策树中的决策节点。根据该属性的值不同，可将训练样本分成相应的子集：\n",
    "  * 如果该子集为空，或该子集的样本属于同一个类，则该子集为叶节点。\n",
    "  * 否则该子集对应于决策树的内部节点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 决策树ID3算法-流程\n",
    "* 1决定分类属性\n",
    "* 2对目前的数据表，建立一个节点N\n",
    "* 3如果数据表中没有其他属性可以考虑，则N就是树叶，在树叶上标出所属的类\n",
    "* 4如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别\n",
    "* 5否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性\n",
    "* 6节点属性选定后，对于该属性中的每个值：\n",
    "  * 从N生成一个分支，交将数据表中与该分支有关的数据形成分支节点的数据表，在表中删除节点属性那一栏如果分支数据表非空，则运用以上算法从该节点建立子树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 决策树IDE算法-基本思想\n",
    "* ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，变即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策 树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 逻辑斯谛\n",
    "### ——模型学习的最优化算法\n",
    "* 逻辑斯谛回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解，它是光滑的凸函数，因此多种最仳化的方法都适用。\n",
    "* 常用的方法有：\n",
    "   * 改进的迭代尺度法\n",
    "   * 梯度下降法\n",
    "   * 牛顿法\n",
    "   * 拟牛顿法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最优化方法\n",
    "* 梯度下降法\n",
    "* 最速下降法\n",
    "* 梯度下降法是一种迭代算法。选取适当的初值X，不断迭代，更新X的值，进行目标函数的最小化，直到收敛。由于梯度方向是使函数值下降最快的方向，在迭代的每一步，以负梯度方向更新X的值，从而达到养活值的目的。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 凸集\n",
    "* 一个点集（或区域），如果在连接其中任意两点X1，X2的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 支持向量和Ｍargins(边界)\n",
    "* 在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量.\n",
    "* 支持向量是使约束条件式等号成立的点,即 $$yi(w*xi + b) - 1 = 0 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 泛函基础\n",
    "* 度量空间\n",
    "* 赋范空间\n",
    "* 向量空间\n",
    "* 希尔伯特空间\n",
    "* 内积空间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 线窨和赋范空间\n",
    "* 线性空间:\n",
    "    * 空间中的任意两点可以做加法或与数相乘,运算的结果仍未该空间的点,并且该空间中的每个点可以定义长度,这个长度称为该点的范数,范数可以视为欧式空间中向量长度要领的推广.\n",
    "* 由于赋范空间既有代数结构,又有拓扑结果,因此其窨结构较度量空间要丰富得多,其在实际中的应用也更加重要."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 无监督学习\n",
    "* 无监督学习的基本想法是对给定数据（矩阵数据）进行某种“压缩”从而找到数据的潜在结构。损失最小的压缩得到的结果就是最本质的结构。\n",
    "* 考虑发掘数据的纵向结构，把相似的样本聚到同类，即对数据进行聚类。\n",
    "* 考虑发掘数据的横向结构，把高维空间的向量转换为低维空间的向量，即对数据进行降维。\n",
    "* 同时考虑发掘数据的纵向与横向结构，假设数据由含有隐式结构的概率模型生成得到，从数据中学习该概率模型。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 聚类\n",
    "* 降类（clustering）是将样本集合中相似的样本（实例）分配到桢的类，不相似的样本分配到不同的类。\n",
    "* 聚类时样本通常是欧氏空间中的向量，类别不是事先给定，而是从数据中自动发现，但类别的个数通常是事先给定的。样本之间的相似度或距离由应用决定。\n",
    "* 如果一个样本只能属于一个类，则称为硬聚类。\n",
    "* 如果一个样本可以属于多个类，则称为软聚类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 降维\n",
    "* 降维（dimensionality reduction）是将训练数据中的样本（实例）从高维空间转换到低维空间。\n",
    "* 假设样本原本存在于低维空间，或者近似地存在于低维空间，通过降维则可以更好地表示样本数据的结构，即更好地表示样本之间的关系。\n",
    "* 高维空间通常是高维的欧氏空间，而低维空间是低维的欧氏空间或者流形。\n",
    "* 从高维到低维的降维中，要保证样本中的信息损失最小。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 无监督学习三要素\n",
    "* 模型\n",
    " * 函数 z = g$$\\theta$$(x),条件概率分布P$$\\theta$$(z|x),或条件概率分布p$$\\theta(x|z)\n",
    "* 策略\n",
    " * 目标函数的优化\n",
    "* 算法\n",
    " * 迭代算法，通过迭代达到对目标函数的最优化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 聚类的模型步骤\n",
    "* 假设用K均值聚类，K=2，开始可以取任意两点作为两个类的中心\n",
    "* 依据样本与类中心的欧氏距离的大小将样本分配到两个类中。\n",
    "* 然后计算两个类中样本的均值，作为两个类的新的类中心。\n",
    "* 重复以上操作，直到两类不再改变\n",
    "* 最后得到聚类结果，A，B，C为一个类，D，E为另一个类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 降维\n",
    "* 由于数据是高维（多变量）数据，很难观察变量的样本区分能力，也很难观察样本之间的关系。\n",
    "* 对数据进行降维，如主万分分析，就可以更直观地分析以上问题。\n",
    "* 对样本集合进行降维（主成分分析），结果在新的二维实数空间中，有二维新的特征y1,y214个样本分布在不同位置。\n",
    "* 通过降维，可以发现样本可以分为三个类，二维新特征由原始特征定义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 话题分析\n",
    "* 话题分析是文本分析的一种技术。\n",
    "* 给定一个文本集合，话题分析旨在发现文本集合中每个文本的话题，而话题由单词的集合表示。\n",
    "* 注意，这里假设有足够数量的文本，如果只有一个文本或几个文本，是不能做话题分析的。\n",
    "* 话题分析可以形式化为概率模型估计问题，或降维问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 图分析\n",
    " * 图分析（graph analytics）的目的是发掘隐藏在图中的统计规律或潜在结构。\n",
    " *　PageRank算法是无监督学习方法，主要是发现有和图中的重要结点。\n",
    " * 给定一个有向图，定义在图上的随机游走即马尔可夫链。\n",
    " * 给随机游走者在有向图上随机跳转，到达一个结点后以等概率跳转到链接出去的结点，并不断持续这个过程。\n",
    " * PageRank算法就是求解该马尔可夫链的平稳分布的算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Page Rank\n",
    "* 一个节点上的平稳概率表示该结点的重要性，称为该结点的PageRank值。\n",
    "* 被指向的结点越多，该结点的PageRank值就越大。\n",
    "* 被指向的结点的PageRank值越大，该结点的PageRank值就越大。\n",
    "* PageRank值越大结点也就越重要。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 聚类方法\n",
    "* 聚类的核心概念是相似度（similarity）或距离（distance），有多种相似度或距离定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 层次聚类\n",
    "* 聚合聚类开始将每个样本各自分到一个类\n",
    "* 之后将相距最近的两类合并，建立一个新的类\n",
    "* 重复些操作直到满足停止条件\n",
    "* 得到层次化的类别\n",
    "* 分裂聚类开始将所有样本分到一个类\n",
    "* 之后将已有类中相距最远的样本分到两个新的类\n",
    "* 重复此操作直到满足停止条件\n",
    "* 得到层次化的类别"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 聚合聚类的具体过程\n",
    "* 对于给定的样本集合，开始将每个样本分到一个类\n",
    "* 然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并\n",
    "* 如此反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 聚合聚类\n",
    "* 聚合聚类需要预先确定下面三个要素\n",
    "* 距离或相似度\n",
    " * 闵可夫斯基距离\n",
    " * 马哈拉诺比斯距离\n",
    " * 相关系数\n",
    " * 夹角余弦\n",
    "* 合并规则\n",
    "  * 类间距离最小\n",
    "  * 类间距离可以是最短距离、最长距离、中心距离、平均距离\n",
    "* 停止条件\n",
    "  * 停止条件可以是类的个数达到闭值（极端情况类的个数是1）\n",
    "  * 类的直径超过阂值\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 奇异值分解基本定理\n",
    "* 确定V和$$\\sum$$\n",
    "* 首先构造n阶正交实矩V和mxn矩形对角实矩阵\n",
    "* 矩阵A是mxn实矩阵，则矩阵ATA是n阶实对称矩阵。\n",
    "* 因而ATA的特征值都是实数，并且存在一个n阶正交实矩阵v实现ATA的对角化，使得vt(ata)v=A成立\n",
    "* 其中A是n阶对角矩阵，其对角线元素由ATA的特征值组成。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 主成分分析\n",
    "* 主成分分析是一种常用的无监督学习方法\n",
    "* 这一方法利用正交变换把由线性相关变量表示的观测数据转换为少数几个由线性无关变量表示的数据，线性无关的变量称为主成分。\n",
    "* 主成分的个数通常小于原始变量的个数，所以主成分分析属于降维方法。\n",
    "* 主成分分析主要用于发现数据中的基本结构，即数据中变量之间的关系。\n",
    "###　基本想法1\n",
    "* 主成分分析中，首先对给定数据进行规范化，使得数据每一变量的平均值为0，方差为1.\n",
    "* 之后对数据进行正交变换，原来由线性相关变量表示的数据，通过正交变换成由叵干个线性无关的新变量表示的数据。\n",
    "* 新变量是可能的正交变换中变量的方差的和（信息保存）最大的，方差表示在新变量上信息的大小。\n",
    "* 可以用主分成近似地表示原始数据，发现数据的结构\n",
    "* 也可以把数据由少数主成分表示，对数据降维\n",
    "## 基本想法2\n",
    "* 数据集合中的样本由实数空间（正交坐标系）中的点表示，空间的一个坐标轴表示一个变量，规范化处理后得到的数据分布在原点附近。\n",
    "* 对原坐标系中的数据进行主成分分析等价于进行坐标系旋转变换，将数据投影到新坐标系的坐标轴上\n",
    "* 新坐标系的第一坐标系、第二坐标轴等分别表示第一主成分、第二主成分等\n",
    "* 数据在每一轴上的坐标值的平方表示相应变量的方差\n",
    "* 这个坐标系是在所有可能的新的坐标系中，坐标轴上的方差的和最大的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 潜在语义分析\n",
    "* 潜在语义分析是一种无监督学习方法，主要用于文本的话题分析\n",
    "* 通过矩阵分解发现文本与单词之间的基于话题的语义关系\n",
    "* 文本信息处理中，传统的方法以单词向量表示文本的语义内容，以单词向量空间的度量表示文本之间的语义相似度。\n",
    "* 潜在语义分析昆在解决这种方法不能准确表示语义的问题，试图从大量的文本数据中发现潜在的话题，以话题向量表示文本的语义内容，以话题向量窨的度量更地表示文本之间的语义相似度这也是话题分析的基本想法。\n",
    "* 潜在语义分析使用的是非概率的话题分析模型。\n",
    "* 具体地，将文本集合表示为单词-文本矩阵，对单词-文本矩阵进行奇异值分解，从而得到话题向量空间，以及主本在话题向量空间的表示。\n",
    "* 奇异值分解特点是分解的矩阵正交\n",
    "* 非负矩阵分解是另一种矩阵的因子分解方法，其特点是分解的矩阵非负\n",
    "* 非负矩阵分解也可以用于话题分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单词向量空间\n",
    "* 文本信息处理，比如文本信息检索、文本数据挖掘的一个核心问题是对文本的语义内容进行表示，并进行文本之间的语义相似度计算。\n",
    "* 最简单的方法是利用向量空间模型也就是单词向量空间模型。\n",
    "* 向量空间模型的基本想法是，给定一个文本，用一个向量表示该文本的“语义”\n",
    "* 向量的每一维对应一个单词，其数值为该单词在该文本中出来的频数或权值\n",
    "* 基本假设是文本中所有单词的出现情况表示了文本的语义内容\n",
    "* 文本集合中的每个文本都表示为一个向量，存在于一个向量空间\n",
    "* 向量空间的度量，如内积或标准化内积表示文本之间的语义相似度。\n",
    "* 直观上，一个单词在一个文本中出现的频数越高，这个单词在这个文本中的重要度就越高。\n",
    "* 一个单词在整个文本集合中出现的文本数越少，这个单词就越能表示其所在文本的特点，重要度就越高。\n",
    "* 一个单词在一个文本的TF-IDF是两种重要度的积，表示综合重要度\n",
    "### 单词向量空间模型\n",
    "* 模型简单\n",
    "* 计算效率高\n",
    "* 有局限性，内积相似度未必能够准确表达两个文本的语义相似度\n",
    " * 一词多义性\n",
    " * 多词一义性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 话题空间向量\n",
    "* 两个文本的语义相似度可以体现在两者的话题相似度上\n",
    "* 一个文本一般含有若干个话题。如果两个文本的话题相似，那么两者的语义应该也相似\n",
    "* 话题可以由若干个语义相关的单词表示，同义词可以表示同一个话题，而多义词可以表示不同的话题。\n",
    "* 这样，基于话题的模型就可以解决上述基于单词的模型存在的问题。\n",
    "* 设想定义一种话题向量空间模型（topic vector space model）\n",
    "* 给定一个样本，用话题空间的一个向量表示该文本，该向量的每一分量对应一个话题，其数值为该话题在该文本中出现的权值\n",
    "* 用两个向量的内积或标准化内积表示对应的两个文本的语义相似度\n",
    "* 注：单词向量空间模型与话题向量空间模型可以互为补充，现实中，两者可以同时使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 从单词向量空间到话题向量空间的线性变换\n",
    "* 直观上，潜在语义分析是将文本在单词向量空间的表示通过线性变换转换为在话题向量空间中的表示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 概率潜在语义分析\n",
    "* 概率潜在语义分析，是一种利用概率生成模型对文本集合进行话题分析的无监督学习方法。\n",
    "* 模型的最大特点是用隐变量表示话题；整个模型表示文本生成话题，话题生成单词，从而得到单词一文本共现数据的过程。\n",
    "* 假设每个文本由一个话题分布决定，每个话题由一个单词分布决定。\n",
    "* 概率潜在语义分析受潜在语义分析的启发，前者基于概率模型，后者基于非概率模型\n",
    "### 基本想法1\n",
    "* 给定一个文本集合，每个文本讨论若干个话题，每个话题由若干个单词表示\n",
    "* 对文本集合进行概率潜在语义分析，就能够发现每个文本的话题，以及每个话题的单词。\n",
    "* 话题是不能从数据中直接观察到的，是潜在的。\n",
    "### 基本想法2\n",
    "* 文本集合转换为文本-单词共现数据，具体表现为单词-文本矩阵\n",
    "* 文本数据基于如下的概率模型产生（共现模型）：\n",
    "* 首先有话题的概率分布，然后有话题给定条件下文本的条件概率分布，以及话题给定条件下单词的条件概率分布。\n",
    "* 概率潜在语义分析就是发现由隐变量表示的话题，即潜在语义。\n",
    "* 直观上，语义相近的单词、语义相近的文本会被聚到相同的“软的类别中”，而话题所表示的就是这样的软的类别。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 可尔可夫链蒙特卡罗法\n",
    "* 蒙特卡罗法，也称为统计模拟方法，是通过从概率模型的随机抽样进行近似数值计算的方法。\n",
    "* 马尔可夫链蒙特卡罗法，则是以马尔可夫链为概率模型的蒙特卡罗法。\n",
    "* 马尔可夫链蒙特卡罗法构建一个马尔可夫链，使其平稳分布就是要进行抽样的分布，首先基于该马尔可夫链进行随机游走，产生样本的序列，之后使用该平稳分布的样本进行近似数值计算。\n",
    "* Metropolis-Hastings算法是最基本的马尔可夫链蒙特卡罗法\n",
    "* 吉布斯抽样是更简单、使用更广泛的马尔可夫链蒙特卡罗法\n",
    "* 马尔可夫链蒙特卡罗法被应用于概率分布的估计、定积分的近似计算、最优化问题的近似求解等问题，特别是被应用于统计学习中概率模型的学习与推理，是重要的统计学习计算方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 可尔可夫链\n",
    "* 基本定义：马尔可夫链的直观解释是“未来只依赖于现在”（假设现在已知），而与过去无关"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 转移概率矩阵和状态分布\n",
    "* 有限离散状态的马尔可夫链可以由有向图表示\n",
    "* 结点表示状态，边表示状态之间的转移，边上的数值表示转移概率\n",
    "* 从一个初始状态出发，根据有向边上定义的概率在状态之间随机跳转或随机转移，就可以产生状态的序列。\n",
    "* 马尔可夫链实际上是刻画随时间在状态之间转移的模型，假设未来的转移状态只依赖于现在的状态，而与过去的状态无关。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 马尔可夫链的性质\n",
    "* 遍历定理的直观解释：\n",
    "* 满足相应条件的马尔可夫链，当时间趋于无穷时，马尔可夫链的状态分布趋近于平稳分布，随机变量的函数的样本均值以概率1收敛于该函数的数学期望。\n",
    "* 样本均值可以认为是时间均值，而数学期望是空间均值。遍历定理实际表述了遍历性的含义：当时间趋于无穷时，时间均值等于空间均值。\n",
    "* 遍历定理的三个条件：不可约、非周期、正常返，保证了当时间趋于无穷时达到任意一个状态的概率不为0.\n",
    "* 理论上并不知道经过多少次迭代，可尔可夫链的状态分布才能接近于平稳分布。\n",
    "* 在实际应用遍历定理时，取一个足够大的整数m，经过m次迭代之后认为状态分布就是平稳分布。\n",
    "* 这时计算从第m+1次迭代到第n次迭代的均值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 潜在锹利克雷分配模型——基本想法\n",
    "* 潜在狄利克分配是文本集合的生成概率模型\n",
    "* 模型假设话题由单词的多项分布表示，文本由话题的多项分布表示，单词分布和话题分布的先验分布都是狄利克雷分布。\n",
    "* 文本内容的不同是由于它们的话题分布不同。\n",
    "* LDA模型是概率图模型，其特点是以狄利克雷分布为多项分布的先验分布。\n",
    "* 学习就是给定文本集合，通过后验概率分布的估计，推断模型的所有参数\n",
    "* 利用LDA进行话题分析，就是对给定文本集合，学习到每个文本的话题分布，以及每个话题的单词分布。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PageRank算法\n",
    "* 假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程\n",
    "* 假设浏览者在每个网页依照连接出去的超以等概率跳转到一下网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链。\n",
    "### 基本想法\n",
    "* 假设有一个浏览者，在网上随机游走\n",
    "* 如果浏览者在网页A，则下一步以1/3的概率转移到网页B，C和D\n",
    "* 如果浏览者在网页B，则下一步以1/2的概率转移到网页A和D\n",
    "* 如果浏览者在网页C，则下一步以概率1转移到网页A\n",
    "* 如果浏览者在网页D，则下一步以1/2的概率转移到网页B和C\n",
    "* 直观上，一个网页，如果指向该网页的超链接越多，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要。\n",
    "* 一个网页，如果指向该网页的PageRank值越高，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要。\n",
    "* PageRank值依赖于网络的拓扑结构，一旦网络的拓扑（连接关系）确定，PageRank值就确定"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PageRank的定义\n",
    "* 不可约且非周期的有限状态马尔可夫链，有唯一平稳分布存在，并且当时间趋于无穷时状态分布收敛于唯一的平稳分布。\n",
    "* 根据马尔可夫链平稳分布定理，强连通且非周期的有向图上定义的随机游走模型，在图上的随机游走当时间趋于无穷时状态分布收敛于唯一的平稳分布。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}