理论介绍

Warning

Chrome系列的浏览器可能无法直接正确显示本页公式。 这是因为用来显示公式用的js没有正确加载。 可点击地址栏右边盾牌状的图标以加载用来显示公式的js。

一个工具，可以抽象为一个函数 \(z=\text{Function}(x)\) ， 根据输入产生输出， 能够进行中文分词、词性标注、句法分析等任务的isan也不例外。

结构分类问题

Isan处理的是一类叫做结构分类的问题。 所谓“分类”， 就是说输出是离散的量， 所谓“结构”，就是说输出不是一个量，而是一组具有内部关联结构的量。 例如，一个函数的输出可以是一个词的序列如“厦门 的 鼓浪屿”，可被看作有三个离散量线性连接而成的结构。 语言中的句法树， 是另一种层次性的结构。

通常一个输入可以有多个候选的输出， 需要建立一个标准选择最好的那个， 因此定义一个评价函数 \(f(\mathbf{x};\mathbf{y})\) 给所有可能的输入输出对打分。 那么根据输入产生输出的过程就可以在数学上抽象为

(1)\[\mathbf{z}=\arg\max_{\mathbf{z}}{f(\mathbf{x};\mathbf{z})}\]

设计工具的问题就变成了如何找到合适的 \(f()\) 使得对于给定的输入能得到期望得到的输出。 有一种方法论（统计机器学习）的来法是这样的：

1. 为了描述所谓“期望的输出”， 我们直接构建一个数据集 \(\{(\mathbf{x}_i,\mathbf{y}_i)\}\) ，其中 \(\mathbf{x}_i\) 是输入样本， \(\mathbf{y}_i\) 是其“期望”的输出。
2. \(f()\) 不能漫无目的地寻找， 最好是人给出一个恰当的范围，然后让计算机在这个范围内参考上面的数据集找到一个最佳的函数。不妨将 \(f()\) 写为 \(f(\mathbf{x},\mathbf{w};\mathbf{y})\) ， 其中 \(\mathbf{w}\) 被称为模型的参数， 其不同的取值会得到不同的评价函数。 然后根据数据集自动地确定参数最佳的取值。

以上的路线图中， 就有一大一小两个搜索问题： 小的搜索问题是根据输入搜索最佳的输出； 大的搜索问题是根据已有的输入输出对组成的数据集， 搜索最佳的评价函数参数， 使得小的搜索问题能最好地完成。

继续，为了搜索最佳的参数， 同样需要评价参数的好坏， 因此再引入损失函数， 刻画在一定的参数下， 对数据集进行处理产生的损失

\[\text{loss}(\mathbf{w})=\sum_{i}{f(\mathbf{x}_i,\mathbf{w};\mathbf{z}_i)-f(\mathbf{x}_i,\mathbf{w};\mathbf{y}_i)}\]

Note

还可以设计其它的损失函数。

这个损失函数是非负的， 当小搜索问题的搜索结果与期望的结果相同时， 损失为0。

参数的搜索也就是以下最优化问题

(2)\[\mathbf{w}^*=\arg\min_{\mathbf{w}}{\text{loss}(\mathbf{w})}\]

这就是整个问题的大框架。 接下来的问题就是以上的两个含有 \(\arg\min\) 、 \(\arg\max\) 的问题如何求解。 在大的思路上这两个问题很类似， 都是为了确定某组量的取值而设计的优化问题。 但细看却很不一样， 搜索最优输出的问题 (1) ， 搜索空间是离散的， 并且是有约束的， 搜索最优参数的问题 (2) ， 搜索空间一般是整个欧式空间，连续的且无约束。 下面就分别介绍这两个问题的具体处理方法。

随机梯度下降算法

1. 得到一个训练样本 \((\mathbf{x}_t,\mathbf{y}_t)\)
2. 解码得到当前权重下的最优输出 \(\mathbf{z}_t=\arg\max_{\mathbf{z}}{f(\mathbf{x}_t,\mathbf{w};\mathbf{z})}\)
3. 如果 \(\mathbf{z}_t\not=\mathbf{y}_t\) 则 \(\mathbf{w}\leftarrow \mathbf{w}-\eta \left. \frac{\partial \text{loss}}{\partial \mathbf{w}} \right|_{\mathbf{w}}\)
4. 判断是否停止，如不停止跳到步骤1。

感知器算法

平均感知器

Early-update

解码器

类隐马尔可夫解码器

一阶解码器适合解决当目标函数可按以下形式分解的情况：

\[f(\mathbf{x};\mathbf{z})=\sum_{i}{g(\mathbf{x};z_i)}+\sum_{i}{h(z_i,z_{i+1})}\]

一般线性解码器

\[f(\mathbf{x};\mathbf{z})=\sum_{i}{h(\mathbf{x};z_i,z_{i+1})}\]

一般二叉树解码器

\[f(\mathbf{x};\mathbf{z})=\sum_{p}{h(\mathbf{x};z_{p},z_{l},z_{r})}+\sum_{l}{g(\mathbf{x};z_{l})}\]

已实现的模型

基于字标注的分词词性标注

基于词的中文分词

基于词图的分词词性标注

移进-归约依存句法分析