文字列パターンと MathML による構造を利用した数学問題文の検索

自然言語処理 テキストマイニング

よくみたら、京都大学生徒の卒論だった. 諸君はもっといいの読むべき.

3. 小問集合の抽出

一つの問題は、

に分解できる.

分解したら、

に対して、

を考えるのが自然.

訓練データ TP, TQ を用いて、 未知の問題データ U に含まれる UP, UQ を抽出したい.

そこで次に説明するパターン言語をもちいる

パターン言語

を用いて \((\Sigma \cup X)^+\) と定義されるもの. さらにここでは、同じ変数は一度しか使われないと限定する (正規パターン言語)

正規言語の繰り返しとかグループ化が無い劣化バージョンである.

汎化関係

パターン \(p, q\) について、 パターン \(p\) にある代入をして、パターン \(q\) になったとき、 \[q \preceq p\] と書いて、 \(p\)\(q\) の汎化 (generalization) であるとか、 あるいは \(q\)\(p\) を包摂 (subsume) するとか言う.

パターンの集合 \[P = \{ p_1 .. p_n \}\] に対して、 あるパターン \(q\) が、 \[\forall i .~ q \succeq p_i\] を満たすとき、 \(q\)\(p_1 .. p_n\) の共通汎化という.

共通汎化であるようなパターンの集合 \(\Pi = \{ q, q_1, q_2 .. \}\) について、 \[\forall i .~ \lnot(q_i \preceq q)\] のとき、\(q\) を極小の共通汎化だという.

さて、パターン \(p\) が作る言語を \(L(p)\) と書く. これは、p に、空文字列を含む任意の代入を行うことで得る文字列の無限集合

さらに、パターンの集合 \(\Pi = \{ p_1 .. p_n \}\) に対して \(L(\Pi) = \bigcup L(p_i)\) とする.

話戻す

TP、TQ はそれぞれ、 パターン集合 \(\Pi_P, \Pi_Q\) が生成する \(L(\Pi_P), L(\Pi_Q)\) の部分集合だと仮定する.

訓練データ TP, TQ から、次のような \(L(\Pi_P), L(\Pi_Q)\) を作ることを目指す.

U を受け取って UP, UQ に、

を共に小さくする.

\(\triangle\) は、対称差

具体的なアルゴリズム

TP, TQ から、まずは \(\Pi_P\) を作る. 全く同様の手順から \(\Pi_Q\) は作られる.

繰り返し回数 \(k\) 閾値 \(m\) を用意して、

こうして構成した \(\Pi_P, \Pi_Q\) から、 未知の文 \(d\) が来た時に、 これを次の2つのスコアの大小比較によって、 \(d\) が P、Q どちらに属するかを決定する.

(このスコア式のあたり、誤植だと思われるので、上のようにした)

問題文間の類似度

自然言語文間の類似度

索引語 \(D = (w_1 .. w_n)\) に tf-idf で重み附けて cos similarity SIM-N を定める

数式集合間の類似度

一つの数式と一つの数式の間の類似度には、 Yokoi+ の手法 T-sim を用いて計算する.

数式集合一つと一つの間の類似度には 以下で説明する Earth Mover's Distance (EMD) を用いる.

これにはまず 2つの数式集合 \(\Pi_1, \Pi_2\) から これを頂点にした 有向グラフを作る.

  1. 頂点は \(V = \{s\} \cup \Pi_1 \cup \Pi_2 \cup \{t\}\) where \(\Pi_1 = \{e_1 .. e_n\}\), \(\Pi_2 = \{f_1 .. f_m\}\).
  2. 枝は \(s \rightarrow e_i\)\(e_i \rightarrow f_j\)\(f_j \rightarrow t\).
このグラフの最大流問題を解くことを考える.
maximize \(\sum_{(i, j)} \text{T-sim}(e_i, f_j) F_{i,j}\)

重み掛ける流量の和な. 書いてないけど、枝の容量は \(e_i \rightarrow f_j\)\(\min(w(e_i), w(f_j))\) として、 他は無限の容量を持つことにすればいい. ここで \(w(e)\) は数式 \(e\) の重み (書いてないけどな).

流量 \(F\) を得たら 最終的に、集合間の類似度を以下のようにする

\[\text{SIM-E}(\Pi_1, \Pi_2) = \frac{ \sum_{i,j} \text{T-sim}(e_i, f_j) F_{i,j} }{\sum F_{i,j}}\]

全体の類似度

自然言語部分と、数式部分とを合わせて、 \[\text{SIM-Q} = \sqrt{\text{SIM-N} \times \text{SIM-E}}\] とする. おわり.

実験

できたパターンは、 基本的には human-readble じゃなさそう.

まず、P,Q の分類は、

P Q
\(F_1\) 65.9% 82.1%

うーん.

PiP

PiQ

で、えっと、 最終的には、問題を、11のクラスに分類してたらしい. 自然言語部分だけのVSMと、 数式をそれに加えたバージョンであるVSM-MATHとの比較.

「統計」なんかはどちらでも100%. 大体は、上手くいっていて、 「ベクトル」は、85.2 \(\rightarrow\) 96.4%. よくみたら、落ちてるのもある. 「三角比」70.2 \(\rightarrow\) 56.0%.