戸田研究室

電気通信大学 大学院情報理工学研究科 情報・ネットワーク工学専攻
キーワード:人工知能、制約充足、論理、推論、SATソルバー
お知らせ:twitter
メンバー向け:github, slack, scrapbox, gather, zoom, カレンダー, 研究室の資料


メンバー

氏名 Eメイルアドレス
教員 戸田 貴久 toda
M2 夏 涛 xiatao
M1 磯田 飛鳥 isoda
M1 中島 祐輝 nakajima
M1 趙 振江 zhenjiang
B4 田中 太一 tanaka
B4 八木 啓至 yagi
B4 山野 光稀 yamano

Eメイルアドレスのドメインはdisc.lab.uec.ac.jpです。


研究紹介

研究紹介のスライド(PDF)

「○○○および△△△および×××という条件をすべて満たすことができるか?」というような問題を考えてみましょう。 例えば、あなたはお店のオーナーで、すべての店員から希望を聞いてシフト(勤務する曜日)を決定するとしましょう。 まずは話を簡単にするために、希望として提示できるのは勤務できる曜日だけとします。 このときにすべての店員の希望を満たしながら、どの曜日も少なくとも1人が勤務するようにしたいとします。 そのようなシフトをどうやって決定すれば良いでしょうか?

この場合は、曜日ごとに勤務できる人を適当に選んで勤務させればOKですね(勤務できる店員がいない曜日はあなたがお店に立つしかなさそうです・・・トホホ)。 何だ簡単じゃないか!と甘く見てはいけません。 現実はもっと複雑です。例えば、店員は週に2日はお休みをとる必要があったり、各曜日に勤務させる人数をもっと増やす必要があるかもしれません。 他にも月曜出勤するならば火曜は休みたいとか、Aさんとは違う日にして欲しいとか、いろいろな条件が考えられます。 こうなると先ほどの方法は通用しませんし、すぐにシフトを決定できる他の良い方法もなさそうです。

えい、面倒だ!とヤケになってAさんは月曜日、Bさんは土曜日・・・という具合にかたっぱしから決めていくとしましょう。 しかし、これでは日曜に勤務できる人が足りなくなった!というように途中で行き詰まることがあるので、別の決め方を考え直さなければならなくなります。 運がよければ何度かやり直した後でシフトを決定できるかもしれませんが、すぐに見つかる保証はなさそうです。 実際、しらみつぶしでやろうとすると、運が悪ければ(店員の人数Nに対して)7のN乗程度の回数のやり直しが必要になります。 Nが少し大きくなるだけで簡単に天文学的な数になります! 地道に調べ上げていくのは到底現実的ではありません。

N 7^N
1 7
2 49
3 343
4 2,401
5 16,807
6 117,649
7 823,543
8 5,764,801
9 40,353,607
10 282,475,249
11 1,977,326,743
12 13,841,287,201
13 96,889,010,407
14 678,223,072,849

そもそも希望を聞かずに決めていけばこんな苦労をする必要はなかったのですが、一度希望を聞くと言った以上後には引けません。 さぁ、ここで研究の始まりです! どうやったら天文学的な数の場合分けの罠にはまらずに、現実的な時間内にシフトを決定できるでしょうか? そもそも提示されたすべての条件を満たすシフトは存在するのでしょうか? 存在しないことが分かったときは、店員と相談してすべての条件が満たされるように条件を緩めてもらう必要があります。 しかし、これは最小限にとどめるようにしたいですね。 例えば、少数の店員の条件が厳しすぎたのが原因であれば、他の人と同程度になるように妥協してもらうことで大多数の店員の希望は維持できます。 どうやってそのような原因を特定すれば良いでしょうか?

前置きが長くなりましたが、「シフトの決定」という身近な例を題材にして、現実にありそうないくつかの課題を見てきました。 当研究室では、複数の条件(制約)を同時に満たすことができるか?というような形の問題(制約充足問題;CSP)とそれに関わる様々な研究課題に取り組んでいます。 制約充足問題の制約を命題論理式に限定すると、充足可能性判定問題SATになります。 CSPやSATは人工知能の論理推論などの分野で伝統的に研究されてきました(今でも活発に研究されています)。 離散数学、計算量理論、アルゴリズム理論といった分野でも観点は異なりますが重要な研究テーマです。 その他にも、当研究室ではすべての解を求めるときに威力を発揮するBDDやZDDというデータ構造も活用しています。

CSPやSATは、通常、論理式や論理関数などといった数学的な言葉を使って説明されるので近寄りがたいように感じられるかもしれませんが、上で見たように現実のさまざまな状況において見られるものです。 CSPやSATの解(上でシフトと呼んでいたもの)を発見するための実践的な計算技法を開発してプログラムとして実現することで、さまざまな現実の状況における問題解決に役立てることができます。

莫大な数の場合分けが生じるような計算をしようとすると、途方もない時間がかかります。 このような場合にCSP/SATやBDD/ZDDはまさに持ってこいのものです。 現在の技術水準で実際に計算によって解決できる領域の境界をCSP/SATやBDD/ZDDを使うことで押し広げていくというのが当研究室におけるチャレンジです。


配属を希望する学生へ

研究室公開

研究活動

研究室の定例の活動は進捗報告会、個別ミーティング、輪講です。 学生は進捗報告会の前までに、パワーポイントなどを使ってあらかじめ簡単なスライドを作成しておきます。当日は、1週間どんなことに取り組み、どんなことを学んだり考えたりしたのか、どんな問題が生じたのか、次に何に取り組むかなどといったことを手短に報告しましょう。 進捗報告会は研究室の他のメンバーに自分の活動を知ってもらうことを目的にしています。 進捗報告会では手短な質疑応答しかできません。 一方、教員と学生の1対1で実施する個別ミーティングは議論をする場です。 研究の問題点を把握したり、解決策を検討したり、次に取り組むべきことを設定したりします。 輪講では、研究分野の専門的な知識を身につけるために教科書を1つ決めて、研究室のメンバー全員で読んでいきます。毎週1人の担当者には、理解した内容をスライドにまとめてもらいます。担当者はあらかじめ決められた順番で交代します。授業や自分の研究があるので、輪講では進める量は少しでも良いのですが、大切にしたいのは毎回の内容をきちんと理解すること、途中で脱落しないで継続していくことです。

研究の進め方

入門的な解説記事や書籍を渡すので、まずは研究分野の基本的な知識から学習しましょう。その上で、自分の興味に合わせて研究テーマを絞り込んでいきます。教員からいくつかの研究テーマの候補を提示するので、そこから選んでも良いです。テーマが決まったら、関連する論文や書籍を読み進めながら、研究課題(解決したい課題)を探します。同時に、先行研究の手法を実装して再現します。必要なツール、ソフトウェアがあればその使い方も学びます。設定した課題を解決するためのアイディアを考えます。アイディアを深めていきます。アイディアを実装して提案法を実現します。計算機実験を実施して、結果の考察を行います。以上のようなプロセスで得られた結果を論文にまとめます。

大学院学生の場合は、学部学生のときよりも主体的に研究を進めることが期待されます。自分の研究だけでなく、学部学生の研究の相談にのったり、研究の補助をやってもらうこともあります。

過去の卒論・修論など

こちらにまとめています。

Q&A

どのプログラム言語を使いますか?どれくらいのプログラミング経験が求められますか?

特にこだわりがなければC言語、C++言語、Java言語など一般的なものを使うと良いでしょう。 配属前までにはプログラミング言語の基本的な文法を理解して、活用できるようになっておくことが必要です。 コンパイル時や実行時のエラーが起きた場合には、最終的には独力でプログラム上の誤った記述を特定して、修正できる“ぐらいの”問題解決能力も必要です。 (あくまで“ぐらいの”です。必ずできることを求めているわけではありません。)

また、linuxのコマンドライン操作にも一定程度慣れていることが望ましいです。 主に計算機実験のためSSHでリモートサーバに接続してターミナル上で操作することになります。

数学が得意ではありませんが、大丈夫ですか?

基本的な数学(高校数学程度)や論理的な思考が身についていることが必要です。

英語が得意ではありませんが、大丈夫ですか?

卒研から英語の文献を読むことがあります。 修士課程では英語の論文や書籍を読む機会が増えます。 オープンソースソフトウェアのドキュメントも基本的に英語で書かれています。 どの研究テーマを選択するかによって全然異なりますが、(特に修士では)日本語で書かれた文献はほとんどないと思っておいた方が良いです。

コロナ禍における研究活動はどのように行っていますか?

現在は新型コロナウィルスへの感染リスクがあるため、自宅で研究できる人は自宅で研究活動をするようにしましょう。 研究室に来ることもできますが、感染しないように各自で十分に対策をとりましょう。

当研究室ではオンラインでも学生同士の交流を保てるように、各種のインターネットサービスを活用して適度にコミュニケーションをとれるように工夫しています。 例えば、毎週金曜日の進捗報告会の前には任意参加のオンライン昼食会を開催しています。

どんな研究をすれば良いかまったく見当がつきませんが、大丈夫ですか?

具体的な研究テーマは配属された後で一緒に考えていきます。 教員から研究テーマの候補を提示するのでその中から選んでも良いです。 配属する前からやりたい研究テーマが決まっている人はあまりいないので気にする必要はありませんが、大切なのは上の研究の概要で説明したようなことに興味を持って取り組めるかどうかです。

研究テーマの決定は大切です。 卒研では1年間そのテーマに取り組むことになるからです。 どんな研究テーマをやりたいのか明確に答えるのは難しいでしょうけれど(それが普通です)、自分はどんなことに興味があるのか、どんなことを面白いと思えるのか、など自分の特性を言葉で伝えられるようにしておくと良いでしょう。

また、研究室公開などの機会にどんな研究ができるのか見に来てみると良いでしょう。興味を持って研究に取り組めるか、研究室の雰囲気は自分に合うか、などといった印象を実際に感じてみると良いでしょう。

卒研はどのぐらい大変ですか?卒業できますか?

どんな研究をするか?ということから一緒に考えていきます。 1年後にどういう形に研究がまとまるかは、学生がその1年間に何をどう考え取り組んだかによって決まっていきます。 教員も適宜サポートするので、ひとりぼっちで進めるわけではありません。

答えを見つけられなかったら卒業できない?・・・そんなことはありません。 そもそも研究では”答え”なんてないことが多いです。 小さくても良いので何かオリジナルの工夫をしましょう。 例えひどい実験結果になったとしても、なぜ当初うまくいくと思っていたこと(仮説)が想定通りにいかなかったのか?分析することはできるでしょう。 そういうことをまとめていけば新しい知見が含まれたオリジナルの成果につながります。

まずは毎週の進捗報告を大切にすることをおすすめします。 進捗報告を積み重ねていけば、研究がまとまるように教員がサポートしていきます。

配属前にどのような準備をしておけば良いですか?

例えば、英語、プログラミング、アルゴリズム、離散数学など学部の科目で学んできたことを復習しておくと良いでしょう。 院試対策にもなります。

研究室に合うかどうかはどうやって決めれば良いですか?

アドバイスとしては、これまで学んできた科目や取り組んだことの中で面白いと思ったものは何か考えてみましょう。 どういうところが面白いと思ったのでしょうか?どういうところにやりがいを感じたのでしょうか? それを踏まえて、研究室の紹介を聞いてみて(まったく同じでないにしても)どこか似たところや近いところはありましたか?

また、研究室公開のときに研究室の先輩学生に話を聞いてみるのも良いでしょう。 研究内容だけでなく、研究生活全般についても気になることがあれば聞いてみると良いでしょう。

他大学から進学したいですが、大丈夫ですか?

あらかじめ面談を実施して、これまでの履修科目や本人の興味や希望などを確認させてもらいますから、まずはEメールで連絡してください。

本学であれ他大学であれ、大学院から当研究室に入る場合は、これまでの研究内容と多少違うことに取り組むことになるので、以下のことには注意をしてください。 2年間で修士レベルの研究をほとんどゼロからまとめるのは簡単ではありません。 実際に研究室に入ってみたらやりたいこととは違ったのでやる気が出ない・・・ゼロからのスタートなのにあまり指示をしてくれなくて不満だ、ということでは不幸になってしまいます。

当研究室では、B4の学生はこれまで研究の経験がないことを前提に、1年間で一通りの経験を積められるように細かい配慮をするようにしています。 しかし、大学院の学生には(研究内容は何であれ)一通りの研究サイクルを経験したことを前提にして、今度は同じ研究サイクルを自分で主体的にまわしていくことを基本方針にしています。 これは学部から当研究室に所属している学生だけでなく、他大学や他研究室の出身者に対しても同じです。 後者の場合には、知らないことや分からないことが多くなりますが、自分で調べたり、考えたり(その上で質問したり、相談したり)しましょう。 自主性をもって取り組まないと研究が進みません。

卒業するときにはどんな知識や経験が身につきますか?

どんな研究テーマを選択するかによって身につく専門知識は異なりますが、概ね人工知能の制約充足分野の知識が身につきます。 ただ、ほとんどの学生にとっては専門知識を身につけること自体が大切なのではなくて、もっと大切なことは、例えば次に挙げるような経験をすることでしょう。 誰も課題として認識していないことを探すこと、課題の解決がどういう価値につながるか想像すること、課題の解決に向けてアイディアを出すこと、多くの人に支持してもらえるように工夫して結果を発表することです(もちろんこれ以外にもあります)。

広い視野から見ればそのような経験はいろんなことにつながっていきます。 最先端の情報技術を活用できることなどのような即戦力も将来的には大切になるかもしれませんが、道具を使いこなして価値につなげるには知恵が必要です。 理想としては、大学における研究活動を通して学生がそういう知恵の種を育てていけられるようにしたいと考えています。 ただ、私ができることは限られています。結局は学生が自分で育てていくしかないので、あらかじめ「これができるようになる」と言うことはできません。

どんな情報技術が身につきますか?

負担にならない範囲で研究活動の中で新しい情報技術を取り入れるようにしています。 例えば、githubで研究進捗の管理やプログラム開発をします(どの程度使い込むかは学生に任せています)。 普段のコミュニケーションはslackでやっています。


企業・研究機関の方へ

当研究室の研究にご興味を持たれた場合は、問い合わせ先のEメールにご連絡下さい。当研究室の研究内容を説明します。


問合せ

〒182-8585 東京都調布市調布ヶ丘 1-5-1
電気通信大学 大学院情報理工学研究科
情報・ネットワーク工学専攻
戸田研究室
ご質問、ご意見、ご相談等 contact(at)disc.lab.uec.ac.jp

(at)をアットマークに置き換えてください。