理论介绍
==================

.. warning::

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

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

结构分类问题
+++++++++++++++++++++++++++

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


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

.. math::
    :label: argmax_z

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

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

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

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

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

.. math::

    \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。

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

.. math::
    :label: argmax_w

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


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

随机梯度下降算法
+++++++++++++++++++++++++++


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

感知器算法

平均感知器
----------------------------


Early-update
----------------------------


解码器
+++++++++++++++++++++++++++


类隐马尔可夫解码器
-----------------------------

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

.. math::

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

一般线性解码器
-----------------------------

.. math::

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

一般二叉树解码器
-----------------------------

.. math::

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

已实现的模型
+++++++++++++++++++++++++++

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


基于词的中文分词
-----------------------------


基于词图的分词词性标注
-----------------------------


移进-归约依存句法分析
-----------------------------