戸田研究室

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


メンバー

氏名 Eメイルアドレス
教員 戸田 貴久 toda
D2 趙 振江 zhenjiang
M2 久保 拓巳 kubo
M2 中本 健太郎 nakamoto
M1 伊藤 正英 itou
M1 中里 祐大 nakazato
M1 高田 雄太 takada
M1 肖 智傑 zhijie
B4 大橋 賢人 ohashi
B4 松尾 涼誠 matsuo
B4 中原 良典 nakahara

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を使うことで押し広げていくというのが当研究室におけるチャレンジです。


講義・演習のサポートページ


配属を希望する学生へ

研究室関連の情報はX でも案内しています。

研究室公開

研究活動

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

研究の進め方

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

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

過去の卒論・修論・輪講など

Q&A

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

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

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

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

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

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

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

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

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

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

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

本学の学生ですが、研究室への短期滞在、輪講への参加などはできますか?

あらかじめ面談を実施して、これまでの履修科目や本人の興味や希望などを確認させてもらいます。 まずは学籍番号・氏名・要件を書いてEメールで連絡してみましょう。

さまざまな形で研究室との関わりを持てる機会があります。 たとえば、情報工学工房という授業では、本研究室に関係するテーマで履修生を例年募集しています。 工房の履修生には、本研究室の各種イベント等で活動を共有する機会(任意参加)があります。 他にも輪講だけ参加することもできます(ただし、これは自主活動となりますから単位認定はできません)。 輪講のテキストは輪講・論文紹介などを確認してみましょう。 ゼミの様子を試しに一度見てみたいという人も歓迎します(内容の理解は難しいでしょうけれど、雰囲気はつかめるでしょう)。

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

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

研究室公開などのときにいろいろ話を聞いてみましょう。 ほとんどの人にとって研究活動ははじめての経験でしょうから、 今後どのようなことをすることになるのか分からないでしょう。 研究内容は知らない言葉がたくさん出てきて、難しく聞こえるかもしれません。 このように感じることは当たり前のことです。 気にする必要はありません。 知らないのは当然と思って、いろいろ聞いてみると良いでしょう。

どんな知識や経験が身につきますか?

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

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


他大学・他研究室から進学希望の方へ

あらかじめ面談(オンライン)を実施して、これまでの履修科目や本人の興味や希望などを確認させてもらいますから、まずはEメールで連絡してください。 随時受け付けています。
上のQ&Aは主に卒研配属の学生を想定して書いていますが、修士課程から進学する学生でもだいたい同じと考えてもらって良いです。 これまでの研究との類似性をそれほど重視しているわけではありません。 思い切って違う分野に挑戦したいという人も受け入れています。


企業・研究機関の方へ

当研究室の研究にご興味を持たれた場合は、問合せ先のEメールにご連絡下さい。当研究室の研究内容を説明します。 当研究室では最先端の基礎研究の成果を現実の問題解決に役立てることを目標のひとつに掲げています。 解決したい課題等についてお教えください。 どのような形で協力できるか検討させていただきます。

本学における産学連携制度の詳細については、こちらをご覧ください。


問合せ

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

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