Monoxer Intern Report #19_数式正解判定アルゴリズムの実装

はじめに

モノグサ株式会社のソフトウェアエンジニアのインターンとして参加させていただいている堀毛晴輝です。 Intern Reportを書くのは2回目で、1回目の記事はこちらです。2022年夏のインターン終了後も、通年でインターンを継続させていただいています。

取り組んだこと

Monoxerでは学習者が数式を解答する形式の問題があります。

この形式では、学習者は数式を入力し解答します。しかし、この形式の問題では登録されている正解の数式と完全に一致しないと不正解となってしまっていました。たとえば正解が $(x+2)(x+3)$ の問題では、 $(x+3)(x+2)$ は不正解と判定されてしまっていました。

問題作成時に別解を登録することができるため、簡単な数式であれば考えられる別解を登録しておくことで解決できますが、複雑な数式になると考えうるすべての別解を登録するのはとても困難です。「同値な数式を入力したのに、登録されている正解と一致しなかったために不正解となってしまう」というのは、学習者にとってモチベーション低下につながってしまいます。また、Monoxerがユーザーの記憶を正しく判定できない、ということにもつながってしまうため、これを解消したいです。

以下、正解として登録した数式を「正解」、学習者が入力した数式を「解答」と呼びます。今回は正解に等号や不等号が含まれているものは対象としません。

数値的な一致判定

正解/解答の数式に対して、 $x$ や $y$ などの変数についてそれぞれ同じ値を代入することを考えます。こうすると、正解と解答の数式は( $0$ で割ったり平方根の中に負の数が入ったりなどしていないなら)それぞれ一つの実数値になります。解答が正解と判定されるべき数式ならば、変数にどのような値を代入しても、この値は一致するはずです。

正解/解答の変数にランダムな変数を代入することを複数回行い、複数回全てでこの値が一致しているかで正誤判定をします。先述した通り、 $0$ で割ったり平方根の中に負の数が入ったりしている時には評価ができないのですが、そのような時は正解と回答は共に評価できなくなるはずです。実際の実装ではランダム変数の代入を複数回行い、値が違ったりどちらか一方が評価できない時は不正解と判定し、最終的に評価した値が一致した回数が規定回数以上であれば正解と判定しています。この判定は完全ではありませんが、実用上は十分な精度を持っていると考えています。

Monoxerでは数式をMathMLの形で扱っています(Monoxerで使われている MathML についてはこちらの記事が詳しいです)。

MathMLは木の構造をしています。この構造をうまく使い、式の値を求めます。例えば $3 ^ 2 + 1$ をMathMLで表すと、

<math>
    <msup>
        <mn>3</mn>
        <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mn>1</mn>
</math>

となります。この式を評価した値を求めることを考えます。これは、下から順に各頂点の値を求めていくことを繰り返せば良いです。

$3 ^ 2 = 9$ なので、

$9 + 1 = 10$ なので、

一番上のmath要素の値が求めたい数式の値です！このように、「子要素から順に値を求めていく」ことを繰り返すことで、求めたい式の値を求めることができます。

競技プログラミング風に言うと、 $\mathrm{dp[node]} := (\mathrm{node} を根とする部分木を評価した値)$ として、木DPをしているイメージです。

シンボル的な一致判定

「次の数式を因数分解せよ。 $x ^ 2+5x+6$ 正解: $(x+2)(x+3)$ 」

この問題は、「因数分解せよ」という問題なので、解答として $(x+2)(x+3)$ や $(x+3)(x+2)$ は正解に、 $x ^ 2+5x+6$ は因数分解されていないので不正解となるべきです。しかし、数値的な一致判定を用いると $x ^ 2+5x+6$ は正解と判定されてしまいます。

そこで、「因数分解せよ」や「展開せよ」といった問題では、数値的な一致判定に加え、以下の条件:

正解と解答に含まれる括弧の数が一致
正解と解答に含まれる各変数(mi要素)/各数字(mn要素)の個数が一致

を満たす時に正解と判定するようにしました。これにより、

$(x+2)(x+3)$ には括弧が2組あるが、 $x ^ 2+5x+6$ には括弧が存在しないので不正解
$(x+2)(x+3)$ には括弧が2組あり、 $x$ が2回、 $2,3$ が1回ずつある。 $(x+3)(x+2)$ にも括弧が2組、$x$が2回、2,3が1回ずつあり、数値的な一致判定でも正解と判定されるため、正解

となり、「因数分解せよ」「展開せよ」といった問題でも想定通りに別解の判定を行うことができるようになりました。

採点方法の設定方法

具体的に、ユーザーは問題作成時に、採点方法を次の3つ:

従来通り、正解と解答が完全に一致するかどうかで判定
数値的な一致判定で判定
数値的な一致判定とシンボル的な一致判定で判定

から選択できるようにしました。別解が考えられるような問題では数値的な一致判定を、「因数分解せよ」や「展開せよ」といった問題では数値的な一致判定とシンボル的な一致判定を選択することを想定しています。

工夫した箇所

特殊なケースの構文解析

数値評価を行うとき「下から順に値を求めていけばよい」と簡単に書きましたが、実はこれだけではうまくいきません。たとえば $\sin ^ 2 x$ などは、MathMLだと

<math>
    <msup>
        <mi>sin</mi>
        <mn>2</mn>
    </msup>
    <mi>x</mi>
</math>

と表現されます。これをそのまま数値評価しようとすると、 $\sin ^ 2$ を計算しようとしてエラーになってしまいます。 $\sin ^ 2 x = (\sin x) ^ 2$ なので、数値評価を行う時に気をつけなければなりません。

評価不能な数式のvalidate

MonoxerではCSV形式でBookやMiniTestを作成できます。この時に採点方法を指定するのですが、たとえば数値計算モードが設定されているのに正解の数式が数値評価できない数式だった時、それは作問ミスである可能性が高そうです。そういった時に警告を出してあげることで、作問者がミスに気づくことができます。

数値計算モードが指定されたエントリの登録時に数値評価ができるかどうかをフロント側で判定し、できなかった場合は登録できないようにしました。

正解が順不同な時の正誤判定

たとえば、

「 $60$ の約数を全て列挙してください。正解: $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ 」

という問題について、順序を入れ替えたものは全て正解としたいです。しかし、この場合順序の入れ替えは $12! = 479,001,600$ 個あり、これらを全て別解として登録することは非現実的です。今までは答えが一意になるように問題文を工夫し、この問題では「昇順で解答してください」と問題文に入れることで対応していたのですが、順不同な時にもうまく動作するようにしました。