本文由 「AI前線」原創(chuàng)，原文鏈接：?http://dwz.cn/7nBdQV

本文經(jīng)阿凡題研究院授權(quán)發(fā)布

作者｜王磊，張東祥，高聯(lián)麗，宋井寬，郭龍，申恒濤

AI 前線導(dǎo)讀：?”增強(qiáng)學(xué)習(xí)和人類(lèi)學(xué)習(xí)的機(jī)制非常相近，DeepMind 已經(jīng)將增強(qiáng)學(xué)習(xí)應(yīng)用于 AlphaGo 以及 Atari 游戲等場(chǎng)景當(dāng)中。作為智能教育領(lǐng)域的引領(lǐng)者，阿凡題研究院首次提出了一種基于 DQN（Deep Q-Network）的算術(shù)應(yīng)用題自動(dòng)求解器，能夠?qū)?yīng)用題的解題過(guò)程轉(zhuǎn)化成馬爾科夫決策過(guò)程，并利用 BP 神經(jīng)網(wǎng)絡(luò)良好的泛化能力，存儲(chǔ)和逼近增強(qiáng)學(xué)習(xí)中狀態(tài) - 動(dòng)作對(duì)的 Q 值。實(shí)驗(yàn)表明該算法在標(biāo)準(zhǔn)測(cè)試集的表現(xiàn)優(yōu)異，將平均準(zhǔn)確率提升了將近 15%。”

研究背景

自動(dòng)求解數(shù)學(xué)應(yīng)用題（MWP）的研究歷史可追溯到 20 世紀(jì) 60 年代，并且最近幾年繼續(xù)吸引著研究者的關(guān)注。自動(dòng)求解應(yīng)用數(shù)學(xué)題首先將人類(lèi)可讀懂的句子映射成機(jī)器可理解的邏輯形式，然后進(jìn)行推理。該過(guò)程不能簡(jiǎn)單地通過(guò)模式匹配或端對(duì)端分類(lèi)技術(shù)解決，因此，設(shè)計(jì)具有語(yǔ)義理解和推理能力的應(yīng)用數(shù)學(xué)題自動(dòng)求解器已成為通向通用人工智能之路中不可缺少的一步。

對(duì)于數(shù)學(xué)應(yīng)用題求解器來(lái)說(shuō)，給定一個(gè)數(shù)學(xué)應(yīng)用題文本，不能簡(jiǎn)單的通過(guò)如文本問(wèn)答的方式端到端的來(lái)訓(xùn)練，從而直接得到求解答案，而需要通過(guò)文本的處理和數(shù)字的推理，得到其求解表達(dá)式，從而計(jì)算得到答案。因此，該任務(wù)不僅僅涉及到對(duì)文本的深入理解，還需要求解器具有很強(qiáng)的邏輯推理能力，這也是自然語(yǔ)言理解研究中的難點(diǎn)和重點(diǎn)。

近幾年，研究者們從不同的角度設(shè)計(jì)算法，編寫(xiě)求解系統(tǒng)，來(lái)嘗試自動(dòng)求解數(shù)學(xué)應(yīng)用題，主要包括基于模板的方法，基于統(tǒng)計(jì)的方法，基于表達(dá)式樹(shù)的方法，以及基于深度學(xué)習(xí)生成模型的方法。目前，求解數(shù)學(xué)應(yīng)用題相關(guān)領(lǐng)域，面臨訓(xùn)練數(shù)據(jù)集還不夠多，求解算法魯棒性不強(qiáng)，求解效率不高，求解效果不好等多種問(wèn)題。由于數(shù)學(xué)題本身需要自然語(yǔ)言有足夠的理解，對(duì)數(shù)字，語(yǔ)義，常識(shí)有極強(qiáng)的推理能力，然而大部分求解方法又受到人工干預(yù)較多，通用性不強(qiáng)，并且隨著數(shù)據(jù)復(fù)雜度的增加，大部分算法求解效果急劇下降，因此設(shè)計(jì)一個(gè)求解效率和效果上均有不錯(cuò)表現(xiàn)的自動(dòng)求解器，是既困難又非常重要的。

相關(guān)工作

算術(shù)應(yīng)用題求解器：

作為早期的嘗試，基于動(dòng)詞分類(lèi)，狀態(tài)轉(zhuǎn)移推理的方法，只能解決加減問(wèn)題。為了提高求解能力，基于標(biāo)簽的方法，設(shè)計(jì)了大量映射規(guī)則，把變量，數(shù)字映射成邏輯表達(dá)式，從而進(jìn)行推理。由于人工干預(yù)過(guò)多，其擴(kuò)展困難。

基于表達(dá)式樹(shù)的方法，嘗試識(shí)別相關(guān)數(shù)字，并對(duì)數(shù)字對(duì)之間進(jìn)行運(yùn)算符的分類(lèi)，自底向上構(gòu)建可以求解的表達(dá)式樹(shù)。除此之外，會(huì)考慮一些比率單位等等的限制，來(lái)進(jìn)一步保證構(gòu)建的表達(dá)式的正確性?；诘仁綐?shù)的方法，采用了一個(gè)更暴力的方法，通過(guò)整數(shù)線性規(guī)劃，枚舉所有可能的等式樹(shù)?；跇?shù)的方法，都面臨著隨著數(shù)字的個(gè)數(shù)的增減，求解空間呈指數(shù)性增加。

方程組應(yīng)用題求解器：

對(duì)于方程組應(yīng)用題的求解，目前主要是基于模板的方法。該需要將文本分類(lèi)為預(yù)定義的方程組模板，通過(guò)人工特征來(lái)推斷未知插槽的排列組合，把識(shí)別出來(lái)的數(shù)字和相關(guān)的名詞單元在插槽中進(jìn)行填充?；谀０宓姆椒▽?duì)數(shù)據(jù)的依賴(lài)性較高，當(dāng)同一模板對(duì)應(yīng)的題目數(shù)量減少，或者模板的復(fù)雜性增加時(shí)，這種方法的性能將急劇下降。

本文的主要貢獻(xiàn)如下：

第一個(gè)嘗試使用深度增強(qiáng)學(xué)習(xí)來(lái)設(shè)計(jì)一個(gè)通用的數(shù)學(xué)應(yīng)用題自動(dòng)求解框架

針對(duì)應(yīng)用題場(chǎng)景，設(shè)計(jì)了深度 Q 網(wǎng)絡(luò)相應(yīng)的狀態(tài)，動(dòng)作，獎(jiǎng)勵(lì)函數(shù)，和網(wǎng)絡(luò)結(jié)構(gòu)。

在主要的算術(shù)應(yīng)用題數(shù)據(jù)集上驗(yàn)證了本文提出的方法，在求解效率和求解效果上都取得了較好的結(jié)果。

方案介紹

基于深度 Q 網(wǎng)絡(luò)的數(shù)學(xué)應(yīng)用題求解器

本文提出的框架如上圖所示。給出一個(gè)數(shù)學(xué)應(yīng)用題，首先采用數(shù)字模式提取用于構(gòu)建表達(dá)式樹(shù)的相關(guān)數(shù)字，然后根據(jù)重排序制定的規(guī)則，對(duì)提取出來(lái)的相關(guān)數(shù)字進(jìn)行順序調(diào)整，比如對(duì)于“3+4*5”, 我們希望優(yōu)先計(jì)算4*5，這里的數(shù)字 5，對(duì)應(yīng)的文本段是“5 元每小時(shí)”，顯然這里的數(shù)字“5”的單位是“元 / 小時(shí)”，當(dāng)數(shù)字“4”的單位是“小時(shí)”，數(shù)字“3”的單位是“元”，遇到這種情況，調(diào)整 4 和 5 放到數(shù)字序列的最前面，隨后，用已排好序的數(shù)字序列自底向上的構(gòu)建表達(dá)式樹(shù)。

首先，根據(jù)數(shù)字“4”和數(shù)字“5”各自的信息，相互之間的信息，以及與問(wèn)題的關(guān)系，提取相應(yīng)的特征作為增強(qiáng)學(xué)習(xí)組件中的狀態(tài)。然后，將此特征向量作為深度 Q 網(wǎng)絡(luò)中前向神經(jīng)網(wǎng)絡(luò)的輸入，得到“+”，“-”，反向“-”，“*”，“/“，反向”/“六種動(dòng)作的 Q 值，根據(jù) epsilon-greedy 選擇合適的操作符作為當(dāng)前的動(dòng)作，數(shù)字”4“和”5“根據(jù)當(dāng)前采取的動(dòng)作，開(kāi)始構(gòu)建表達(dá)式樹(shù)。下一步，再根據(jù)數(shù)字”4“和數(shù)字”3“，或者數(shù)字”5“和數(shù)字“3”，重復(fù)上一步的過(guò)程，把運(yùn)算符數(shù)字的最小公共元祖來(lái)構(gòu)建表達(dá)式樹(shù)。直到?jīng)]有多余相關(guān)數(shù)字，建樹(shù)結(jié)束。隨后將詳細(xì)介紹深度 Q 網(wǎng)絡(luò)的各個(gè)部件的設(shè)計(jì)方式。

狀態(tài)：對(duì)于當(dāng)前的數(shù)字對(duì)，根據(jù)數(shù)字模式，提取單個(gè)數(shù)字，數(shù)字對(duì)之間，問(wèn)題相關(guān)的三類(lèi)特征，以及這兩個(gè)數(shù)字是否已經(jīng)參與表達(dá)式樹(shù)的構(gòu)建，作為當(dāng)前的狀態(tài)。其中，單個(gè)數(shù)字，數(shù)字對(duì)，問(wèn)題相關(guān)這三類(lèi)特征，有助于網(wǎng)絡(luò)選擇正確的運(yùn)算符作為當(dāng)前的動(dòng)作；數(shù)字是否參與已經(jīng)參與表達(dá)式樹(shù)的構(gòu)建，暗示著當(dāng)前數(shù)字對(duì)在當(dāng)前表達(dá)式樹(shù)所處的層次位置。

動(dòng)作：因?yàn)楸疚奶幚淼氖呛?jiǎn)單的算術(shù)應(yīng)用題，所以只考慮，加減乘除四則運(yùn)算。在構(gòu)建樹(shù)的過(guò)程中，對(duì)于加法和乘法，兩個(gè)數(shù)字之間不同的數(shù)字順序?qū)⒉挥绊懹?jì)算結(jié)果，但是減法和除法不同的順序?qū)?dǎo)致不同的結(jié)果。由于，我們實(shí)現(xiàn)確定好數(shù)字的順序，所以添加反向減法和反向除法這兩個(gè)操作是非常有必要的。因此，總共加減乘除，反向減法和除法 6 種運(yùn)算符作為深度 Q 網(wǎng)絡(luò)需要學(xué)習(xí)的動(dòng)作。

獎(jiǎng)勵(lì)函數(shù)：在訓(xùn)練階段，深度 Q 網(wǎng)絡(luò)根據(jù)當(dāng)前兩個(gè)數(shù)字，選擇正確的動(dòng)作，得到正確的運(yùn)算符，環(huán)境就反饋一個(gè)正值作為獎(jiǎng)勵(lì)，否則反饋一個(gè)負(fù)值作為懲罰。

參數(shù)學(xué)習(xí)：本文采用了一個(gè)兩層的前向神經(jīng)網(wǎng)絡(luò)用于深度 Q 網(wǎng)絡(luò)計(jì)算期望的 Q 值。網(wǎng)絡(luò)的參數(shù)θ將根據(jù)環(huán)境反饋的獎(jiǎng)勵(lì)函數(shù)來(lái)更新學(xué)習(xí)。本文使用經(jīng)驗(yàn)重放存儲(chǔ)器來(lái)存儲(chǔ)狀態(tài)之間的轉(zhuǎn)移，并從經(jīng)驗(yàn)重放存儲(chǔ)器中批量采樣 (s,a,s',r)，用于更新網(wǎng)絡(luò)參數(shù)θ。模型的損失函數(shù)如下：

利用損失函數(shù)的梯度值來(lái)更新參數(shù)，來(lái)縮小預(yù)測(cè)的 Q 值和期望的目標(biāo) Q 值的差距，公式如下：

算法流程如下：

實(shí)驗(yàn)

本文采用了 AI2, IL,CC 這三個(gè)算術(shù)應(yīng)用題數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中 AI2 有 395 道題目，題目中含有不相關(guān)的數(shù)字，只涉及加減法。IL 有 562 道題目，題目中含有不相關(guān)的數(shù)字，只涉及加減乘除單步運(yùn)算；CC 有 600 道題，題目中不含有不相關(guān)的數(shù)字，涉及加減乘除的兩步運(yùn)算。

三個(gè)數(shù)據(jù)集準(zhǔn)確率如下圖：

觀察上述實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，本文提出的方法在 AI2，CC 數(shù)據(jù)集上取得了最好的效果。ALGES 在 IL 上表現(xiàn)很好，但是在 AI2 和 CC 數(shù)據(jù)集上表現(xiàn)卻很差，這從側(cè)面證明了我們的方法有更好的通用性。UnitDep 提出的單位依賴(lài)圖對(duì)只有加減運(yùn)算的 AI2 數(shù)據(jù)集沒(méi)有明顯的效果，其增加的 Context 特征在 CC 數(shù)據(jù)集上有取得了明顯的效果，但是卻在 AI2 數(shù)據(jù)集上效果明顯下降，這里表現(xiàn)出人工特征的局限性。對(duì)于本文提出的方法，重排序在 CC 數(shù)據(jù)集上，提升效果明顯，由于 AI2 只有加減運(yùn)算，IL 只涉及單步運(yùn)算，所以在這兩個(gè)數(shù)據(jù)集上效果不變。

除此之外，本文還做了單步和多步的斷點(diǎn)分析，實(shí)驗(yàn)效果表明，本文提出的方法在多步上表現(xiàn)十分優(yōu)異，實(shí)驗(yàn)結(jié)果如下圖：

運(yùn)行時(shí)間如下圖：

觀察單個(gè)題目求解需要的時(shí)間，我們可以發(fā)現(xiàn)，多步運(yùn)算的數(shù)據(jù)集 CC，在時(shí)間上明顯耗費(fèi)更多。ALGES 由于要枚舉所有可能的候選樹(shù)，因此耗費(fèi)時(shí)間最長(zhǎng)。本文提出的方法，求解效率僅次于只有 SVM 做運(yùn)算符，和相關(guān)數(shù)字分類(lèi)的 ExpTree。

平均獎(jiǎng)勵(lì)和準(zhǔn)確率的走勢(shì)如下圖：

總結(jié)

本文首次提出了一個(gè)用于求解數(shù)學(xué)應(yīng)用題的增強(qiáng)學(xué)習(xí)框架，在基準(zhǔn)數(shù)據(jù)上其求解效率和求解效果展現(xiàn)出較好的效果。

未來(lái)，我們將繼續(xù)沿著深度學(xué)習(xí)，增強(qiáng)學(xué)習(xí)這條線去設(shè)計(jì)數(shù)學(xué)應(yīng)用題自動(dòng)求解器，來(lái)避免過(guò)多的人工特征。同時(shí)在更大更多樣化的數(shù)據(jù)集上，嘗試求解方程組應(yīng)用題。

論文題目:《MathDQN: 利用深度增強(qiáng)學(xué)習(xí)求解算術(shù)應(yīng)用題》

英文:《MathDQN: Solving ArithmeticWord Problems via Deep Reinforcement Learning》

Paper URL:

http://cfm.uestc.edu.cn/~zhangdongxiang/papers/mathdqn.pdf

團(tuán)隊(duì)：?阿凡題研究院、電子科技大學(xué)、北京大學(xué)

作者：?王磊，張東祥，高聯(lián)麗，宋井寬，郭龍，申恒濤

更多干貨內(nèi)容，可關(guān)注AI前線，ID：ai-front，后臺(tái)回復(fù)「AI」、「TF」、「大數(shù)據(jù)」可獲得《AI前線》系列PDF迷你書(shū)和技能圖譜。