イベント / EVENT

平成25年度 第7回 Q&A

第7回 2014年1月22日(水)

問題を見ずに問題を解く~ 定数時間アルゴリズムとは? ~
吉田 悠一 (国立情報学研究所 情報学プリンシプル研究系 准教授)

講演当日に頂いたご質問への回答(全14件)

※回答が可能な質問のみ掲載しています。

先生の研究はバイオインフォマティクスに応用可能でしょうか。
ゲノムのデータに対して、どのようなアプローチが考えられるでしょうか。

応用は可能だと思います。ゲノムのデータはATGCの4種類の文字からなる長い文字列と考えることができ、長い文字列に対する検査アルゴリズムは既に提案されています。ただしバイオインフォマティクスの研究者が喜ぶ問題を選ぶことが大事だと思います。

検査アルゴリズムでパラメータ k が距離Dに依存しない理由がよくわかりませんでした。

完全に証明の都合です。t≧εn/2(k=2/εより)という式がスライドにありますが、これを成り立たせる為にそう選んでいます。これに関しては何故そうなのか感覚的な説明をするのが難しいです。

「直径≤4D+2からε-far」も「直径≤D+4からε-far」どちらも区別可能ということですが、条件のきつい後者ではなく、前者の説明をされたのは、難しさが大きく異なるからでしょうか? 計算量の違いなのか、証明の困難さの違いなのか。

直径≦D+4からε-farの場合はかなり証明が難しく、また全体のアイデアも分かりにくいので今回は割愛しました。

枝の結合の強さ(例えば2重結合のような)は、何か役に立つことはないのでしょうか。(時系列で調べるとか)

どれぐらいグラフが密に連結しているかを考える上では枝の結合の強さを考えるのは自然で、既によく研究されています。

・資料の「性質検査の狙い」の箇所で、"ε=0.01などに固定"とありますが、εの定め方の妥当性はどのように検証されるのでしょうか。また、定数時間アルゴリズムが有効とされる場合、一般に誤差はどの程度許容されるのが前提なのでしょうか。
・εの設定根拠は何ですか。

εの値は工学的な立場から決める必要があると思いますが、残念ながらまだ定数時間アルゴリズムは工学的に利用されていないこともあり、εの決め方に対する統一的な見解はありません。試行錯誤をして納得のいくパラメータを見つけなければならないでしょう。

S=6/ε, K=2/εはどこから出てきたのでしょうか。

完全に証明の都合です。s=6/εとすることで成功確率を2/3以上にすることができます。(1 - (εn/2)/n)^sという式がスライド中にありますが、これを十分小さくする為にs=6/εと選んでいます。kも同様で同じページのt≧εn/2(k=2/εより)というのを成り立たせる為にそう選んでいます。

距離があるグラフにも容易に応用できるのでしょうか。

直径の検査に関して言えば可能です。幅優先探索をしていたところの代わりにダイクストラのアルゴリズムと呼ばれる手法を使うことになるでしょう。ただし距離があるグラフに対してはε-farをどう定義するべきかで議論が分かれる所だと思います。

「どんなグラフでも」とありましたが、アルゴリズムが適用しにくいグラフはあるのか、あるならどのようなものでしょうか。

どんなグラフでも大丈夫です。これは理論的に証明されています。逆に世の中に現れるグラフに対してチューニングを施して性能を上げることが出来るかもしれません。

タンパク質の立体構造の予測の適用ができますか。

今回の場合は与えられた入力がある性質を満たすかどうかというYes/No問題を考えています。立体構造予測の場合は立体構造が出力なので、何か別の枠組みを考える必要があります。

枝は距離=1ではないのでしょうか。

はい、そうです。

D≤X≤4D+2 から ε-far は?
この赤字の間はどうなっているのでしょうか。
また、D≤X≤D+4 から ε-far は?

この赤字の範囲に対する入力グラフが与えられた場合には何を出力するか分かりません。そういう意味では今回紹介したアルゴリズムは満足いかないものかもしれません。せめて≦Dと≦Dからε-farが区別出来れば良いのですが。

お勧めの入門書か参考書があれば教えてください。

定数時間アルゴリズムに関しては実はまだ和書が有りません。私がそのうち書かなければならないかもしれません。もっと一般的なアルゴリズムの入門書であれば共立出版の「アルゴリズム・サイエンスシリーズ」というシリーズの1巻、2巻が読みやすいです。

工場の品質検査サンプリング法も全数が多くなっても全数のうち、100個なら100個サンプリングするので、これと同じ検査方法ですね。

はい、似ています。

shimin 2013-qa_7 page2531

注目コンテンツ / SPECIAL