ナレッジグラフ1050ノードを作って踏んだ3つの罠

ノード 1,050・エッジ 2,261 のナレッジグラフを組みました。作業そのものは単純です。ノードとエッジを何にするかを決めて、元データを読み替えるだけなので半日で終わります。

詰まったのは全部「関係が一意に決まらない場所」でした。 3種類あって、どれも元データを眺めているだけでは見えません。組んで、クエリを投げて、答えが変なので戻る、という順でしか見つかりませんでした。

そして3つ目は、実験の結果を丸ごと捨てさせました。

題材

マインクラフト (Minecraft) のクラフトレシピです。作りたいものと材料の関係が、ゲーム自身から機械可読な形で配られています。

理由は1つ、答え合わせができるからです。組んだグラフが正しいかどうかを、人が読んで判断するのではなく機械で検算できます。文書からエンティティを取り出すタイプのグラフに、この性質はありません。

グラフの形は最小限にしました。ノードは Item 1種類、エッジは INGREDIENT_OF 1種類だけです。種類を増やす前に、1種類で問いに答えられるかを確かめます。

(トウヒの原木) -[:INGREDIENT_OF]-> (トウヒの木材) -[:INGREDIENT_OF]-> (トウヒの階段)

罠1: 循環

最初に壊れたのは鉄でした。

鉄インゴット 9個  →  鉄ブロック 1個
鉄ブロック 1個   →  鉄インゴット 9個
鉄インゴット 1個  →  鉄ナゲット 9個
鉄ナゲット 9個   →  鉄インゴット 1個

エッジが両方向に張られています。 「鉄インゴットの材料を辿れ」と言うと、ブロックとナゲットの間を永遠に往復します。

素朴な対処は「一度通ったノードは通らない」でしょう。ところがそれだと辿る順番で答えが変わります。先にブロックへ行けば材料はブロック、先にナゲットへ行けばナゲットになり、どちらも間違いです。

採った方法は、探索中のスタックに載っているノードを要求するレシピを、選択肢から外すというものです。

鉄インゴットを展開する
  レシピA (鉄ブロックから) → 鉄ブロックは鉄インゴットを要求する → 却下
  レシピB (ナゲット9個から) → ナゲットは鉄インゴットを要求する → 却下
  全部却下 → 鉄インゴットは「これ以上たどれないもの」として扱う

そしてこの結果が現実と合っています。 鉄インゴットは実際には鉱石を精錬して得るもので、クラフトの段数に数えるべきではありません。循環を正しく処理すると、正しい答えが落ちてきました。

循環には、もっと短いものもあります。自分自身を材料に含むレシピです。

防具の鍛冶型 + ダイヤ + ブロック  →  防具の鍛冶型 2個

型を複製するレシピなので、材料に型そのものが入っています。長さ1の循環です。こういうものが 19件あり、レシピを全部外すと材料が空になるので、原材料として扱っています。

罠2: 分岐

次に壊れたのは木材でした。

「黒いベッド」の材料は羊毛と木材ですが、木材は6種類のどれでもよく、羊毛の色も染料で変わります。素朴に組むと、こういう答えが出ます。

黒いベッド → 青い羊毛, サクラの原木, イカスミ

サクラである必然性はありません。 実装が最初に見つけた枝を返しているだけです。

ここでの判断は「どれか1つを選ぶ」ではありませんでした。正解が一意に決まらないものは、正解データから外す、にしました。材料の組み合わせが2通り以上あるアイテムを全部落とすと、887件のうち 439件が消えます。半分近くです。

削りすぎに見えますが、外さないと後で高くつきます。この実験は「モデルの答えが正しいか」を採点するものなので、正解が一意でないと、モデルの正しい別解を誤りと数えてしまいます。

罠3: どこで止めるか

3つ目が一番危なく、そして一番気づきにくいものでした。

グラフを辿るのをどこでやめるか。素朴には「これ以上クラフトできないところ」ですが、その定義が曖昧です。

石       丸石を精錬して作る          → クラフトではない。止まる?
ガラス    砂を精錬して作る            → 同上
レンガ    粘土を精錬して作る          → 同上
原木     木を切って手に入れる         → 止まる
ダイヤ    採掘して手に入れる          → 止まる

私はデータ側で「クラフトのレシピが無いもの」を葉にしました。石もガラスもレンガもクラフトのレシピが無いので、そこで止まります。

そして質問文には「クラフトできないものまで展開してください」と書きました。 一致しているように見えます。

一致していませんでした。モデルはこう答えました。

石の感圧板   こちらの正解 石        モデル 丸石     ← 石は丸石を精錬して作る
ガラス瓶     こちらの正解 ガラス     モデル 砂       ← ガラスは砂を精錬して作る
レンガ       こちらの正解 レンガ     モデル 粘土玉

モデルのほうが正しく、1段深く展開していました。 「クラフトできないもの」を言葉どおりに取れば、石は丸石から作れるので葉ではありません。私の正解データが、自分で書いた定義を守っていませんでした。

気づいたきっかけは、成績が不自然に低かったことでした。一番簡単なはずの1段の問題で、一番大きいモデルが37%しか取れていない。変です。中身を開いたら、モデルの正解を不正解として数えていました。

直したのは2つです。質問文に止まる場所を例つきで書くこと。そして「実は作れるもの」が葉に混ざる問題 (小麦9個 ⇄ 干草の俵のような圧縮ペア) を、さらに57件外すこと。

そのうえで、それまでの結果を全部捨てて回し直しました。

曖昧なものは捨てずに、印を付けて載せる

ここまでで 515 件を「正解データから外す」と書きましたが、グラフからは外していません。

正解データ (datasets/)   厳しく絞る。372件だけ
グラフ (Neo4j)          全部載せる。1,050ノード。
                        外した分には unambiguous: false を立てる

グラフ側で「作れるもの」として数えられるのは 868 件です (887 から、材料が自分だけになる19件を引いた数)。そのうち 372 件が一意で、残り 496 件は材料が一意に決まりません。 後者も印を付けて載せています。

役割が違うので、同じ基準で絞る必要はありません。そして、解決できない箇所を隠すより、明示するほうが安全です。

グラフを使う側から見ると、この差は大きいです。曖昧なものを消したグラフは「そんなアイテムは無い」と答えます。印を付けて残したグラフは「あるが、材料が一意に決まらない」と答えられます。無いことと分からないことが、同じ表示になってはいけません。

検算

最後に、組んだものが正しいかを確かめました。

同じ「原材料まで展開する」計算を、2つの実装で行います。片方は Python の再帰で、循環の除外を自前で書いたもの。もう片方は Cypher の可変長パスで、グラフDB に任せたものです。

MATCH p = (leaf:Item)-[:INGREDIENT_OF*]->(t:Item {name: $name})
WHERE NOT (:Item)-[:INGREDIENT_OF]->(leaf)
RETURN DISTINCT leaf.name, min(length(p))

372件すべてで一致しました。不一致は0件です。

これで落とせるのは「実装依存の間違い」です。片方だけが持っているバグなら、答えが割れます。割れなかったので、少なくとも2つの独立した書き方が同じ結論に至っていることは言えます。

題材に答え合わせのできるものを選んだ効果が、ここで出ます。 文書から抽出したグラフでは、この検算ができません。正しさを人が読んで判断するしかなくなります。

まとめると

作る手間は大したことがありません。難所は3つとも「関係が一意に決まらない場所」に集中しています。

循環        辿る順番で答えが変わる    → 探索中のノードを要求する枝を外す
分岐        正解が複数ある            → 一意でないものは正解データから外す
葉の定義    どこで止めるかが曖昧      → 例つきで定義を書き、両側で揃える

そして3つ目は、気づくのが遅れると測定結果ごと無効になります。 気づいたきっかけは「数字が不自然だった」ことでした。組んだあと、成績が想定と違ったら、モデルを疑う前に自分の正解データを開いてください。

グラフDB への載せ方と、そこで書けるクエリは次の章で扱います。

---

Minecraft は Mojang Synergies AB の商標です。このページは Mojang Studios および Microsoft とは無関係で、承認も後援も受けていません。クラフトデータは PrismarineJS/minecraft-data から取得しています。