10种常见AI算法

感知机  二分类

二分类的线性分类模型，也是判别模型。
目的是求出把训练数据进行线性划分的分离超平面。
感知机是神经网络和支持向量机的基础。
学习策略：极小化损失函数。损失函数对应于误分类点到分离超平面的总距离。
基于随机梯度下降法对损失函数的最优化算法，有原始形式和对偶形式。

 

K近邻法 K-nearest neighbor, K-NN 多分类和回归

是一种分类和回归方法，有监督学习。在训练数据集中找到和新的输入实例最接近的K个实例，这k个实例的多数类别就是这个新实例的类别。
三要素：K的选择，距离度量，分类决策规则。
实现方法：kd树（二叉树）快速搜索K个最近邻的点。
K值选择：反映了对近似误差和估计误差的权衡。交叉验证选择最优的K值，K小，模型复杂，K大，模型简答。

 

朴素贝叶斯法 多分类 用于NLP

朴素贝叶斯法是基于贝叶斯定理和特征条件独立假设的分类方法。首先学习输入输出的联合概率分布，然后基于此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。
后验概率最大等价于0-1损失函数的期望风险最小化。
是典型的生成学习方法，由训练数据求出联合概率分布，再求出条件概率分布（后验概率）。
概率估计方法是：极大似然估计或者贝叶斯估计。
基本假设是条件独立性

 

决策树 decision tree  多分类，回归

是一种分类和回归算法。包括三个步骤：特征选择，决策树生成和决策树的修剪，常用算法：ID3，C4.5，CART

 

逻辑斯地回归和最大熵模型 多分类

本质就是给线性回归添加了对数函数
它的核心思想是，如果线性回归的结果输出是一个连续值，而值的范围是无法限定的，那我们有没有办法把这个结果值映射为可以帮助我们判断的结果呢。
而如果输出结果是 (0,1) 的一个概率值，这个问题就很清楚了。我们在数学上找了一圈，还真就找着这样一个简单的函数了，就是很神奇的sigmoid函数(如下)：
逻辑回归用于二分类和多分类
逻辑斯地分布是S型曲线
最大熵模型：熵最大的模型是最好的模型。
X服从均匀分布时候，熵最大
最大熵模型的学习等价于约束最优化问题。
对偶函数的极大化等价于最大熵模型的极大似然估计。
模型学习的最优化算法有：改进的迭代尺度法IIS，梯度下降法，牛顿法，或者拟牛顿法

 

支持向量机 二分类

线性可分支持向量机利用间隔最大化求最优分离超平面。
函数间隔表示分类预测的正确性和确信度
几何间隔是样本点到超平面的距离最近的点
线性支持向量机和硬间隔最大化
带有特异点的线性支持向量机和软间隔最大化
非线性支持向量机和核函数

 

提升方法boosting 二分类

分类问题中，改变训练样本权重，学习多个分类器，然后把多个分类器进行线性组合，提高分类性能。

 

EM算法及其推广 概率模型参数估计

EM算法用于含有隐变量的概率模型参数的极大似然估计的迭代算法。
分两步：E步，求期望Expectation，M步，求极大Maximization

 

隐马尔科夫模型 hidden Markov model,HMM 标注问题  生成模型 NLP

 
是用于标注问题的统计学模型，描述由隐藏的马尔科夫链随机生成观测序列的过程，属于生成模型。表示状态序列和观测序列的联合分布，状态序列是隐藏的。
标注问题是给定观测序列预测对应的标记序列。
概率计算：计算在模型下观测序列出现的概率。前向，后向算法是通过递推的计算前后向概率可以高效进行隐马尔科夫模型的概率计算。
学习问题：在模型下让观测序列概率最大，用极大似然估计法估计参数。极大后验概率估计。具体算法有：概率计算公式和EM算法。
预测问题：维特比算法应用动态规划高效的求解最优路径，即概率最大的状态序列。

 

条件随机场 CRF 标注问题 判别模型 NLP

conditional random field CRF是给定输入随机变量X条件下，输出随机变量Y的条件概率分布模型，其形式为参数化的对数线性模型。最大特点是假设输出变量之间的联合概率分布构成概率
无向图模型（马尔科夫随机场），属于判别模型。
线性链条件随机场表示为在观测序列条件下的标记序列的条件概率分布。由参数化的对数线性模型表示。
概率计算采用前后向算法
学习方法：（正则化的）极大似然估计法：即在给定训练数据下，通过极大化训练数据的对数似然函数来估计模型参数。具体的算法有：迭代尺度算法，梯度下降法，拟牛顿法。
应用：标注。维特比法：给定观测序列，求条件概率最大的标记序列的方法。