Provably Lossless Acceleration of DNN Mutation Testing via Memoization

ロボットに猫を認識させる方法を教えていると想像してみてください。あなたは、何千枚もの写真から学習する、小さなスイッチ（ニューロン）の層で作られた巨大で複雑な脳を構築しました。しかし、そのロボットが本当に賢いのか、それとも単に運が良いだけなのか、どうすればわかるでしょうか？ソフトウェアテストの世界には、「ミューテーション・テスティング（変異テスト）」と呼ばれる巧妙なトリックがあります。それは、あえてロボットの脳を、スイッチを一つ反転させたり、ワイヤーを一つねじったりといった、ランダムで小さな方法で壊してみる「間違い探し」のようなゲームです。もし、脳を壊した後でもロボットが犬を猫だと判断してしまうなら、あなたのテストは役割を果たせていないことになります。

問題は、このゲームが信じられないほど遅く、コストがかかることです。現代的なロボットの脳をテストしようとすると、一つの故障に対して、数千回脳を壊し、数百万枚の画像を通さなければならないかもしれません。それは、まるで一本の藁（わら）を壊しては全体をチェックするという作業を、何度も何度も繰り返して、干し草の山全体を作り直しながら針を探すようなものです。多くの人々は、これを加速させるために、結果を推測するというショートカットを使って「ズル」をしてきました。しかし、科学において推測を行うことはリスクを伴います。もし推測を間違えれば、実際には壊れているのに、ロボットは安全であると誤認してしまう可能性があるからです。この論文は、高速でありながら、決してズルをしない、新しいゲームの遊び方を紹介しています。

ロボットの脳のための「コピー＆ペースト」の近道

Mure（「ムーレイ」と発音します）をご紹介しましょう。これは、Ali Ghanbari、Ben Greenman、Sasan Tavakkol、そしてShibbir Ahmedの研究者たちによって設計された、新しいツールです。ディープニューラルネットワーク（ロボットの脳）を、工場の長い組立ラインと考えてみてください。原材料（画像）が入り、多くのステーション（層）を通過し、完成品（答え）となって出てきます。

ラインの最後にある機械を壊して工場をテストしたいとき、毎回工場全体をゼロから作り直す必要はありません。壊れた機械と、その後の数少ないステーションだけを修正すればよいのです。故障箇所の前のステーションは、元の工場と全く同じなのです。

Mureは、**メモ化（memoization）**という技術を使用しています。これは、「既に行ったことを記憶する」という、少し凝った言葉です。現実世界での仕組みは以下の通りです：

1. 組立ライン： 100種類の少しずつ異なるおもちゃの車を作る工場を想像してください。そのうち99個において、最初の10ステップの組立工程は同一です。最後の2ステップだけが異なります。
2. 従来の方法（バニラ・テスティング）： 古い方法では、あらゆるバージョンに対して、最初からおもちゃの車を丸ごと作り直します。最初の10ステップを実行し、次に最後の2ステップを実行し、また最初に戻って最初の10ステップを再び実行し、また最後の2ステップを実行する……という具合です。これは膨大なエネルギーの無駄です。
3. Mureの方法： Mureはこう言います。「ちょっと待って！最初の10ステップは全員同じだ」。そこで、Mureは最初の10ステップを一度だけ実行し、その結果を「メモ・テーブル（壁に貼った付箋のようなもの）」に保存します。そして、個々の変異した車に対しては、その付箋を手に取り、最初の10ステップをスキップして、最後の2ステップだけを組み立てるのです。

大発見：ズルをしないスピードアップ

研究者たちは、Mureが数学的に**「ロスレス（情報の損失がない）」であることを証明しました。これが最も重要な部分です。過去には、他のツールが、エラーを見逃す可能性のあるショートカット（「ロシー（情報の損失がある）」な方法）を使って高速化を図っていました。それらは、塩加減を確認せずにスープを味わうシェフのようなものでした。Mureは違います。Mureは、毎回重さを量る代わりに、あらかじめ計量されたカップを使うことで、元のレシピと全く同じ方法**で塩を確認するシェフなのです。

この論文は、Mureが、あの遅くて退屈な「すべてをゼロから行う」方法と全く同じ結果を生み出すことを証明しています。Mureは壊れたロボットを見逃すことはありません。ただ、より速く作業を行っているだけなのです。

数字が示すもの

チームは、単純なものから、数百万のパーツを持つ巨大で複雑なものまで、あらゆる形状とサイズの15種類のロボットの脳を用いてMureをテストしました。これらのテストは、標準的なコンピュータ（特殊なスーパーコンピュータやグラフィックスカードは使用していません）上で実行されました。

• 速度の向上： 平均して、Mureはテストプロセスを44.54%高速化しました。つまり、テストに100分かかっていたものが、今では約55分になります。
• トレードオフ： 彼らは、Mureを他の「ズル（ショートカット）」を行う手法（DM# や BSS と呼ばれるもの）と比較しました。それらのショートカットはさらに高速（最大88.97%高速）でしたが、間違いを犯していました。それらは、ロボットが壊れているのに大丈夫だと言ったり、あるいはその逆だったりすることがありました。Mureは、そのような間違いを拒みました。
• 「どれくらい壊したか？」テスト： 研究者たちはさらに、「もっと多くの部分を壊したらどうなるか？」と問いかけました。彼らは、ニューロンの1%、3%、5%を壊すテストを行いました。より多くの部分を壊すにつれて、再利用できる「最初の10ステップ」が少なくなるため、スピードアップの効果は小さくなりました。しかし、ニューロンの5%を壊した場合でも、Mureは依然として20%のスピード向上を実現しました。

なぜこれが重要なのか

これは単に時間を節約することではありません。それは「信頼」の問題です。自動運転車や医療診断のような安全性が極めて重要な分野では、推測は許されません。テストが「車は安全である」と判定する場合、それは100%確実でなければなりません。Mureを使えば、エンジニアは100%の確実性を犠牲にすることなく、これらの重厚で高価な安全チェックをはるかに速く実行できるのです。

研究者たちは、脳のどの部分を再利用するかについて賢明に対処することで、テストのコストをほぼ半分に削減できることを示しました。彼らはこれが機能すると推測しただけでなく、実際にツールを構築し、実験を行い、数学的に証明したのです。これは、時には、ベストな方法は「より速く走ること」ではなく、「既に行ったことを記憶しておくこと」であるということを思い出させてくれます。