正解がわからないコードはどうテストする？

機械学習モデルをリリースした。サポートチケットにラベルを付与するものだ。テストスイートはグリーンだ。すべてのテストが通過した。

どのテストも、ラベルが正しいかどうかはチェックしていない。正しいラベルが何かはわからない。誰にもわからない。「正しい」出力は現実世界の入力に対して実質的に不可知なので、関数がクラッシュしないか、出力の形が期待通りかを確認するにとどまっている。それはテストではない。希望を持っているだけだ。

これがoracle problemだ。コンパイラー、シミュレーション、最適化アルゴリズム、不正検出器、ground truthが高価で主観的、あるいは計算不可能なあらゆるシステムで現れる。期待される出力を定義できないとき、従来のunit testは崩壊する。

Metamorphic testingは出口を提供する。「この出力は正しいか？」と尋ねるのではなく、「関連する入力が、既知の関係性を満たす出力を生成するか？」と尋ねるのだ。そうでなければ、コードは壊れている。そうであれば、正解を知らなくても実質的な信頼を得られる。

Metamorphic testingとは何か

Metamorphic testingは、1990年代後半にTsong Yueh Chenらによって提案された。frustratingな現実への回答だった：多くのプログラムは本当に有用だが、従来のoracleでは実質的にテスト不可能なのだ。

核となるアイデアは単純だ。metamorphic relation を特定する：プログラムの複数回の実行の入力と出力の間に成り立つはずの性質だ。ソース入力でプログラムを実行し、その入力をrelationに従って変換し、再度実行して、出力がpropertyが予測する通りに互いに関係しているかをチェックする。

期待される出力は不要だ。人間のラベラーは不要だ。ゴールデンデータセットは不要だ。

重み付きグラフで最短経路を見つける関数を考えてみよう：

from typing import List, Tuple, Optional

def shortest_path(
    edges: List[Tuple[int, int, float]],
    start: int,
    end: int
) -> Optional[float]:
    """Dijkstra's algorithm. Returns path length or None if unreachable."""
    import heapq

    graph = {}
    for u, v, w in edges:
        graph.setdefault(u, []).append((v, w))

    dist = {start: 0.0}
    heap = [(0.0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if u == end:
            return d
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return None

複雑なグラフの最短経路を手で計算するのは面倒だ。しかし、いくつかのmetamorphic relationsが成り立つことはわかっている：

エッジ重みに対する単調性。 単一のエッジ重みを増加させれば、最短経路は短くならないはずだ。同じまま（そのエッジが最適経路上にない場合）か、長くなるかのどちらかだ。
正の定数倍下での同次性。 すべてのエッジ重みを正の定数で掛ければ、最短経路長も同じ定数だけスケールするはずだ。
無向グラフでの経路対称性。 グラフが無向なら、startとendを入れ替えれば同じ経路長が得られるはずだ。

これらはヒューリスティックではない。数学的性質だ。いずれかが失敗すれば、実装は間違っている。議論の余地はない。

Metamorphic testの書き方

単調性のrelationが実際にどう見えるか、以下に示す：

import random

def test_shortest_path_monotonicity():
    # Generate a random connected graph
    nodes = list(range(10))
    edges = []
    for i in range(len(nodes) - 1):
        edges.append((i, i + 1, random.uniform(1.0, 10.0)))
    # Add some random cross edges
    for _ in range(10):
        u, v = random.sample(nodes, 2)
        edges.append((u, v, random.uniform(1.0, 10.0)))

    start, end = 0, 9
    original = shortest_path(edges, start, end)
    assert original is not None

    # Increase the weight of one arbitrary edge
    idx = random.randrange(len(edges))
    u, v, w = edges[idx]
    modified_edges = list(edges)
    modified_edges[idx] = (u, v, w + 5.0)

    modified = shortest_path(modified_edges, start, end)
    assert modified is not None
    assert modified >= original

このテストは、期待される最短経路を一度も計算しない。必要ない。構造的性質が成り立つかをチェックするだけで、驚くほど多様なバグを捉えられる：符号エラー、重みの累積におけるoff-by-oneミス、不正なpriority queueの順序付け、など。

スケーリングのrelationはさらに簡単にテストできる：

def test_shortest_path_scaling():
    nodes = list(range(8))
    edges = []
    for i in range(len(nodes) - 1):
        edges.append((i, i + 1, random.uniform(2.0, 5.0)))

    start, end = 0, 7
    original = shortest_path(edges, start, end)

    factor = 3.5
    scaled_edges = [(u, v, w * factor) for u, v, w in edges]
    scaled = shortest_path(scaled_edges, start, end)

    assert abs(scaled - original * factor) < 1e-9

浮動小数点の許容誤差に注目してほしい。Metamorphic testsも数値精度の問題から免れないので、他の数値テストと同じ注意を払ってアサーションを書く。

このアプローチが実際に役立つ場面

Metamorphic testingは、従来のoracleが弱いか存在しない領域で輝く。

機械学習。 映画レビューの正確なsentiment scoreはわからないが、「terrible」という単語を追加してポジティブなsentimentが増加しないことはわかっている。物体検出器の正確なbounding boxはわからないが、画像を水平方向に反転すればbounding boxの座標も反転するはずだ。

コンパイラー。 最適化されたバイナリが、あらゆる可能なプログラムに対して未最適化のものと完全に同じ出力を生成することを検証するのは不可能だ。しかし、プログラムをコンパイルしてから、no-op変換（変数名の変更など）を施して再コンパイルし、意味的に等価なバイナリが生成されることを確認できる。

科学技術計算。 複雑なシミュレーションにおける粒子の正確な軌道はわからないが、時間を反転すれば軌道も反転するはずだ。分子の正確な基底状態エネルギーはわからないが、基底集合のサイズを増やせば、それは減少する（あるいは一定のままである）はずだ。

どの場合も、洞察は同じだ：正しさは、常に単一の期待値と一致することを意味するわけではない。変換を通じて構造を保持することを意味することもある。

トレードオフと限界

Metamorphic testingは無償ではなく、あらゆる種類のテストの代替ではない。

Relationsは不完全になりうる。 定義したmetamorphic relationをすべて満たしていても、プログラムが間違っている可能性がある。relationセットが特定のバグクラスをカバーしていなければ、そのバグはすり抜ける。これがカバレッジ問題であり、現実のものだ。

Relationsは誤りである可能性がある。 成り立たない性質を成り立つと誤ってアサートすれば、テストは誤検出の工場になる。かつて、k-meansクラスタリングがfeature scalingに対して不変であるべきだと主張するチームを見た。そうではない。centroidはデータとともにスケールする。テストは数か月間パスしていた。なぜならテストデータではスケーリング係数が偶然1.0だったからだ。実データが到着すると、モデルは静かに劣化したのに、テストはグリーンのままだった。

デバッグは難しい。 従来のunit testが失敗したとき、期待される出力が何だったか正確にわかる。Metamorphic testが失敗したとき、relationが違反されたことはわかるが、正しい出力は依然としてわからない。Property violationから根本的なバグへ逆方向に推論する必要があり、それはより多くの作業を要する。

テストデータ生成は重要だ。 ランダムなグラフ、ランダムな文章、ランダムな画像は、実際の入力を代表していない。合成データに対するmetamorphic testはパスするのに、本番システムはgeneratorが生成しなかったエッジケースで失敗する可能性がある。Hypothesisのようなproperty-based testingライブラリを使うと役立つが、自分のgeneratorに対しては懐疑的でいよう。

今日から使い始める方法

新しいフレームワークは不要だ。3つのものだけが必要だ：

Oracleが弱い関数を1つ選ぶ。 モデルの推論メソッド、幾何計算、シミュレーションステップなど。今は「クラッシュしない」ことをテストしていて、もっとやりたいと思っているもの。
3つのrelationをブレインストーミングする。 どの変換が出力を変えないはずか？どの変換が予測可能な方法で出力を変えるはずか？どの入力のペアが関連した出力を生成するはずか？自明に思えても、書き留めておく。
1つのrelationをテストとして実装する。 ランダム化された入力で実行する。失敗すれば、バグを見つけたか、間違ったrelationを定義したかのどちらかだ。どちらも価値がある。

先ほど述べたk-meansの例では、正しいrelationセットはこうなる：

import numpy as np
from sklearn.cluster import KMeans

def test_kmeans_translation_invariance():
    X = np.random.rand(100, 3)
    shift = np.array([10.0, -5.0, 2.0])

    km1 = KMeans(n_clusters=3, random_state=42, n_init=10).fit(X)
    km2 = KMeans(n_clusters=3, random_state=42, n_init=10).fit(X + shift)

    # Centroids should differ by exactly the shift vector
    np.testing.assert_allclose(km1.cluster_centers_ + shift, km2.cluster_centers_)

このテストは、クラスタリングのロジックが座標系を誤って扱うと失敗し、正しいcentroidが何であるかをアサートすることなくそれを実現する。

答えがわからないときは、構造をテストする

Oracle problemは、テストのエッジケースではない。有用なソフトウェアの巨大なクラスにとってのデフォルト状態だ。Metamorphic testingは完全には解決しないが、「テストできない」から「重要な性質はテストできる」へと移行させてくれる。

1つのrelation、1つの関数、1つ捕捉した実際のバグから始めよう。それだけでアプローチを正当化するに十分だ。あとはrelationを追加するだけだ。