Winter Festa Episode 2

若手研究者主体のイベント→ 大学院生・ＰＤ中心（２５－３５歳）
ビジネス色はなるべく少なく、基礎技術、基礎研究中心
 情報系（基礎）の大型プロジェクト結集！
→ 現在の日本の主要プレーヤーも集結！ 研究はどれも世界レベル！
 タイムリーな招待講演！
→ ＪＳＴ＆文科省からの叱咤激励＆クリスマスプレゼント？


幅広い情報系基礎研究を披露＆若手研究者の交流
プロジェクトの紹介を少なめ（＜１０分）＆ポスター中心（交流できるように！）→ 若手研究者の方、ぜひ楽しんで下さい！

Day1 Thursday，December 22
13:00 － 13:05 開会・主催者挨拶

Day2 Friday，December 23
10:00 － 10:25 革新知能統合研究センター(AIPセンター)紹介 / ハイライト
杉山 将 （理化学研究所）

河原林 健一 JST ERATO 河原林巨大グラフプロジェクト 研究総括
13:05 － 13:30 ERATO 河原林プロジェクト紹介 / ハイライト

10:25 － 10:40 CREST 津田プロジェクト紹介 / ハイライト
津田 宏治 （東京大学）

河原林 健一 （国立情報学研究所）
13:30 － 13:45 CREST 岩田プロジェクト紹介 / ハイライト
岩田 覚 （東京大学）
13:45 － 14:30 ポスターセッション
14:30 － 14:55 CREST 佐久間プロジェクト紹介 / ハイライト
佐久間 淳 （筑波大学）
14:55 － 15:10 CREST 平岡プロジェクト紹介 / ハイライト

10:40 － 11:20 ポスターセッション
11:20 － 11:45 CREST 加藤プロジェクト紹介 / ハイライト
加藤 直樹 （関西学院大学）
11:45 － 11:55 さきがけ研究者 ハイライト
11:55 － 12:35 ポスターセッション
12:35 － 14:00 昼食
14:00 － 14:20 ACT-I「情報と未来」 紹介
後藤 真孝 研究総括 （産業技術総合研究所）

平岡 裕章 （東北大学 原子分子材料科学高等研究機構）
15:10 － 15:25 さきがけ研究者 ハイライト

河原林 健一 領域アドバイザー （国立情報学研究所）

15:25 － 16:15 ポスターセッション

湊 真一 領域アドバイザー （北海道大学）

16:15 － 16:45 新学術領域研究 渡辺プロジェクト(ELC)紹介 / ハイライト
渡辺 治 （東京工業大学）
16:45 － 17:00 ACT-I研究者 ハイライト
17:00 － 17:50 ポスターセッション
17:50 － 18:10 特別講演 「情報系若手研究者への日本政府から期待と支援」
栗原 潔 文部科学省研究振興局参事官（情報担当）付専門官
18:30 － 20:30 懇親会

14:20 － 14:50 基盤(S) 離散構造処理系プロジェクト紹介 / ハイライト
湊 真一 （北海道大学）
14:50 － 15:05 CREST 宇野プロジェクト紹介 / ハイライト
宇野 毅明 （国立情報学研究所）
15:05 － 15:50 ポスターセッション
15:50 － 16:10 ERATO 河原林プロジェクト ハイライト
16:10 － 17:00 ポスターセッション
17:00

閉会の挨拶

JST ERATO巨大グラフプロジェクト

国立情報学研究所
河原林 健一JST戦略的創造研究推進事業（ＥＲＡＴＯ型研究）における5/43
平成２４年度 新規研究領域および研究総括の決定について（9月28日）
研究総括： 河原林 健一（カワラバヤシ ケンイチ）（国立情報学研究所 教授）
研究領域： 巨大グラフ
戦略目標： 人間と調和する情報環境を実現する基盤技術の創出
研究期間：５年程度、研究費総額：最大１２億円程度
研究内容： 巨大なネットワークを解析する高速アルゴリズムの開発を通じて、革新的な数学的理論を構築し、 大量情報の解析におけるその有効性の実証を目指します。

10月1日より、ERATO発足に伴い、NIIに「ビッグデータ数理国際研究センター」発足

～ ２０１８年３月
 もうすぐ「審査」される側です！
 目標、研究計画などはなく、あとは仕上げ！
世界的な研究成果をあげるためには、


理論研究者を最低一人巻き込む

データホルダーも巻き込む
現実的＆困難な課題を持っている人を巻き込む（実装力のある）大学院生＆PDが主導



GOOGLE，MICROSOFT等のトップIT企業の研究所と同様の研究組織を目指す！（→このような研究所は日本では皆無！）

我々の研究成果（’１３-’１６）：数！
注意： 情報学分野では、論文誌よりトップ国際会議に論文が採用される方が重要！

アルゴリズム＆理論（ＳＴＯＣ, ＦＯＣＳ, ＳＯＤＡ）+ ＳＯＤＡ‘１３ ＆１５, ＦＯＣＳ’１５, Ｂｅｓｔ Ｐａｐｅｒ Ａｗａｒｄｓ!
 データベース (ＳＩＧＭＯＤ, ＶＬＤＢ, ＩＣＤＥ) 機械学習等(ＩＣＭＬ, ＮＩＰＳ, ＡＡＡＩ, ＩＪＣＡＩ) データマイニング(ＫＤＤ, ＷＷＷ, ＣＩＫＭ,ＷＳＤＭ)
 その他(ＳＯＣＧ, ＬＩＣＳ, ＩＮＦＯＣＯＭ,ＣＣＣ,ＡＣＬ)
３4
６
２９１38

評価
１．合計90本（以上）は，日本全体の１/４～１/３.
２．計算機科学分野の広範囲をカバーしている
３．ほぼすべての論文が，「数理科学」の理論研究ベース（多くの理論の組み合わせ）！
４．ほぼすべての論文で，大学院生、ポスドクが主体！
５．日本のＶＩＳＩＢＩＬＩＴＹ向上(１%程度）にも貢献
６．アルゴリズム分野でも質（３ ＢＥＳＴ ＰＡＰＥＲＳ）＆量ともに向上！
７．同じ予算規模の中では、世界の有数の研究センターに！

「純粋」な底上げ
ＥＲＡＴＯ前ＥＲＡＴＯ中 データベース (ＳＩＧＭＯＤ, ＶＬＤＢ, ＩＣＤＥ)０→６ 機械学習等(ＩＣＭＬ, ＮＩＰＳ, ＡＡＡＩ, ＩＪＣＡＩ)
4→２９ データマイニング(ＫＤＤ, ＷＷＷ, ＣＩＫＭ,ＷＳＤＭ) 1→
１3
 その他(ＬＩＣＳ, ＩＮＦＯＣＯＭ,ＣＣＣ，ＡＣＬ)
0→
5合計

5→

５3

毎年 ＋１３～１５ の底上げ！

コミュニティに訴えることができたこと成功した研究例は…
１．多くの大学院生・ＰＤが主導
２．「理論ベース」のアプローチ
３．幅広い理論の道具を結集！

（若手研究者の）研究に必要な能力 ［重要度順］
１．アルゴリズムの理解
２．（組合せ）最適化の理解
３．実装力
４．機械学習・AI・データベース・データマイニングでの知識人材育成
ＲＡ, ＰＤの過去３年間でのポジション取得状況（⇒ＥＲＡＴＯ終了までに１．５倍程度の規模になる可能性あり）
トロント大助教(Ａｓｓｉｓｔａｎｔ Ｐｒｏｆｅｓｓｏｒ)
 ＮＩＩ助教（2人）
 東大助教（5人）
 京大助教 東工大助教
 大阪大助教
 東北大助教
静岡大助教
 豊橋技術大学助教
 ＮＩＣＴテニュアトラック研究員
 産総研ＡＩセンター
テニュアトラック研究員（２人）
 鳥取大助教
 帝京大専任講師
 JSTさきがけ研究員


その他： ＮＥＣ研究所、日立研究所、富士通研究所、Ｇｏｏｇｌｅ、リクルートなど多数
ＲＡから学振（ＤＣ）→１４人

安倍首相のインド訪問に合わせて開催された「科学技術関連セミナー」

「科学技術関連セミナー」

日英ＢＩＧ ＤＡＴＡ交流主催（英国訪問2014）

日英ＢＩＧ ＤＡＴＡ ＷＯＲＫＳＨＯＰ主催（２０１４）

日仏ＢＩＧ ＤＡＴＡ ＷＯＲＫＳＨＯＰ主催(2014)

日英ＢＩＧ ＤＡＴＡ交流主催（２０１５）ウィリアム王子来日記念！

注意： 情報学分野では、論文誌よりトップ国際会議に論文が採用される方が重要！

アルゴリズム＆理論（ＳＴＯＣ, ＦＯＣＳ, ＳＯＤＡ）+ ＳＯＤＡ‘１３ ＆１５, ＦＯＣＳ’１５, Ｂｅｓｔ Ｐａｐｅｒ Ａｗａｒｄｓ!
 データベース (ＳＩＧＭＯＤ, ＶＬＤＢ, ＩＣＤＥ) 機械学習等(ＩＣＭＬ, ＮＩＰＳ, ＡＡＡＩ, ＩＪＣＡＩ) データマイニング(ＫＤＤ, ＷＷＷ, ＣＩＫＭ,ＷＳＤＭ)
 その他(ＳＯＣＧ, ＬＩＣＳ, ＩＮＦＯＣＯＭ,ＣＣＣ,ＡＣＬ)




３4
６２９１３8このような研究成果は、ほとんど日本では発表していない！
→ 日本でも発表の場が必要！
本ＰＪ外の研究者もトップ会議論文発表！
→ コミュニティに、現在日本で世界的な仕事を行っている（若手）研究者のショーケースを示す！

Ｗｉｎｔｅｒ Ｆｅｓｔａ
我々の組織は離散数学，アルゴリズム，機械学習，データマイニング，自然言
語処理, 統計物理学, データベース，最適化，OR等，広範囲の研究者集団！
「数理科学」のキーワードのもとに数学，OR，情報科学のトップ研究者が集結⇒ 情報処理・電気通信・応用数理・物理・応用物理・数学・ＯＲなどの学会に広がる組織⇒ 学会の枠を超えた研究集会が必要！
クオリティの高い！情報系大型プロジェクト間の交流を行う！


Day1 Thursday，December 22

13:00 － 13:05 開会・主催者挨拶



Day2 Friday，December 23

10:00 － 10:25 革新知能統合研究センター紹介 / ハイライト
杉山 将 （理化学研究所）

河原林 健一 JST ERATO 河原林巨大グラフプロジェクト 研究総括
13:05 － 13:30 ERATO 河原林プロジェクト紹介 / ハイライト_Group１

10:25 － 10:40 CREST 津田プロジェクト紹介 / ハイライト

河原林 健一 （国立情報学研究所）

津田 宏治 （東京大学）

13:30 － 13:45 CREST 岩田プロジェクト紹介 / ハイライト
岩田 覚 （東京大学）

10:40 － 11:20 ポスターセッション
11:20 － 11:45 CREST 加藤プロジェクト紹介 / ハイライト
加藤 直樹 （関西学院大学）

13:45 － 14:30 ポスターセッション
14:30 － 14:55 CREST 佐久間プロジェクト紹介 / ハイライト
佐久間 淳 （筑波大学）
14:55 － 15:10 CREST 平岡プロジェクト紹介 / ハイライト
平岡 裕章 （東北大学 原子分子材料科学高等研究機構）

11:45 － 11:55 ERATO 河原林プロジェクト ハイライト_Group2
11:55 － 12:35 ポスターセッション
12:35 － 14:00 昼食
14:00 － 14:30 基盤(S) 離散構造処理系プロジェクト紹介 / ハイライト
湊 真一 （北海道大学）

15:10 － 16:00 ポスターセッション
16:00 － 16:30 新学術領域研究 渡辺プロジェクト紹介 / ハイライト

14:30 － 14:45 CREST 宇野プロジェクト紹介 / ハイライト
宇野 毅明 （国立情報学研究所）

渡辺 治 （東京工業大学）
16:30 － 16:45 さきがけ ・ ACT-I研究者 ハイライト

14:45 － 15:30 ポスターセッション

16:45 － 17:30 ポスターセッション

15:30

17:30 － 18:15 ディスカッション

15:50 － 16:30 ポスターセッション

18:15 － 18:30 写真撮影

16:30 － 17:00 ディスカッション

18:30 － 20:30 懇親会

17:00

15:50 さきがけ研究者・ERATO 河原林プロジェクト ハイライト_Group3

閉会の挨拶ＥＲＡＴＯ後（２０１８，２０１９以降）は？

白紙！

Emtiyaz Khan (AIP)波多野 大督 （ＮＩＩ＆ＥＲＡＴＯ）
薗部 知大 （ＮＩＩ＆ＥＲＡＴＯ）
小西 卓哉 （ＮＩＩ＆ＥＲＡＴＯ）
原 聡 （ＮＩＩ＆ＥＲＡＴＯ）
照山 順一 （ＮＩＩ＆ＥＲＡＴＯ）
阿部 真人 （ＮＩＩ＆ＥＲＡＴＯ）
関口 卓也 （ＮＩＩ＆ＥＲＡＴＯ）
Man-Kwun Chiu (NII&ERATO)

Inference	   on	  Complex	  Bayesian	  Models	   using	  Simple	  Computations.
Mohammad	  Emtiyaz	   Khan	  and	  Wu	  Lin	  (AIP,	  RIKEN)q New	  method	  for	  inference	   probabilistic	  graphical	  models	  that	  contain	  difficult terms	  by	  using	  Stochastic	  Message-­‐Passing.
§ Non-­‐conjugate	  terms	  (e.g.	  in	  logistic	  regression,	  we	  have	  Gaussian	  distribution	  with	  logistic likelihood).
q Main	  Idea:	  conjugate	  approximations	  for	  non-­‐conjugate	  terms	  by	  using	  “proximal-­‐gradient”	  method.
§ E.g.	  approximate	  logistic	  likelihood	  by	  Gaussian,	  which	  converts	  logistic	  regression	   to	  linear	  regression.
q Benefit:	  Modular,	  scalable,	  generalizable,	  and	  convergent	  updates.

Computing Least Cores of Supermodular
Cooperative Game [AAAI 2017, to appear]
Daisuke Hatano(Joint work with Yuichi Yoshida)
Motivation: Sharing economy
Productive-Service System

Collaborative lifestyle

Redistribution markets

Need sharing for achieving the sustainable
and resilient economy
Our goal: Find a value division to the players
from which they have no incentive to deviate

Computing Least Cores of Supermodular
Cooperative Game [AAAI 2017, to appear]
Daisuke Hatano(Joint work with Yuichi Yoshida)
Core: A solution concept of the game

￥110

￥50

￥40 ￥70

Analyze the following solution concepts– Strong least core
– Weak least core
Our contribution
Derive explicit and concise formulations
for the strong and weak least core values￥50

Looking Inside Literal Blocks: Towards Mining More
Promising Learnt Clauses in SAT Solving

Tomohiro Sonobe
decision level0 ~ d-3

SAT instance:(a’ v b’ v x’)(b’ v y’)ab(c’ v d)(c’ v d’ v e):
(x v y v e’ v f )(e’ v f’)¬(xʼyʼ

decision level d-2

x’y’

decision level d-1
decision level ddfcef’

literal blocklearnt clausee) <=> (x v y v e’)Literal Block Distance (LBD)=2

Looking Inside Literal Blocks: Towards Mining More
Promising Learnt Clauses in SAT Solving

Tomohiro Sonobe

LBD=3

LBD=2

(a1 v a2 v a3 v a4)(a1 v a2 v a3 v a4)

a1 and a2 are turned out
to be in the same block•

Learnt clauses with potentially low LBD value should be preserved.

•

Learnt clauses with the same length and LBD are completely same?

(a1 v a2 v a3 v a4)(b1 v b2 v b3 v b4)

Both clauses have length=4 and LBD=2.
Features of literal blocks aﬀect updates of LBD?

Identifying Key Observers
to Find Popular Information in Advance小西 卓哉（NII） 岩田 具治（NTT）
林 浩平（産総研） 河原林 健一（NII）

ウェブ上の情報共有と流行予測•アイテム（情報）：メッセージ，写真，商品やサービス etc.

•選択（アイテムの共有）：リツイート，ブックマーク，レビュー etc.

•

将来流行しそうなアイテムを事前に察知したい
選択

いいね！

ユーザ

アイテム
流行

流行せず

観測者を経由した流行の早期検知•

観測者：エキスパート，ヘビーユーザなど•

どのように有用な観測者をみつけるか？
– 機械学習の特徴選択を応用して検出

流行度
自分

流行

情報共有

お気に入り

流行せず
観測者
時刻

アンサンブル⽊モデル解釈のためのモデル簡略化法
原聡（NII/河原林巨⼤グラフプロジェクト）、林浩平（産総研）• アンサブル⽊モデル：ランダムフォレスト、Gradient Boosted Treesなど• ⻑所：予測精度が⾼い。様々なデータに適⽤できる。
• 短所：学習したモデルの解釈性が低い。

• 提案法の概要
データ

学習

たくさんの決定木

提案法

簡略化したモデル…
決定木が多すぎて、どんなモデルが学習されたのかわからない！！

このモデルは4つのルールで（近似的に）記述できるよ！
各ルールはこんなのだよ！

• 結果の⼀例：エネルギー効率データ• 各建物について8個の特徴量、768データ• 建物のエネルギー消費量の予測（回帰）y提案法 - 簡略化された予測ルール (K = 5)

12.14

Wall Area ＜ 306.25, Overall Height ＜ 5.25

14.41

Wall Area ≧ 306.25, Overall Height ＜ 5.25

27.80

Wall Area ＜ 330.75, Overall Height ≧ 5.25

28.45

Wall Area ＜ 330.75, Overall Height ≧ 5.25, RoofArea ≧ 116.375, Glazing Area Distribution ≧ 437.23

Wall Area ≧ 330.75, Overall Height ≧ 5.25

建物 - ⼩→ 消費 - ⼩
建物 - 中→ 消費 - 中
建物 – ⼤→ 消費 – ⼤• ⼩数のルールで⼩さいMSEを達成できた。
ランダムフォレスト

提案法inTrees（Deng, ʻ14）

決定⽊

ルール数＞1000

51058

MSE

1.21

10.16

20.31

158.79Satisfiability Algorithms for
Read-k-times Branching Programs and k-IBDDs
Junichi Teruyama (NII, JST ERATO)
joint work with Atsuki Nagao(Univ. of Electro-Communications), Kazuhisa Seto(Seikei Univ.)

Branching Program (BP)◦ Computation Model◦ Representation of f : {0, 1}n → {0, 1}

root

BP Satisfiability (BP SAT)
◦ Find an assignmentthat reaches to the 1-sink◦ NP-Complete◦ Exhaustive Search: 𝟐𝒏 time𝒏◦ Can we solve in time 𝟏. 𝟗𝟗 ?
exponential speed-up

0-sink

1-sinkx1 x2 x3 : Output
0 0 0 : 10 0 1 : 00 1 0 : 10 1 1 : 1
1 0 0 : 01 0 1 : 0
1 1 0 : 1
1 1 1 : 0super-polynomial speed-up
𝛿Time: 2𝑛−𝑛 , 𝛿 = 𝛿 𝜖 , Size: 𝑛2−𝜖 , Space: Exp.

General[Chen, et al. (CCC2014)]⊂

Result 1

𝟏

Time:𝟐⊆Read k-times

k-IBDD

𝟏− 𝒌+𝟏 𝒏
𝟒,Size: poly(𝑛), Space: Poly.

exponential speed-up !!

Result 2

Time:𝟐𝟏
𝟐

𝟏− 𝒌 𝒏,Size: poly(𝑛), Space: Poly.
2-IBDD

exponential speed-up for linear size input
Time: 2 1−𝜇 𝑐 𝑛 , 𝜇 𝑐 = Ω1log

2𝑘−1 −1𝑐Input size: 𝑐𝑛, Space: Exp.
[Nagao, Seto, T. (WADS2015)]

Key Ideas Decomposing Read-k-times BPs
 Exhaustive Search for Disjoint Sets

Read-TwiceLine Separators of Unit Disk Graphs
Man-Kwun Chiu
chiumk@nii.ac.jp
National Institute of Informatics
Joint work with Paz Carmi, Matthew J. Katz, Matias Korman, YoshioOkamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada andShakhar SmorodinskyCarmi et al.

Line Separators of Unit Disk GraphsProblem Definition - Line separator in Unit disk graph

Unit disk graph G = (V , E ) :Each vertex vi represents a disk Di .
(vi , vj ) ∈ E iff Di ∩ Dj 6= ∅.

Carmi et al.

Line Separators of Unit Disk Graphs

Problem Definition - Line separator in Unit disk graph

A line α-separator S ⊆ V is a set of all the disksintersected by a line ` such that each of two open
halfplanes bounded by ` contains at most α|V | disks.
Objective : minimize α ∈ [1/2, 1] and the size |S|.
Carmi et al.

Line Separators of Unit Disk Graphs

Problem Definition - Line separator in Unit disk graphSA line α-separator S ⊆ V is a set of all the disksintersected by a line ` such that each of two open
halfplanes bounded by ` contains at most α|V | disks.
Objective : minimize α ∈ [1/2, 1] and the size |S|.
Carmi et al.

Line Separators of Unit Disk Graphs

Problem Definition - Line separator in Unit disk graph

A line α-separator S ⊆ V is a set of all the disksintersected by a line ` such that each of two open
halfplanes bounded by ` contains at most α|V | disks.
Objective : minimize α ∈ [1/2, 1] and the size |S|.
Carmi et al.

Line Separators of Unit Disk Graphs

Our Results

Upper bound on the size of the separator :For any unit disk graph with n disks and m intersecting
pairs
p of disks, there exists a line 2/3-separator of sizeO( (m + n) log n).
For any unit disk graph, √there is an axis-parallel line
4/5-separator of size O( m + n).
Lower bound on the size of the separator :For any unit disk graph, there does notline∗
p exist a √2/3-separator of size better than Ω( m log(n/ m)).

Carmi et al.

Line Separators of Unit Disk Graphs