「正解が分からない」アルゴリズムをどうテストするか

この記事は Hacobell Developers Advent Calendar 2025 の18日目の記事です。

こんにちは。ハコベルの上島です。

実務において機械学習や数理最適化を扱ったソフトウェアを開発していると、「アルゴリズムの正当性をどう検証するか」という壁に直面します。なぜなら、機械学習モデルの予測結果や数理最適化アルゴリズムは、事前に「正解」を定義することが困難なケースが多いためです。

こうした状況下で、私たちはどのようにしてソフトウェアの品質を保証すればよいのでしょうか？

オラクル問題

ソフトウェアテストにおいて、「入力に対して期待される正しい出力」を判定するための情報源を オラクル と呼びます。通常のテストでは、事前に用意した期待値そのものがオラクルとして機能します。

# 通常のテスト：オラクルが存在する（期待値が[1, 2, 3]であることが分かっている）
def test_sort():
    assert sort([3, 1, 2]) == [1, 2, 3]

一方で、このオラクルが存在しない、あるいは用意するコストが極めて高い問題を 「オラクル問題」 と呼びます。

# オラクル問題：オラクルが存在しない（期待値が事前に分からない）
def test_complex_algo():
    input_data = ...
    # オラクルを用意できない関数
    output = run_algorithm(input_data)
    # 期待値が不明なため単純に比較できない
    assert output == ???

オラクル問題が顕在化するケース

実務では、主に以下のような状況でオラクル問題に直面します。

1. 評価基準が曖昧

• 機械学習モデルの予測結果（文字認識、クラス分類など）
• 画像処理（フィルタリング、超解像など）
• 自然言語処理（テキスト要約、翻訳など）

2. 出力が非決定的

• 乱数を使うシミュレーション（モンテカルロ法など）
• 確率的アルゴリズム（焼きなまし法、遺伝的アルゴリズムなど）

3. 計算コストが高すぎる

• 組合せ最適化問題（巡回セールスマン問題、ナップサック問題など）
• 大規模グラフの処理（最短経路、全域木など）

---

こうしたオラクル問題に対処するために、本記事では以下の3つのテスト手法を紹介します。

• Property-based Testing：あらゆる入力に対して出力が満たすべき共通の性質を検証する手法
• Metamorphic Testing：入力を変化させたとき、出力がどう変化すべきかという関係性を検証する手法
• Intramorphic Testing：実装を変化させたとき、出力がどう変化すべきかという関係性を検証する手法

それぞれの手法について、具体例と実装パターンを交えて見ていきます。

本記事で登場する実装例ではPythonの Hypothesis ライブラリを使用しています。

Property-based Testing

Property-based Testingは、あらゆる入力に対して出力が満たすべき共通の性質を検証するブラックボックステスト手法です。

「個別の入力に対する正解は分からないが、出力全体が守るべきルールは分かっている」という点に着目します。

具体例と実装パターン

例1: 暗号化

暗号化アルゴリズムの期待値を知らなくても、次のような性質は検証できます：

• 可逆性: 暗号化→復号で元に戻る
• 決定性: 同じ平文とキーであれば常に同じ暗号文が生成される

※ここでは説明のため、決定性をもつ暗号化アルゴリズムを想定しています。

from hypothesis import given, strategies as st

def encrypt(plaintext: str, key: str) -> str:
    """平文を暗号化する"""
    ...

def decrypt(ciphertext: str, key: str) -> str:
    """暗号文を復号する"""
    ...

@given(
    # ランダムな平文とキーを生成
    st.text(min_size=1, max_size=100),
    st.text(min_size=8, max_size=32)
)
def test_encryption(plaintext: str, key: str):
    """暗号化アルゴリズムの性質を検証"""
    ciphertext = encrypt(plaintext, key)
    decrypted = decrypt(ciphertext, key)

    # 性質1: 可逆性
    assert decrypted == plaintext

    # 性質2: 決定性
    assert ciphertext == encrypt(plaintext, key)

例2: クラスタリング

クラスタリングの期待値を知らなくても、次のような性質は検証できます：

• 完全性: 全てのデータ点がいずれかのクラスタに割り当てられている
• 排他性: 各データ点は一つのクラスタにのみ割り当てられている
• 非空性: 各クラスタには少なくとも一つのデータ点が含まれている

from hypothesis import given, strategies as st

def kmeans(points: list[tuple[float, float]], k: int) -> list[list[int]]:
    """K-meansクラスタリングを実行"""
    ...

@given(
    # 平面上のランダムな点群を生成
    st.lists(
        st.tuples(
            st.floats(min_value=0, max_value=100), 
            st.floats(min_value=0, max_value=100)
        ),
        min_size=10,
        max_size=100
    ),
    # クラスタ数kを2から10の範囲で生成
    st.integers(min_value=2, max_value=10)
)
def test_clustering(points: list[tuple[float, float]], k: int):
    """クラスタリングアルゴリズムの性質を検証"""
    clusters = kmeans(points, k)

    # 性質1: 完全性
    assigned = {idx for cluster in clusters for idx in cluster}
    assert assigned == set(range(len(points)))

    # 性質2: 排他性
    total = sum(len(cluster) for cluster in clusters)
    assert total == len(points)

    # 性質3: 非空性
    assert all(len(cluster) > 0 for cluster in clusters)

Metamorphic Testing

Metamorphic Testingは、入力を変化させたとき、出力がどう変化すべきかという関係性を検証するブラックボックステスト手法です。

「ある入力 $A$ に対する正解は分からないが、入力 $A$ を少し変えた入力 $A'$ に対する出力との差分や関係は予測できる」という点に着目します。

具体例と実装パターン

例1: 統計量計算（順序不変性）

データの順序を変えても統計量は同じであること（順序不変性）を検証します。

import random
from hypothesis import given, strategies as st

def compute_mean(data: list[float]) -> float:
    """平均値を計算"""
    ...

def compute_variance(data: list[float]) -> float:
    """分散を計算"""
    ...

@given(
    # ランダムな実数列を生成
    st.lists(
        st.floats(min_value=-1e6, max_value=1e6),
        min_size=5,
        max_size=100
    )
)
def test_statistics(data: list[float]):
    """統計量計算の順序不変性を検証"""

    mean1 = compute_mean(data)
    variance1 = compute_variance(data)

    # データをシャッフル
    shuffled = data.copy()
    random.shuffle(shuffled)

    mean2 = compute_mean(shuffled)
    variance2 = compute_variance(shuffled)

    # 順序によらず統計量は同じ
    # 丸め誤差を考慮して比較
    assert abs(mean1 - mean2) < 1e-10
    assert abs(variance1 - variance2) < 1e-10

例2: コサイン類似度（スケール不変性）

ベクトルをスケーリングしても、コサイン類似度は不変であること（スケール不変性）を検証します。

from hypothesis import given, strategies as st

def cosine_similarity(vec_a: list[float], vec_b: list[float]) -> float:
    """コサイン類似度を計算"""
    ...

@given(
    # ランダムな2次元ベクトルのリストを生成
    st.lists(
        st.tuples(
            st.floats(min_value=-1e3, max_value=1e3), 
            st.floats(min_value=-1e3, max_value=1e3)
        ),
        min_size=5,
        max_size=50
    )
)
def test_cosine(data: list[tuple[float, float]]):
    """コサイン類似度のスケール不変性を検証"""
    vec_a = [d[0] for d in data]
    vec_b = [d[1] for d in data]

    similarity1 = cosine_similarity(vec_a, vec_b)

    # ベクトルをスケーリング
    scaled_a = [v * 5 for v in vec_a]
    scaled_b = [v * 100 for v in vec_b]

    similarity2 = cosine_similarity(scaled_a, scaled_b)

    # スケール変換しても結果は同じ
    assert abs(similarity1 - similarity2) < 1e-10

例３: ジオコーディング（ロバスト性）

住所が表記揺れを含んでいても得られる座標が近いこと（ロバスト性）を検証します。

def geocode(address: str) -> tuple[float, float]:
    """住所を緯度経度に変換"""
    ...

def haversine_distance(coord1: tuple[float, float], coord2: tuple[float, float]) -> float:
    """球面上の2点間の最短距離を計算"""
    ...

def test_geocoding():
    """ジオコーディングの表記揺れロバスト性を検証"""
    address1 = "東京都渋谷区道玄坂1-2-3"
    address2 = "東京都　渋谷区　道玄坂　１－２－３"

    coord1 = geocode(address1)
    coord2 = geocode(address2)

    # 表記揺れでも座標が近い（100メートル以内）
    distance = haversine_distance(coord1, coord2)
    assert distance < 100

Metamorphic Testingで検証できる関係性（メタモルフィック関係）の例として、以下のようなものがあります：

• 順序不変性: 入力の順序を変えても結果は同じ
• スケール不変性: 入力をスケーリングしても結果は同じ
• 加法性: 入力を分割して処理した結果を合成できる
• 単調性: 入力が増加すれば出力も増加する（またはその逆）
• 対称性: 対称な入力変換に対して出力も対称に変化
• 可換性: 複数の操作の順序を変えても結果は同じ
• ロバスト性: 入力の微小な変化に対して出力が大きく変化しない

Intramorphic Testing

Intramorphic Testingは、実装を変化させたとき、出力がどう変化すべきかという関係性を検証するホワイトボックステスト手法です^[1]。

「ある入力 $A$ に対する正解は分からないが、実装 $P$ を少し変えた実装 $P'$ に対する出力との差分や関係は予測できる」という点に着目します。

具体例と実装パターン

例1: ソートアルゴリズム

ソート関数の比較ロジックを反転させた変種を作り、結果の関係性を検証します。

def my_sort(data: list[int], ascending: bool = True) -> list[int]:
    """ソートを実行"""
    ...

def test_sort():
    """ソートの実装変更による関係性を検証"""
    data = [3, 1, 4, 1, 5, 9, 2, 6]

    # 昇順ソート
    asc = my_sort(data, ascending=True)

    # 実装変更: 降順ソート
    desc = my_sort(data, ascending=False)

    # 降順は昇順の逆順
    assert desc == list(reversed(asc))

例2: モンテカルロ法

モンテカルロ法のサンプル数を変えた変種を作り、サンプル数が増えると精度が向上することを検証します。

def estimate_pi_monte_carlo(n_samples: int, seed: int | None = None) -> float:
    """モンテカルロ法でπを推定"""
    ...

def test_monte_carlo():
    """モンテカルロ法のサンプル数と精度の関係を検証"""
    true_pi = 3.141592653589793

    # 少ないサンプル数で実行
    est_small = estimate_pi_monte_carlo(n_samples=1000, seed=42)
    est_large = estimate_pi_monte_carlo(n_samples=100000, seed=42)

    error_small = abs(est_small - true_pi)
    error_large = abs(est_large - true_pi)

    # サンプル数を増やすと精度が向上
    assert error_large < error_small

確率的挙動を含んだソフトウェアのより厳密なテストでは、複数回の実行による平均誤差を比較するなど、統計的な検証手法を用いるなどの工夫が必要になる場合もあります^[2]。

おわりに

本記事では、「正解が分からない」アルゴリズムのテスト手法として、Property-based Testing、Metamorphic Testing、Intramorphic Testingの3つを紹介しました。

3つの手法の違いを再度整理すると以下のようになります。

手法	何を検証するか
Property-based Testing	あらゆる入力に対して出力が満たすべき共通の性質
Metamorphic Testing	入力を変化させたとき、出力がどう変化すべきかという関係性
Intramorphic Testing	実装を変化させたとき、出力がどう変化すべきかという関係性

「正解」そのものを検証するのではなく、性質や関係性に着目することで、オラクル問題に対処できます。実際のプロジェクトでは、これらを組み合わせることで、より堅牢なテスト戦略を構築できるでしょう。

脚注

1. Intramorphic Testing: A New Approach to the Test Oracle Problem - Speaker Deck

2. データサイエンティストのための確率的挙動を含むソフトウェアテスト - Zenn