Technopark Mail.ru Konstantin Anisimovich-ABBYYの技術開発部長でのスピーチに基づいて、人工知能に関する一連の投稿を続けています。 2番目の記事では、検索アルゴリズムについて説明します。
一連の投稿のナビゲーター：
選択した知識の提示方法（宣言的または生産的）に応じて、知識の適用方法を決定します。 本番システムではすべてが非常に簡単です。製品を直接解釈します。
知識の宣言的表現を選択すると、すべてが少し複雑になります。 これを行うには、状態空間で検索を実装する必要があります 。 事実、知識の構造化された表現は階層的に編成されています。 また、入力データに階層的な記述を適用しようとすると、各レベルでデータの可能な解釈が得られます-仮説。
組み合わせ爆発を回避し、1つ以上の最良の仮説を効果的に選択するために、状態空間検索アルゴリズムが使用されます。
状態空間は、問題の解決策が個別のステップに分割されるときに発生します。 ここでは、仮説をまだ選択していないときの初期状態と、問題の許容可能な解決策である仮説を見つけたときの最終状態を区別します。 この仮説を検索する過程で、次の状態に遷移する操作があります。 空間的状態が数値のステップに応じて指数関数的な複雑さを持っていることに気付くのは難しくありません。 状態空間全体を回るには、指数関数的な時間が必要です。
この問題を回避するために、さまざまな検索アルゴリズムが適用されます。 それらは、徹底的な検索とヒューリスティック検索の2つのタイプに分けられます。 すでに明らかなように、ほとんどの場合の徹底的な検索は（非常に小さな問題を解決しない限り）適切ではありませんが、ある程度の教育的価値があります。 したがって、最初にそれを検討します。これに慣れている場合は、すぐに発見的タイプに切り替えることができます。
完全列挙を使用した検索
徹底的な検索には、幅優先検索、深さ優先検索、反復深層検索があります。
幅優先探索では、初期状態の空間状態で可能なすべての手順を実行し、新しい状態のセットを取得します。 さらに、このセットの各状態から可能なすべてのステップを実行し、次の状態セットを取得します。解決策が見つかるまで続きます。 グラフィカルに、幅優先探索は、状態空間の正面の動きとして表すことができます。
詳細な検索とは、初期状態から一歩進んだ後、新しい状態から次のステップに進み、最終状態に到達するまで、またはステップを実行できない状態に到達するまでです。 この場合、再帰的な状態に戻り、戻った状態から解決策が見つかるまでステップを繰り返します。
このような幅優先の検索には、時間とメモリの両方で指数関数的な複雑さがあることがわかります。 また、ディープサーチには指数関数的な時間の複雑さがあります。 もちろん、私たちは幸運かもしれませんし、解決策がすぐに見つかるでしょうが、実際にはこれはありそうにありません。
反復深探索は深さおよび幅の探索の最適化であり、指数状態の複雑さを回避して、初期状態に最も近い解を見つけることが保証されています。 このアルゴリズムはどのように実装されていますか？ 一定のNの深さ制限で深さを探しています。解決策が見つかりました-良い。 見つからない-見つかったまで、定数N + 1で深さ検索を繰り返します。 このアルゴリズムは、実装は簡単ですが、最も単純なタスクにのみ適しています。
発見的検索
ほとんどの場合、実用的なタスクはヒューリスティック検索を使用して解決されます。 ヒューリスティック検索は、状態評価機能に基づいています。 徹底的な検索アルゴリズムとは対照的に、ヒューリスティック検索では、「見込み」に基づいて空間状態をランク付けできます。 ヒューリスティック検索は、完全な検索アルゴリズムよりも意図的に状態空間で検索します。 多くの問題では、状態評価が初期状態からこの状態を達成する方法の最良の推定値であることが重要です。 問題でこのような評価が可能な場合、発見的検索アルゴリズムは大幅に簡素化されます。
ヒューリスティック検索アルゴリズムの主なクラスは、最適な状態からの検索です。 貪欲な検索、光線検索、およびA *の3つの主要なアルゴリズムが含まれています。 彼らの一般的な考え方は、1つまたは複数の最良の状態を一度に検索および選択するプロセスで、達成された状態のセットを維持することに基づいています。
それらの最も単純なものは、 貪欲な検索です。 グラフで最適なパスを見つけるタスクに適用される場合、これはよく知られているダイクストラアルゴリズムを生成します 。 貪欲な検索は、検索を続行する元の状態を選択し、初期から指定されたパスへのパスの最適な推定値を持つ状態を検索します。 したがって、それは「欲張り」と呼ばれます-結果を考えずに、現時点で最高の状態を「つかむ」からです。 当然のことながら、多くの貪欲なアルゴリズムのように、そのような戦略は最適なソリューションにつながりません。 多くの場合、最終状態に到達するのに時間がかかりすぎて、最適ではありません。 さらに、貪欲な検索は、達成されたすべての状態のセットを常にサポートする必要があります。これは多すぎるため、メモリが過剰に消費される理由です。
光線探索アルゴリズムとA *アルゴリズムは、欲張り探索の動作を改善し、それに固有のこれらの2つの問題を修正する試みです。 光線検索は次のように機能します。各ステップで、N個の最適な状態の一部をサポートします。 次に、これらの各状態から、可能なすべての手順を実行し、次世代の多くの状態を取得します。 このセットでは、重複、つまり同じ状態を削除します。 残りのものを評価し、劣化順に並べ替えます。 次に、最終的な興味のある状態が見つかるまで、N個の最適なものを選択します。
光線検索には長所と短所があります。 その主な短所は、貪欲なものとは異なり、レイサーチは最高の品質の最終状態を見つけることを保証しないことです。なぜなら、前部を移動する過程で、最良の状態が抜け落ちる可能性があるからです。 実際には、前面の幅を調整することでこれに対処できます。 前部が狭いほど、アルゴリズムの動作は速くなりますが、誤解される頻度が高くなります。 前部が広いほど、アルゴリズムは良くなりますが、長くなります。 これは重要な利点の1つです。速度と品質を簡単にバランスさせることができます。 レイ検索は、アカデミック環境、特に中国の科学者の間で非常に人気があります。 実装は簡単で、かなりうまく機能します。
A *アルゴリズムの考え方は、各ステップで、現時点では最良ではなく最も有望な状態を選択するというものです。 パスが通過する可能性が最も高い状態は、より良い最終状態になります。
アルゴリズムA *の現在の状態を評価するために、パスの残りの下から最終状態までのヒューリスティック推定が追加されます。 ヒューリスティックな下限が十分であれば、A *は効率的に機能し、最適な条件をすばやく見つけます。 この場合、A *はステップ数の多項式であり、指数関数ではありません。 A *は本当に良いアルゴリズムです。私の研究では、ビーム検索よりもずっと頻繁に使用しています。
アルゴリズムA *の欠点は、ヒューリスティックを考え出す必要があることです。 公平に言えば、多くの問題でこのヒューリスティックは非常に簡単で自然であると言わなければなりません。 このようなタスクでは、A *を使用することをお勧めします。 ヒューリスティックを発明できない場合は、光線検索が役立ちます。
このシリーズの3回目の投稿では、人工知能の作成に使用される知識を取得する方法、および機械学習、特にFineReaderで使用される方法について説明します。