アルゴリズム理論と機械学習・知識発見の橋渡し

小林 靖明

若手1 平成28 年10 月に情報学研究科知能情報学専攻知能計算分野の助教として着任しました小林靖明と申します。明治大学にて博士号を取得し、学習院大学に2 年間勤めた後、京都大学へ来ました。私の学生時代からの研究の興味の中心は、グラフなどの離散的な対象におけるアルゴリズム理論で、理論だけでなく実用にも興味を持っています。
 私の研究テーマのひとつとして、グラフの木幅(Treewidth)といったグラフの構造的パラメータの研究が挙げられます。グラフの木幅はグラフがどれだけ木に近いかを表すものです。多くのNP 困難なグラフ上の最適化問題は、入力されるグラフを木に制限することでグラフの頂点数に対して線形時間で動作する動的計画法が設計できることはよく知られています。木とは限らない一般のグラフにおいても、木幅に関連する木構造をうまく利用することで同様の動的計画法を設計できることが知られており、特にグラフの木幅が小さいときには、この動的計画法が高速に動作することを理論的に保証することができます。また、近年ではグラフのマッチングや最短経路問題などの多項式時間可解であるような問題に対しても、これらのパラメータが有効に働くことが示され、その重要性がさらに増してきています。私のこれまでの研究では、このようなグラフパラメータを高速に計算するアルゴリズムを理論面・実用面から提案してきました。また、それらを用いて、グラフ描画問題に関するアルゴリズムの研究に取り組んできました。
 現在所属している分野では、機械学習や知識発見に関する研究に取り組んでいます。これらの研究は、私のこれまでの研究とは必ずしも一致しません。しかしながら、これらの研究の中には頻繁に最適化問題が現れ、このような問題を効率良く解くことは非常に重要であると考えられています。特に、私がこれまでに取り組んできたようなNP 困難な問題は、様々な分野において「解けない問題」として考えられていましたが、データの性質をうまく利用することで、ある程度の規模であれば厳密に解くことも不可能ではなくなってきています。特に木幅を用いた研究は、このような応用から生じた問題に対しても有効であることがわかってきています。現在の研究分野である機械学習や知識発見に対しては、そこで現れる諸問題に対して、これまでの研究で得られた知見や技術を活かすことで貢献し、その一方で機械学習や知識発見に現れる新しい問題を今までの研究分野に提供することで、双方の研究分野の発展に貢献できたらと考えています。
 最後に、これまでの所属では教員という立場で学生に対して研究・教育指導することがほとんどなかったのですが、京大に来てから始めて学生の指導を行っています。なかなか苦労することも多いですが、新たな発見も数多くあり充実しています。今後も学生とともに自分自身も成長できるよう研鑽を積んでいきたいと思っています。

(助教 情報学研究科)