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

• original paper: https://kaigi.org/jsai/webprogram/2013/pdf/643.pdf

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

3. 小問集合の抽出

一つの問題は、

• 前提記述 (P)
• 質問記述がいくつか (Q)

に分解できる.

分解したら、

• P = {P}
• Q = {Q1, Q2}

に対して、

• (P + Q1)
• (P + Q2)

を考えるのが自然.

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

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

パターン言語

• \(\Sigma\): Alphabet
• X: Vars

を用いて \((\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 に、

• \(|UP \triangle (U \cap L(PiP))|\)
• \(|UQ \triangle (U \cap L(PiQ))|\)

を共に小さくする.

\(\triangle\) は、対称差

具体的なアルゴリズム

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

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

• \(T \leftarrow TP\)
• \(\Pi \leftarrow \{\}\)
• 次を \(k\) 回繰り返す
  • \(e_1 \in_u T\) (ランダムに選ぶ)
  • \(e_2 \in_u T\) (\(e_1 \ne e_2\))
  • \(p = mcp(e_1, e_2)\) ; minimum common pattern
  • \(x = | L(p) \cap TP |\) ; goodness
  • \(y = | L(p) \cap TQ |\) ; badness
  • \(m' = \frac{x}{x+y}\)
  • If \(m' \geq m\)
    • \(\Pi \leftarrow \Pi \cup \{ P \}\)
    • \(T \leftarrow T \setminus L(p)\)
• \(T\) を返して終了

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

• score of P: \(\sum \{ |L(p) \cap TP| - |L(p) \cap TQ| : p \in \Pi_P, d \preceq p \}\)
• score of P: \(\sum \{ |L(p) \cap TQ| - |L(p) \cap TP| : p \in \Pi_Q, d \preceq p \}\)

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

問題文間の類似度

自然言語文間の類似度

索引語 \(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\).

重み掛ける流量の和な. 書いてないけど、枝の容量は \(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 の分類は、

うーん.

PiP

• x1 と x2 する x3
• x1 点 x2 と x3 を x4.
• x1 い x2 と x3 (x1(adj) x2 and x3)
• x1 とき x2 (when x1, x2)

PiQ

• x1 が x2 り x3 (x1 do x2 and x3)
• x1 である. (it is x1)
• x1 となる. (it becomes x1)
• であり、 (It is …. and)

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

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