外文翻譯-概率的數(shù)學(xué)公式識別使用一個二維的上下文無關(guān)文法圖

1、(本科畢業(yè)設(shè)計論文)畢業(yè)設(shè)計論文外文資料翻譯作 者：學(xué)科專業(yè)：學(xué) 號：班 級：指導(dǎo)老師：附件：1.外文原文2.外文資料翻譯譯文2021年6月概率的數(shù)學(xué)公式識別使用一個二維的上下文無關(guān)文法圖數(shù)學(xué)表達式的識別問題。興旺的系統(tǒng)靈活的，它可以很容易的擴展語法由于它的圖形語法，不需要指定規(guī)那么的優(yōu)先級。在這個意義上是最正確表達式的所有可能的解釋是擴大沒有早期的承諾或艱難的決定。在這，我們給出了整個系統(tǒng)的概述和描述詳細(xì)說明用圖的語法和解析過程系統(tǒng)，隨著對字符的一些初步結(jié)果,的結(jié)構(gòu)和表達的識別性能。關(guān)鍵詞在線，手寫識別，OCR，數(shù)學(xué)方程，二維圖形語法，圖框語法一、引言在計算機和其他地方的增長盡管在我們的生活

2、中的數(shù)字設(shè)備，紙和筆是最傳送或記錄信息的方便的方法方法。特別是，數(shù)學(xué)表達式是最反對手寫輸入的應(yīng)用。計算機理解手寫文字手寫或數(shù)學(xué)公式是一個正在進行的研究領(lǐng)域。不同的？困難是由于幾個因素，包括寫作風(fēng)格的變化較大，其詞匯的指示可能的替代品的大小，和一定形狀的無語義歧義理解例如，“O和“0。數(shù)學(xué)表達式識別包括兩個主要ubproblems：賽格字符識別的識別化和標(biāo)記符號數(shù)字，字母，特殊數(shù)學(xué)符號和結(jié)構(gòu)分析下優(yōu)秀的表達結(jié)構(gòu)的空間字符和字符識別之間的關(guān)系定義輸出。數(shù)學(xué)表達式的識別更挑戰(zhàn)相比，在識別由于手寫文本O數(shù)學(xué)表達式的復(fù)雜語義以及漢字的二維布局。有幾種方法在文獻結(jié)構(gòu)數(shù)學(xué)表達式的分析：程序編碼規(guī)那么 1 ；

3、X-Y削減基于投影親？LES 2 ， 3 ；基線樹的構(gòu)建 4 ， 5 ；隨機上下文無關(guān)語法 6 ；約束屬性文法 7 ；分層分解分析 8 ；生成樹的生成加權(quán)圖 9 ；和圖形語法 10 13 。在之間這些方法有一定的優(yōu)勢，圖語法：為把 14 了，圖語法的本質(zhì)二維表示可以代表一個可能在于有限數(shù)量的模式，有限數(shù)量的規(guī)那么，當(dāng)增強屬性。事實上，圖語法是公式識別的首選方法之一,近年來。在 10 ，圖語法添加到現(xiàn)有的系統(tǒng)放松約束的書寫順序的符號。在 11 13 的工作是基于圖重寫，在一個自底向上使用的語法分析器，折疊節(jié)點匹配在每一個規(guī)那么應(yīng)用到一個節(jié)點。這些系統(tǒng)，的解析過程的輸出是一個單節(jié)點的含所有輸入符號

4、和對應(yīng)的預(yù)期所表達的意思。我們的系統(tǒng)使用概率上下文無關(guān)圖指導(dǎo)系統(tǒng)數(shù)學(xué)有效的解釋和關(guān)聯(lián)概率可解釋的表達。所提出的系統(tǒng)區(qū)別于以往工作的概率算法的方法：先前的基于圖文法方法修改初始圖的應(yīng)選擇的語法規(guī)那么是不可逆的，我們的方法娛樂的相鄰標(biāo)記所有可能的解釋最終的表達。這可能是由于它的圖形語法，可以指定需要規(guī)那么的優(yōu)先級，在所有可能的解釋為在迄今為止被保存在一個擴展圖。在這框架，所有可能的解釋歧義消解的表達是在分析結(jié)束，由考慮到由此產(chǎn)生的可能的解釋。一種解釋的可能性取決于適宜性的符號空間分布的規(guī)律和與公認(rèn)的符號的似然。輸出我們的系統(tǒng)是最有可能的解析的輸入，隨著他們的情況。這是一個重要的優(yōu)勢所提出的系統(tǒng)，為

5、用戶可以簡單地選擇正確解析從名單上，而不是糾正解析結(jié)果或重寫的表達。下一節(jié)簡要描述圖克火星，然后我們的方法和實驗結(jié)果AR在隨后的章節(jié)中描述。在本文的其余局部，使用的術(shù)語指的是字符識別的OCR不久符號和字符的互換是指segmente字符；和節(jié)點或令牌是指目前的O組符形式的表達式。二圖語法數(shù)學(xué)公式精確的語法嚴(yán)格的數(shù)學(xué)的適當(dāng)?shù)臄?shù)學(xué)定義是什么性表達和正確解析含義一個給定的數(shù)學(xué)表達。語法包括生產(chǎn)規(guī)那么說明終端和非終端定義在語法方面，聯(lián)合產(chǎn)生作為一個結(jié)果的規(guī)那么應(yīng)用的非終端。例如我們可以舉一個簡單的字符串的語法，德？NES規(guī)那么這使得數(shù)字和整數(shù)如下這里的10數(shù)字終端，而數(shù)字和點是非終端：數(shù)學(xué)公式精確的語法

6、嚴(yán)格的適當(dāng)?shù)臄?shù)學(xué)定義是什么性表達和正確解析含義一個給定的數(shù)學(xué)表達。語法包括生產(chǎn)規(guī)那么終端和非終端定義語法方面，聯(lián)合產(chǎn)生作為一個結(jié)果的規(guī)那么應(yīng)用的非終端。例如我們可以舉一個簡單的字符串的語法，規(guī)那么這使得數(shù)字和整數(shù)如下這里的10數(shù)字終端，而數(shù)字和整數(shù)是非終端。數(shù)字=0,1,2,3,4,5,6,7,8,9整數(shù)=0,1,2,3,4,5,6,7,8,9,圖的語法提供了一個形式主義的語法多維數(shù)據(jù)不能計算處理通過字符串的語法實現(xiàn)。由于他們的介紹解決圖像處理問題，圖語法被用來在不同的領(lǐng)域，如并行系統(tǒng)，數(shù)據(jù)庫，編程語言和生物學(xué) 15 。在數(shù)學(xué)表達式的識別，圖的語法是十配合使用圖重寫的方法初始圖形構(gòu)造標(biāo)記的表達

7、反復(fù)降低到相應(yīng)的單節(jié)點圖解析表達式樹。在每次迭代中，一個語法規(guī)那么的選擇和應(yīng)用，當(dāng)圖的電流圖的匹配規(guī)那么的模式圖；結(jié)果規(guī)那么的應(yīng)用，當(dāng)前圖轉(zhuǎn)化為用規(guī)那么表示。特別的，規(guī)那么R =GL；GR；C；EM由左側(cè)和右側(cè)圖圖Gl GR，一個適用性謂詞C，和一個嵌入規(guī)那么了Em。適用性謂詞C是一組約束節(jié)點和/或邊緣的屬性值，和不存在一定的邊緣，需要滿足，以便能應(yīng)用的語法規(guī)那么。例如，應(yīng)用一個規(guī)那么謂詞表示兩個標(biāo)鄰近的標(biāo)記應(yīng)具有可接受的大小和位置關(guān)系。適用的謂詞，應(yīng)用一個生產(chǎn)規(guī)那么可以限制即使規(guī)那么有在輸入圖的匹配。一個生產(chǎn)應(yīng)用一個圖G的規(guī)那么產(chǎn)生G0，這是表示GR G0。與生產(chǎn)GR G0一個發(fā)生圖G是一個

8、圖GL GR生產(chǎn)取代G0按照嵌入規(guī)那么，EM，如果適用謂詞是滿意的。嵌入規(guī)那么規(guī)定子圖的將子GR在圖含有原子GL。在字符串的語法，安置生產(chǎn)是顯而易見的，但是在圖文法，安置生產(chǎn)圖GR必須指定通過嵌入規(guī)那么的EM，描述如何處理懸邊邊緣那個失去一個節(jié)點后，GL是從圖和如何連接到現(xiàn)有生產(chǎn)圖GR圖。一個圖G =N；E被認(rèn)為是在圖語法GG的當(dāng)且僅當(dāng)N 2 N節(jié)點和E 2 E邊緣的GG和存在的推導(dǎo)，可以生成G規(guī)那么從河從圖G圖G0推導(dǎo)語法GG是德？內(nèi)德作為一系列產(chǎn)品其中GRI1 G1ri2 G2：里克G0。圖1顯示了一個例規(guī)那么從圖G的導(dǎo)出G0在哪兒標(biāo)記節(jié)點A和C都有替換節(jié)點D一個有向邊從A到C的嵌入規(guī)那么

9、表示只有邊緣向C和邊出應(yīng)保持。虛節(jié)點和邊在規(guī)那么說明可能的額外的節(jié)點和邊，這可能會或可能不會在實際的呈現(xiàn)。圖1。規(guī)那么R圖給圖G0應(yīng)用。三、提出的方法所提出的系統(tǒng)的概述，如圖2所示。輸入的表達首先分割成孤立的符號(一個字符或中風(fēng)的字符，每個符號的OCR引擎解釋局部識別ii-a.然后初始圖的構(gòu)造，其中的節(jié)點a認(rèn)可的符號和邊緣代表德連接符號之間的空間，如N段iii-b.解析算法應(yīng)用文法規(guī)那么的電流圖，添加一個新的節(jié)點，在每次迭代中的邊緣參見中間記號在圖2。這些新的節(jié)點或標(biāo)記鄰近的令牌代表可能的解釋。解析過程繼續(xù)下去，直到?jīng)]有有效的生產(chǎn)電子資金轉(zhuǎn)賬。我們的語法和解析算法的解釋的方向III-C. II

10、I-D。A. 分割和字符識別OCR輸入的表達首先分割成單獨的基于時間維度的特征，即相對兩個連續(xù)的中風(fēng)或大之間的時間差特征是用來表示字符邊界。然后，在空間上重疊的符號被重新組合例如兩個“+符號筆劃。OCR系統(tǒng)是結(jié)合支持向量機SVM和人工神經(jīng)網(wǎng)絡(luò)ANN，結(jié)合使用。它的輸入的分段特征參數(shù)和輸出三個相關(guān)的分?jǐn)?shù)。我們從拉維奧拉數(shù)據(jù)集選擇的一個子集 5 ，附錄。預(yù)處理包括大小歸一化的事對在線數(shù)據(jù)以減少工件的坐標(biāo)每個點被映射到一個固定的坐標(biāo)范圍。然后人物形象是通過插值從這些點的創(chuàng)立。特征提取作為輸入的調(diào)整大小的圖像特征，忽略了時間維度。這樣做是為了消除在人物畫的時空變化，以及允許用戶修改的符號和公式后可以完

11、成了方程。兩分類,輸入功能包括水平，垂直和對角直方圖的符號圖像的水平，垂直和對角線的深處的黑色像素點符號圖像；8的Windows 8黑色像素數(shù)在整個符號和圖像的寬度和高度的比率。在這個數(shù)據(jù)的支持向量機的系統(tǒng)成功率92%。雖然有方法生成后從多類支持向量機分類的概率陽離子，我們使用一個神經(jīng)網(wǎng)絡(luò)生成的分類，陽離子的選擇和獲得可靠的識別欺詐證據(jù)。人工神經(jīng)網(wǎng)絡(luò)的分類，用是一個1-hid隱藏層前饋神經(jīng)網(wǎng)絡(luò)與30隱藏神經(jīng)元。這個分類的性能低相比于SVM，詳細(xì)的和高識別88%和97%的比率，分別為。由于支持向量機在的表演更成功，OCR系統(tǒng)采用支持向量機的輸出作為首選，并獲得下一個兩個選擇和控制從人工神經(jīng)網(wǎng)絡(luò)的

12、研究。什么時候精度是低于國家的最先進的OCR結(jié)果，不在這項工作中的主要焦點。B. 構(gòu)造初始圖最初的圖是從一個標(biāo)記列表生成通過分割得到通過OCR發(fā)動機。在該圖中，一個節(jié)點對應(yīng)于一個標(biāo)記和一個邊緣的兩個節(jié)點之間說明這兩個節(jié)點在表達的空間布局的鄰居。過程可以說正是利用以下定義圖形元素：節(jié)點：一個節(jié)點是一個元組的n =t；i；c；A) t 是節(jié)點類型的；i 是一個獨特的識別；c是相同的的規(guī)那么，構(gòu)建了節(jié)點屬性值。一個節(jié)點的類型是詞法類型的符號，如數(shù)字，字母，算子。每個節(jié)點知道哪些規(guī)那么構(gòu)建自身，所以如果需要的話，整個歷史可以產(chǎn)生。在圖4中每個方塊代表一個圖中的節(jié)點。邊：邊緣是元組E =t；n1；n2t

13、 是的邊緣型，n1和n2是連接節(jié)點在一起的邊緣。有三種類型的邊緣用解析過程：l 空間關(guān)系的邊表示兩個節(jié)點是否鄰居見定義以下。l 組件的邊緣的非終端節(jié)點及其關(guān)系組件，用于生成語法樹后解析過程。l 生產(chǎn)邊緣組件邊緣反，連接一個終端和非終端節(jié)點到非終端節(jié)點，利用它。初始圖形空間關(guān)系的邊緣，只有他們決定勝負(fù)，而其他人組件生產(chǎn)的邊緣被用來跟蹤和加速解析過程。在此系統(tǒng)中，空間關(guān)系的邊緣不有任何屬性，因為我們不區(qū)分不同鄰里關(guān)系的不同類型側(cè)，頂部，底部等；不同的社區(qū)類型是隱式的決定每個規(guī)那么的適用性謂詞。我們的優(yōu)勢方法是將空間關(guān)系的屬性適用性詞的規(guī)那么，而不是判定元件全球空間關(guān)系的定義，每個規(guī)那么可以有它自己

14、的空間關(guān)系的定義類別。在這種方式中，而不是拘泥于標(biāo)記這是寫的一個與側(cè)弱y符號附近的邊緣，比方下標(biāo)規(guī)那么決定如果這兩個符號的相對位置后大的應(yīng)用規(guī)那么。街道本身是有一個清晰的線他們的包圍盒的中心點之間的視線在小于一個閾值計算的距離從表達式中的符號的平均大小。通常，一個令牌3最正確識別方案與之相關(guān)的。然而，如圖2所示，如果一個角色可能屬于一個以上的類型的符號如“+是一個操作數(shù)的符號或“t，然后生成令牌它為了簡化解析過程。C. 語法我們用一個概率上下文無關(guān)文法是二維的基于數(shù)學(xué)的語法，使用空間布局在本規(guī)那么的適用性謂詞信息。在這個語法，規(guī)那么是一個元組R =GR；GL；C在GL該模式圖，GR是產(chǎn)品圖和C

15、的應(yīng)用謂詞，C：通用能力！ftrue falseg通用汽車的地方是一個與GL圖形。沒有嵌入因為所有的規(guī)那么，規(guī)那么的遵循相同的嵌入。正常圖語法規(guī)那么說明，GL被GR但在我們的系統(tǒng)中，它說明，GR被添加到圖形如一個新的節(jié)點和GL保存它。左邊的圖GL每個規(guī)那么是一個星形圖一圖有一個中心節(jié)點和周圍的鄰居節(jié)點只連接到中央節(jié)點，和正確的右手邊的圖的GR是一個節(jié)點。圖3 GL和兩個簡單的語法規(guī)那么的GR圖，其中“+在R1和R2的規(guī)那么的規(guī)那么算子是中央節(jié)點規(guī)那么。對申請的決定規(guī)那么中最重要的局部來自性謂詞。對于大多數(shù)的規(guī)那么符號之間的角度和距離的檢查，以及它們的大小。一些規(guī)那么可以對屬性有進一步的檢查價值

16、觀。例如，用于檢查分?jǐn)?shù)的規(guī)那么，GL具有中心節(jié)點代表水平線符號。用性謂詞的約束保持寬松，為了保持所有可能的解釋數(shù)學(xué)表達式。例如，上標(biāo)規(guī)那么不要求，上標(biāo)符號較小的尺寸比的根底，但它是不很大。由于匹配節(jié)點保持在圖中，每個規(guī)那么也有一個謂語，檢查不存在生產(chǎn)的邊緣連接到相同的節(jié)點GR的規(guī)那么，以防止再次匹配相同的節(jié)點產(chǎn)生相同的產(chǎn)品。這有點復(fù)雜解析過程和增加了復(fù)雜性，但刪除需要定義優(yōu)先規(guī)那么。目前有17的語法規(guī)那么，包括對于下標(biāo)，上標(biāo)的數(shù)學(xué)規(guī)那么，運算符+，'，' '，和'，分?jǐn)?shù)，求和，和積分，以及至于寫在多個非符號組合的一些規(guī)那么重疊筆劃例如' = '，

17、'。某些終端與非終端定義語法中給出附錄。所開發(fā)的系統(tǒng)主要是將手寫數(shù)學(xué)表達式為乳膠容易進入科學(xué)文章；因此，在LaTeX代碼正確的語法是明確的。然而，系統(tǒng)不了解數(shù)學(xué)的優(yōu)先級規(guī)那么，因此兩個或兩個以上的可能會產(chǎn)生解析方案對于一個輸入，只會得到解決的優(yōu)先規(guī)那么例如，A + BC + D。然而，由于該系統(tǒng)提供的所有可能的解釋給用戶，用戶可以選擇正確的解釋的幾種可能的解釋之間。我們的解析算法是一個相當(dāng)簡單的底部過程。在每一輪中，算法檢查什么規(guī)那么的語法可以在每個令牌是適用的圖。如圖4所示，最初有4個代幣在初始圖4節(jié)點對應(yīng)；然后，之后第一輪，兩個新的標(biāo)記A2和a + b的生成和添加到圖。特別地，兩個

18、任務(wù)必須由解析器進行：尋找一個相匹配的規(guī)那么模式圖和嵌入產(chǎn)生的產(chǎn)品圖。因為任何模式圖規(guī)那么是在我們的系統(tǒng)中的星形圖，當(dāng)處理一個節(jié)點，分析器查找匹配的規(guī)那么具有相同的中心節(jié)點；然后檢查相鄰節(jié)點和適用性謂詞匹配過程。一旦找到一個匹配的，一個新的節(jié)點根據(jù)的規(guī)那么，然后連接到現(xiàn)有的圖組件和生產(chǎn)的邊緣?？臻g關(guān)系邊緣產(chǎn)生新產(chǎn)生的節(jié)點在后沒有可能的生產(chǎn)是在現(xiàn)有的圖左。每個新的節(jié)點繼承了它的組件的鄰居?？臻g關(guān)系的新生成的節(jié)點之間的邊分開。為了處理的解析過程的復(fù)雜性在所有可能的地方解釋保持，我們使用的可能性標(biāo)記的決定擴展這個令牌即應(yīng)用規(guī)那么。理想的應(yīng)該是做一個A*搜索，但是目前它是通過一個閾值是動態(tài)調(diào)整，根據(jù)令

19、牌總數(shù)和覆蓋如何輸入表達式的多標(biāo)記覆蓋的最好的令牌。解析過程的輸出是一個圖可能的產(chǎn)品是目前。此外，如果輸入可以定義的語法，那么至少有一個節(jié)點其中包括所有輸入符號將在輸出圖。由于組件的邊緣保持產(chǎn)品的歷史，一個如果一個表達式樹可替代的產(chǎn)生解釋節(jié)點為根和組件邊緣之后，直到到達一個終端節(jié)點。我們計算的可能性，也被稱為性，性每一個解析的替代根據(jù)預(yù)先了解空間布局。OCR輸出的概率分布。這些分布問題，例如為根底的相對大小差異下標(biāo)符號，都學(xué)會了在單獨的訓(xùn)練數(shù)據(jù)。總之，所產(chǎn)生的每一個節(jié)點可能是產(chǎn)生的空間關(guān)系的平均對數(shù)似然節(jié)點和構(gòu)件是似然一個符號的發(fā)生概率。舉個例子，在圖4的輸入，可能標(biāo)記的a+ b將取決于的可能

20、性的符號“a的空間布局，“b和“+，就規(guī)那么添加。我們的每一個空間分布模型分布統(tǒng)計直方圖和計算的可能性在兩個符號中的一個給定的距離例如X或Y偏移從“a和+相對于該直方圖。我們還使用字符識別概率的區(qū)別之間的替代分析a+ b和atb共享相同的布局相似，但不同的可能性字母“t。一個更復(fù)雜的表達式的可能性例如a + b2是由其平均數(shù)對數(shù)似然性計算通過在每個組件的數(shù)量加權(quán)組件組件?？赡苁窃诿總€規(guī)那么進行計算應(yīng)用。四、實驗結(jié)果開發(fā)的系統(tǒng)使用的一局部測試在協(xié)會收集的數(shù)學(xué)表達數(shù)據(jù)庫這項工作 16 。完整的數(shù)據(jù)庫包含57個方程每次從15個不同的用戶選擇，從常見的表達結(jié)論以匹配由王等人 17 使用的。表達長度范圍

21、從7到30個字符長度。測試集由20個方程組成，每個由5個不同的用戶。結(jié)果是在與表達分析精度產(chǎn)生的膠乳的代碼方程正確的；結(jié)構(gòu)的識別精度乳膠代碼除了OCR錯誤糾正；字符識別精度，說明如表IV。任務(wù)準(zhǔn)確性計數(shù)正確認(rèn)識17% 17 / 100的表達正確的結(jié)構(gòu)分析50% 50 / 100正確的字符識別 79% 1100 / 1410表一整體準(zhǔn)確度5用戶×20表達式任務(wù)準(zhǔn)確性比例表達長度小于等于1025 / 100正確認(rèn)識表達52%13 / 25正確的結(jié)構(gòu)分析88% 22 / 25表達的長度趨于11 30 75 / 100正確認(rèn)識的表達5,33 % 4 / 75正確的結(jié)構(gòu)分析 37,33 % 28 / 75表二分析表達式的長度方面的結(jié)果。我們看到，方程的識別精度較低17%，這是不是很奇怪的DIF水平的問題；但結(jié)構(gòu)識別精度也不是很高50%。這可以通過事實的解釋整體結(jié)構(gòu)誤差影響的意義.明顯的OCR精度