平滑化分析

理論計算機科学において、平滑化解析はアルゴリズムの複雑さを測定する方法である。2001年に導入されて以来、平滑化解析は数理計画法、数値解析、機械学習、データマイニングなどの問題に関する多くの研究の基礎として使われてきた。^[1]最悪のケースや平均的なケースのシナリオを使った解析に比べて、アルゴリズムの実際のパフォーマンス（実行時間、成功率、近似品質など）のより現実的な解析が可能となる。

平滑化分析は、最悪ケース分析と平均ケース分析の両方の利点を継承したハイブリッドです。最悪ケースの入力のわずかなランダムな摂動の下でアルゴリズムの予想されるパフォーマンスを測定します。アルゴリズムの平滑化複雑度が低い場合、データがわずかなノイズや不正確さの影響を受ける実際のインスタンスを解決するためにアルゴリズムが長い時間をかける可能性は低くなります。平滑化複雑度の結果は、強力な確率的結果であり、大まかに言えば、入力空間の十分に大きいすべての近傍で、ほとんどの入力が簡単に解決可能であることを示しています。したがって、平滑化複雑度が低いということは、入力の難しさが「脆弱な」特性であることを意味します。

最悪ケースの複雑度は多くのアルゴリズムの実際のパフォーマンスを説明するのに広く成功しているが、このスタイルの分析は多くの問題に対して誤解を招く結果をもたらす。最悪ケースの複雑度は、あらゆる入力を解くのにかかる時間を測定しますが、解くのが難しい入力は実際には決して発生しない可能性があります。そのような場合、最悪ケースの実行時間は、実際に観測される実行時間よりもはるかに悪くなる可能性があります。たとえば、単体アルゴリズムを使用して線形計画法を解く最悪の複雑度は指数関数的ですが、^[2]実際に観測されるステップ数はほぼ線形です。^{[3] [4]}単体アルゴリズムは実際には楕円体法よりもはるかに高速ですが、後者は最悪ケースの複雑度 が多項式時間です。

平均ケース分析は、ワーストケース分析の限界を克服するために最初に導入されました。ただし、結果として得られる平均ケースの複雑さは、入力に対して選択された確率分布に大きく依存します。実際の入力と入力の分布は、分析中に行われた仮定とは実際には異なる場合があります。ランダムな入力は、一般的な入力とはまったく異なる可能性があります。このデータ モデルの選択により、理論上の平均ケースの結果は、アルゴリズムの実際のパフォーマンスについてほとんど何も語らない可能性があります。

平滑化分析は、最悪ケース分析と平均ケース分析の両方を一般化し、両方の長所を継承します。平均ケースの複雑さよりもはるかに一般化することを目的としており、同時に低い複雑さの境界を証明できるようにします。

ACMと欧州理論計算機科学協会は、平滑化解析の開発に対して、ダニエル・スピルマン氏とシャンホア・テン氏に2008 年のゲーデル賞を授与しました。平滑化解析という名前は、アラン・エデルマン氏によって考案されました。^[1] 2010 年、スピルマン氏は平滑化解析の開発に対してネヴァンリンナ賞を受賞しました。スピルマン氏とテン氏の JACM 論文「アルゴリズムの平滑化解析: シンプレックス アルゴリズムに通常多項式時間がかかる理由」は、数理計画学会(MPS) とアメリカ数学会(AMS)が共同でスポンサーとなった2009 年のフルカーソン賞の 3 人の受賞者の 1 つでもありました。

シンプレックス法は実用上非常に効率的なアルゴリズムであり、線形計画法の実用上主要なアルゴリズムの 1 つです。実際の問題では、アルゴリズムのステップ数は変数と制約の数に比例します。^{[3] [4]}しかし、理論上の最悪のケースでは、最もうまく解析されたピボットルールに対して指数関数的に多くのステップが必要になります。これが、平滑化解析を開発する主な動機の 1 つでした。^[5]

摂動モデルでは、入力データがガウス分布からのノイズによって摂動されていると仮定します。正規化のために、摂動されていないデータは行列のすべての行に対して を満たすと仮定します。ノイズは、平均と標準偏差のガウス分布からサンプリングされた独立したエントリを持ちます。 と設定します。平滑化された入力データは、線形計画で構成されます。 ${\displaystyle {\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n },\mathbf {c} \in \mathbb {R} ^{d}}$${\displaystyle \|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1}$${\displaystyle ({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})}$${\displaystyle ({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).}$${\displaystyle ({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})}$${\displaystyle 0}$${\displaystyle \sigma}$${\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }} +{\hat {\mathbf {b} }}}$

最大化する

${\displaystyle \mathbf {c^{T}} \cdot \mathbf {x} }$

対象となる

${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$。

データに対するアルゴリズムの実行時間が次のように与えられる場合、単体法の平滑化された複雑度は^{[6]である。}${\displaystyle \mathbf {A} ,\mathbf {b} ,\mathbf {c} }$${\displaystyle T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )}$

${\displaystyle C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).}$

この境界は、シャドウ頂点ルールと呼ばれる特定のピボットルールに当てはまります。シャドウ頂点ルールは、ダンツィヒルールや最急勾配ルール^[7]などのより一般的に使用されるピボットルールよりも低速ですが、確率分析に非常に適した特性を持っています。^[8]

多くの局所探索アルゴリズムは、最悪の場合の実行時間は悪いものの、実際には良好なパフォーマンスを発揮します。^[9]

一例として、巡回セールスマン問題に対する2-optヒューリスティックが挙げられます。局所的に最適な解が見つかるまでには指数関数的に多くの反復が必要になりますが、実際には実行時間は頂点の数の2乗以下です。^[10]アルゴリズムの出力の長さと最適解の長さの比である近似比は、実際には良い傾向にありますが、理論上の最悪の場合には悪いこともあります。

問題のインスタンスの 1 つのクラスは、ボックス 内のポイントで表すことができます。ここで、ポイント間の距離はノルムから得られます。2 次元の場合、2-opt ヒューリスティックは、局所最適値を見つけるまで指数関数的に多くの反復が必要になる可能性があります。この設定では、確率密度関数を持つ確率分布に従って頂点が個別にサンプリングされる摂動モデルを分析できます。 の場合、ポイントは均一に分布しています。が大きい場合、敵対者は困難な問題インスタンスの可能性を高める能力が高くなります。この摂動モデルでは、2-opt ヒューリスティックの予想される反復回数と、結果として得られる出力の近似比は、およびの多項式関数によって制限されます。^[10]${\displaystyle n}$${\displaystyle [0,1]^{d}}$${\displaystyle v_{1},\dots ,v_{n}}$ ${\displaystyle f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]}$${\displaystyle \theta =1}$${\displaystyle \theta >1}$${\displaystyle n}$${\displaystyle \theta }$

平滑化解析が成功した別の局所探索アルゴリズムは、k平均法である。内の点が与えられた場合、同じクラスター内の点間のペアワイズ距離が小さいクラスターへの適切な分割を見つけることはNP困難である。ロイドのアルゴリズムは広く使用されており、実際には非常に高速であるが、最悪の場合、局所最適解を見つけるのに反復が必要になることがある。しかし、点がそれぞれ の期待値と標準偏差 を持つ独立したガウス分布 を持つと仮定すると、アルゴリズムの反復の期待回数は、およびの多項式によって制限される。 ^[11]${\displaystyle n}$${\displaystyle [0,1]^{d}}$${\displaystyle e^{\Omega (n)}}$${\displaystyle [0,1]^{d}}$${\displaystyle \sigma }$${\displaystyle n}$${\displaystyle d}$${\displaystyle \sigma }$

• 平均的なケースの複雑さ
• 擬似多項式時間
• 最悪の場合の複雑さ