Hypothesisを用いたテスト最適化の探求
0
以下の文章はこちらの記事を翻訳したものです。https://github.com/HypothesisWorks/hypothesis/blob/master/HypothesisWorks.github.io/_posts/2016-05-29-testing-optimizers-with-hypothesis.md
以前、Hypothesisを使ったテストパフォーマンスの最適化のについて触れましたが、今回はまったく異なるアプローチを紹介します。ここでは、ある値を最適化するために設計されたコードをどのようにテストするかに焦点を当てます。つまり、特定の関数が与えられたときに、その関数の出力を最大化（または最小化）する引数を見つけることが目標です。
このテーマは非常に興味深いものであり、Hypothesisの**data()ストラテジーの使用方法を示す絶好の機会です。data()**ストラテジーを利用することで、テスト開始後に追加のデータを取り込むことができます。これにより、多様な状況におけるテストの質を大幅に向上させることが可能です。
具体例として、ナップサック問題を取り上げてみましょう。ここでは、Wikipediaに記載されている貪欲近似アルゴリズム用いて、Hypothesisを使って、それが単なる近似であり、実際には最適解でないことを示します。
ナップサック問題を解決する関数は以下の通りです。
def pack_knapsack(items, capacity):
"""与えられたアイテムのリスト[(value, weight)]について、valueとweightは厳密に正の整数で、
合計重量がcapacity以下であるアイテムの最大価値サブセットを見つけることを試みる"""
remaining_capacity = capacity
result = []
# 単位重量あたりの価値が低下する順に並べ替える。同じ場合は、より軽いアイテムを優先する。
items = sorted(items, key=lambda x: (x[1] / x[0], x[1]))
for value, weight in items:
if weight <= remaining_capacity:
result.append((value, weight))
remaining_capacity -= weight
return result
では、この関数をどのようにテストすればよいでしょうか？他の最適化手法が存在すれば、2つの結果を比較することができます。しかし、それがない場合は、特定の特性を見つけてその特性をテストする必要があります。
テストの要点は、関数に加えられた変更がどのように結果に反映されるかを観察することです。つまり、まず関数を実行し、その出力に影響を与えると思われるデータの変更を行った後、もう一度関数を実行して、実際に何か変化が生じたかどうかを確認します。
それでは、どのような変更を加えるべきでしょうか？重要なのは、最適化アルゴリズムの実行結果を分析し、その結果に基づいて変更を加えることです。具体的には、以下の2つの特性をテストすることです。
- 最適解の一部として以前に選択されたアイテムを削除する: 最適解の一部であったアイテムを削除した場合、スコアが向上しないはずです。これにより、元の解が実際に最適であるかを確認することができます。
- 最適解の一部として以前に選択されたアイテムの追加コピーを加える: 既に選択されているアイテムの追加コピーをナップサックに加えた場合、スコアが悪化することはないはずです。このテストは、アルゴリズムがアイテムの重複を適切に処理しているかを確認します。
以下にテストのコード例を示します。
from hypothesis import given, strategies as st
def score_items(items):
return sum(value for value, _ in items)
PositiveIntegers = st.integers(min_value=1, max_value=10)
Items = st.lists(st.tuples(PositiveIntegers, PositiveIntegers), min_size=1)
Capacities = PositiveIntegers
@given(Items, Capacities, st.data())
def test_cloning_an_item(items, capacity, data):
original_solution = pack_knapsack(items, capacity)
assume(original_solution)
items.append(data.draw(st.sampled_from(original_solution)))
new_solution = pack_knapsack(items, capacity)
assert score_items(new_solution) >= score_items(original_solution)
@given(Items, Capacities, st.data())
def test_removing_an_item(items, capacity, data):
original_solution = pack_knapsack(items, capacity)
assume(original_solution)
item = data.draw(st.sampled_from(original_solution))
items.remove(item)
new_solution = pack_knapsack(items, capacity)
assert score_items(new_solution) <= score_items(original_solution)
（整数に対するmax_valueパラメータは必須ではありませんが、設定することでより良質な例が得られます。）
dataストラテジーは、テスト中に動的にデータを生成するために使用されます。これにより、関数の実行結果に基づいて、その場で適切な選択を行うことが可能になります。テストが失敗した場合、どのようなデータが生成されたかが追加情報として表示されます。
実際、以下の二つのテストでは失敗が確認されました。
Falsifying example: test_cloning_an_item(items=[(1, 1), (1, 1), (2, 5)], capacity=7, data=data(...))
Draw 1: (1, 1)
この例では、Hypothesisは価値と重量が共に1のアイテムを複数回選択しました。この結果、アルゴリズムがナップサックに3つの(1, 1)のアイテムを詰め込むことになります。しかしこの操作によって、ナップサックにはまだ空き容量が残っているにもかかわらず、適したサイズの小さいアイテムが不足してしまいました。
Falsifying example: test_removing_a_chosen_item(items=[(1, 1), (2, 4), (1, 2)], capacity=6, data=data(...))
Draw 1: (1, 1)
反対のケースでは、貪欲法を用いたアルゴリズムが最初に(1, 1)のアイテムを選択し、結果として他の2つのアイテムのうち1つしかナップサックに入れられなくなりました。Hypothesisがこのアイテムを取り除くと、ナップサックには残りの2つのアイテムが収まり、結果的により高い合計スコアを獲得することができました。
これらの失敗例は、ある程度予想されたものです。Wikipediaで「貪欲法では（ナップサック問題の）最適解を得られない」と説明されているように、ここで取り扱っている小規模なナップサックのケースでは、貪欲法に基づく近似アルゴリズムは実際にはそれほど効果的ではありません。Hypothesisを使用することで、そのような不備が容易に明らかになります。
この手法の応用範囲はもっと広いです。例えば、ユーザーの権限や設定を変更して選択肢を増やしたり、サブシステムの容量を拡大してタスクの割り当てを増やしたりするなど、様々なシチュエーションで利用することが可能です。
関連記事
関連記事
