研究 / Research

「劣モジュラ最適化問題」を極め、機械学習の効率化をめざす

「組合せ最適化問題」で計算量は減る

　私は「組合せ最適化問題」の中でも、劣モジュラ性をもつ「劣モジュラ最適化問題」を数学的に研究しています。この問題へのアプローチが、AI（人工知能）を教育する機械学習の効率化につながるとわかり、研究はますます盛んになっています。
　「組合せ最適化問題」とは、例えば、昼食のためにコンビニに行き、"主食"と"おかず"と"サラダ"といったように、いくつかの商品を組み合わせて購入する際にも起こる身近な問題です。一見簡単なようですが、商品が10個の場合にその組み合わせは約1000通り、30個では約10億通りにもなります。しかし、実際には、「栄養バランスのいい組み合わせ」や、「お腹がいっぱいになる組み合わせ」などの条件をつけて商品を選ぶので、すべての組み合わせを考える必要はありません。つまり「組合せ最適化問題」では、その時々に求められる"最もいい（最適な）組み合わせ"を選ぶことで、考えなければならない組み合わせの数をぐっと少なくし、答えを得るための計算量を減らせるのです。

劣モジュラ性が教師データ選びに力を発揮

　「劣モジュラ性」とは、「同じことが起こっても、満たされているとその効果が表れにくい」ことを言います。例えば、昼食にピザをもらっても、何もない人と、すでに弁当をもっている人では嬉しさの度合いが異なります。このような状況を劣モジュラ性があると言います。
　「劣モジュラ最適化問題」の考え方は、機械学習を効率化させる、「能動学習」や「特徴選択」に応用できます。機械学習では、AIを教育するためにたくさんの教師データが必要です。ただ、データの中には、学習効果が高いものとそうでないものがあるので、教師データの選び方によって効率的に学習させることができます。これを「能動学習」と呼びます。
　哺乳類とそうでない動物がそれぞれ6種類ずついて、これらを類似性に基づいて並べると、両者を分ける線を引くことができるとします（図）。しかし、この例では、蛇と象とイルカの3種類があれば境界線を引くことができます。つまり、この3種類の動物の組み合わせが、「哺乳類の判別」を効率的に学習できるデータです。そのほかの動物のデータを学習させても学習効果が低いので、ここには劣モジュラ性があるのです。一方「特徴選択」では、たくさんある特徴の中から、意味のある特徴を抽出することで、同様に機械学習の効率化を図ります。

〈図〉能動学習のイメージ。哺乳類とそうでない動物それぞれ6種類ずつデータがあると、両者を分ける線が引ける（左）。蛇と象とイルカのように上手くデータを選べば、3つのデータで線を引くことができる。この発想から、データの選び方によって効果的な機械学習が可能だと言える。

　私は「劣モジュラ最適化問題」研究の副産物として得られるアルゴリズムを、「能動学習」と「特徴選択」に応用したいと思っています。さらに将来的には、実際の問題を解決したいので、社会の問題に詳しい人たちとの共同研究も考えています。

よい組合せを見つけるには？組合せ最適化で機械学習の問題を解決 藤井 海斗 国立情報学研究所 研究紹介

リンク

• [NII SEEDS]劣モジュラ最適化の理論を用いて効率的な機械学習アルゴリズムを設計