IM-PinYin

GitHub - RichardS0268/Input-Method_PinYin: Project 1 of the THU course Introduction to AI

Project 1 of the THU course Introduction to AI. Contribute to RichardS0268/Input-Method_PinYin development by creating an account on GitHub.

https://github.com/RichardS0268/Input-Method_PinYin

1. 问题建模

隐马尔可夫模型（Hidden Markov Model）的解码（Decoding）问题。

1.1 隐马尔可夫模型

标准的隐马尔可夫模型（二元）的定义为

其中为初始概率矩阵，为状态转移矩阵，为发射矩阵。

假设隐变量（随机变量）为 , 其实现值为

假设观测变量（随机变量）为, 其实现值为, 则

HMM的Decoding问题即为求解:

1.2 问题转换

根据本项目要解决的问题，对隐马尔可夫模型相关变量进行定义

1.2.1 隐变量，观测变量

将隐变量定义为与拼音相对应的汉字，观测变量为输入的全拼。

如输入

"qing hua da xue ji suan ji xi"

则观测变量集合为

["qing", "hua", "da", "xue", "ji", "suan", "ji", "xi"]

隐变量为（应为）

["清", "华", "大", "学", "计", "算", "机", "系"]

1.2.2 转移矩阵和发射矩阵

与原模型的定义稍有不同

将转移矩阵中定义为已知后一个汉字为的前提下，前一个汉字为的概率, 即

将发射矩阵中定义为观测到变量为的前提下，该观测变量对应的隐变量为的概率，即

1.2.3 假设

二元模型假设：每个字出现的概率仅和它前一个字及后一个字有关，即

观测假设，每个隐变量只与对应“时点”上的观测变量有关，即

1.2.4 递推公式

由以上定义和假设，在得到观测变量——输入的全拼序列时，求解目标为

设

由假设可知

则可得递推表达式：

通过该递推式实现解码（decoding）功能

记录，则即为模型输出

2. 具体实现

2.1 数据预处理

对于新浪新闻的语料库，先将txt文件合并，然后进行如下处理

将阿拉伯数字0-9替换成汉字 “零“, ... ,”九“

去除所有符号，将其替换成空格

以空格为分隔符，重新排列，形成“每句话”占一行的txt文件sentences_normal.txt

调用外部API（pypinyin: https://pypi.org/project/pypinyin/）生成sentences_normal.txt中的每句话对应的拼音，存到pinyin_normal.txt中

2.2 模型与方法

2.2.1 HMM

定义class HMM() 其该类包含主要方法如下


class HMM:
		...
    def cal_init_map(self): # 构建hanzi_map和duyin_map
				...

    def cal_transfer_matrix(self): # 计算转移矩阵
				...

    def cal_emit_matrix(self): # 计算发射矩阵
				...
    
    def train(self):
        print("Model Training ...")
        self.train_file = [hanzi_table, yuliao_data]
        self.cal_init_map()
        self.cal_transfer_matrix()
        self.cal_emit_matrix()
        print("Training Process Finished")

    def decoding(self, Input): # 维特比算法(动态规划)，进行decoding
				...

2.2.2 cal_init_map

功能：构建hanzi_map和duyin_map 两个字典，即将所有一二级汉字，以及所有合法的拼音与整数一一对应，方便之后的索引和操作。

2.2.3 cal_transfer_matrix

功能：计算转移矩阵

本项目采用字的二元模型，因此需要统计语料库（sentences_normal.txt）中每个汉字的前一个汉字的概率分布情况。统计结果使用DataFrame对象self.transfer 存储，每一行进行归一化（Normalization）对应一个汉字。self.transfer.iloc[i, j]即表示在语料库中，hanzi_map[i]前面一个汉字是hanzi_map[j]的概率

由于统计量巨大，因此采用多进程预处理的方式（见2.2.6），将统计好的转移矩阵以.csv文件存储，HMM对象在训练时直接读取该文件

2.2.4 cal_emit_matrix

功能：计算发射矩阵

统计语料库中，每个拼音所对应的汉字的概率分布情况。统计结果使用DataFrame对象self.emit_matrix 存储，每一行进行归一化（Normalization）对应一个拼音。

self.emit_matrix.iloc[i, j]即表示在语料库中，duyin_map[i]对应的汉字是hanzi_map[j]的概率

由于统计量巨大，因此采用多进程预处理的方式（见2.2.6），将统计好的转移矩阵以.csv文件存储，HMM对象在训练时直接读取该文件

2.2.5 decoding

根据1.2.4中的推导，结合2.2.3中获得的转移矩阵及2.2.4中获得的发射矩阵即可进行动态规划求解。

对于的设定：

其中表示在语料库中，汉字作为句首汉字出现的概率，是超参数

2.2.6 Multiple Process Data Handler (MPDH)

Linux 操作环境

计算转移矩阵和发射矩阵时，如果直接对语料库进行遍历十分耗时，可以通过将语料库拆分成若干个小语料库（数目等于进程数）加速这一过程。

通过修改template.txt 文件中的占位符(X_NUM_X)生成若干txt文件。创建脚本文件，写入nohup python XXX.txt >> XXX.log 2>&1 &命令，运行脚本。每条指令都会对应生成一个转移/发射矩阵，并存储到.csv文件中，待所有进程都完成后，读取并加合各.csv文件，进行归一化处理后存入.csv文件中。最后删除进程运行过程中产生的.log文件和合并前的.csv文件。

run_1.py和run_2.py集成了这些操作，直接在命令行中输入:

nohup python run_0.py >> run_0.log 2>&1 &

nohup python run_1.py >> run_1.log 2>&1 & 即可。

3. 实验结果

改变模型中的超参数（self.ir）, 将实验提供的input.txt作为输入，输出结果保存到my_output.txt中，对比my_output.txt与标准输出std_output.txt的到以下结果：

🎯

好的例子，坏的例子分别选自当次实验中整句准确率排名前五和后五的句子，第一项为模型判断结果，第二项为标准输出，第三项为该句准确率（正确字数/句长）

通过调整模型超参数（self.ir）, 分别检验模型的预测准确率，超参设定不同的模型之间的差异不大，这说明句首汉字的选择对整个搜索算法影响不大。

4. 总结收获

4.1 总结

这次实验是对第一章搜索问题的一次实践。许多问题在进行转化后都可以化归成求解最短路径的问题，如本题将概率的倒数作为路径长度，就是一个求解最短路径的问题。

本次实验主要用到隐马尔可夫模型，它属于概率图这个大范畴，同时它也有“序列”的概念。这次实验的内容——通过拼音输出汉字——与隐马尔可夫模型的解码问题（Decoding）十分契合。隐马尔夫模型的训练即是计算出三个矩阵，结合实验实际，对三个矩阵进行合适的定义，并通过已有的语料库进行计算。计算过程的统计量巨大，因此用多进程的方法进行加速。

4.2 改进方向

训练数据方面：本次实验使用的语料库是新闻材料，因此对不同的词汇预测准确率有所偏差。可以通过使用更大，词汇覆盖面更广的语料库来提高模型表现。

模型方面：本次实验采用了的基于字的二元模型，假设每个字只与其前后两个字存在关联。可以通过统计汉字三元组，使用基于字的三元模型来使模型更复杂，从而提升模型表现。

Direct Inference

IM.ipynb

drive.google.com