Semantic Tagging of Mathematical Expressions

數學表達式之語意分析 (STME)的目標是為數學式中的每個符號標記上其隱含的語意。本研究提出一個解決STME的新方法，此方法僅需要一個數學規則庫 (文法庫)作為預備知識，而不倚賴額外的自然語言資訊，也不需要任何帶標記的訓練資料。我們指出，除了數學規則之外，數學式中變數的特殊性質以及人們書寫數學式時的習慣都能夠幫助分辨數學式模糊的語意。因此，我們的方法考慮了數學規則和變數特性的限制，藉以找出每個符號可能的語意組合；接著，我們再用非監督式學習訓練出一個機率模型來模擬人們書寫數學式的習慣。當一篇文章有多種可能的語意組合，機率模型便可以決定最有可能的一種。我們從一個公開的數學論壇上蒐集巨量數學式，建立一個大規模的訓練資料與測試資料庫，來訓練機率模型和測量準確率。實驗結果顯示我們提出的方法的準確率顯著地高於現行實作上常見的最大頻率法。最後，我們從資料庫的統計結果中點出一些數學語言的性質。Semantic tagging of mathematical expressions (STME) gives the semantic meaning to tokens in mathematical expressions. In this work, we propose a novel STME approach that relies on neither text along with expressions, nor labelled training data. Instead, our method only requires a mathematics grammar set. We point out that besides the mathematics grammar, the special property of variables and user habits of writing expressions help us understand the implicit user intents. We build a system that considers both restrictions from grammar and variable property, and then apply an unsupervised method to our probabilistic model to learn the user habits. To evaluate our system, we build a large-scale training and testing dataset automatically from a public math forum. The results demonstrate the significant improvement of our method, compared to the maximum-frequency baseline. We also make some statistics to reveal the mathematics language properties.口試委員審定書 i 中文摘要 ii Abstract iii Contents iv List of Figures vii List of Tables viii 1 Introduction 1 2 Problem Formalization and Related Work 6 2.1 Context-Free Grammar (CFG) . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Problem Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.1 Mathematical Search . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.2 Semantic Enrichment . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.3 Part-of-Speech Tagging . . . . . . . . . . . . . . . . . . . . . . 10 3 System Framework and Preprocessing 12 3.1 System Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Parse Forest Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Tagging Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Probabilistic Model 17 4.1 Two Steps of Writing Expressions . . . . . . . . . . . . . . . . . . . . . 17 4.2 Model Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3 Learn the Probabilistic Model . . . . . . . . . . . . . . . . . . . . . . . 21 4.4 Reduce Search Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Experiments 24 5.1 Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 Test Dataset and Ground Truth . . . . . . . . . . . . . . . . . . . . . . . 26 5.4 Competitive Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.5.1 Overall Performance . . . . . . . . . . . . . . . . . . . . . . . . 28 5.5.2 Performance of Each Token . . . . . . . . . . . . . . . . . . . . 29 5.5.3 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.6 Issue of Mathematics Language . . . . . . . . . . . . . . . . . . . . . . 31 5.6.1 Document Frequency and Zipf’s Law . . . . . . . . . . . . . . . 31 5.6.2 Merging Standard Function . . . . . . . . . . . . . . . . . . . . 33 5.6.3 Derivation Ambiguity . . . . . . . . . . . . . . . . . . . . . . . 33 5.6.4 Issue of Mathematics Language . . . . . . . . . . . . . . . . . . 34 6 Conclusions 36 A Full CFG Rules 37 A.1 General Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 A.2 Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 A.3 Tag of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 A.4 Function-Related Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 A.5 Set-Related Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 A.6 Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 A.6.1 marks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 A.6.2 Summations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 A.6.3 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 A.6.4 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 A.7 Consistence Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Bibliography 4