荒瀬由紀
大阪大学大学院情報科学研究科

パラフレーズ（言い換え表現）
Relying on team spirit, expedition members defeated difficulties.
<-> Members of the scientific team overcame challenges
through teamwork.

自動QAや対話システムで重要な言語資源
文単位のパラフレーズでは応用しにくい、チャンクではマッチングが難しい。

構文木（森）をアラインメントすることで、フレーズを単位とする文法的なパラフレーズを効率的に獲得するモデルを提案
SS

Relying on team spirit <-> through team work
NPVP
VP
expedition
members <-> membersof the scientific team
Relying on team spirit expedition members defeated difficulties

S

defeated difficulties <-> overcame challenges…
VPNPVPPP

Members of the scientific team overcame challenges through teamwork非線形非負行列分解を用いたディープニューラル
ネットワーク計算手法の開発
今倉 暁(筑波大学 システム情報系・人工知能科学センター)☆ 背景・研究目的

 背景：DNN計算が画像認識等の分野で成果をあげている

 研究目的：バックプロパゲーション（BP）法と異なるア

プローチの解法として、非線形非負行列分解（非線形NMF）を用いた逐次最適化法を提案する

2017/12/25-26

情報系 WINTER FESTA Episode3@一橋講堂

1

研究内容

☆ 提案：非線形NMFを用いた逐次最適化法
 各最適化は制約・正則化項付き非線形NMF

制約・正則化項付き非線形NMF
非線形NMF☆ 数値実験：画像認識（MNIST）

古典的なBP法と同程度の性能
2017/12/25-26

バイアス・正則化項により過学習が抑制

情報系 WINTER FESTA Episode3@一橋講堂

2

私の研究対象小林 亮太 (国立情報学研究所)

イベント時系列データ解析に基づくWebデータマイニング
国立情報学研究所 小林 亮太
イベント時系列: あるイベントの起きた時刻のデータ
イベント
t1t2

データ

t3

コンテンツへのアクセス
コンテンツの投稿(動画の視聴、投稿)

発生

Webデータ(Twitter, Youtubeなど)

時刻問題

データ

予測

予測結果

N(t)=2t1 t2
観測期間t3
予測期間

論文
Kobayashi & Lambiotte, ICWSM 2016
Proskurnia et al., WWW 2017)ZQFS2VFTUJPOT6OTVQFSWJTFE5BSHFUJOHPGB'FX
&YQFSUTJO$SPXETPVSDJOH<$*,.ˏ>+JZJ -J :VLJOP#BCB )JTBTIJ ,BTIJNB ,ZPUP6OJW㼔Ꟍ㹺ָ㼰侧崢‫ה׌‬㢳侧寸‫כד‬姻瘶ָ䖤‫ְז׸׵‬! ֮‫㉏׷‬겗‫ךפ‬纇遚‫ך‬䠐鋅‫׾‬㢳侧寸瘝‫ד‬窟さ‫׃‬姻‫ְ׃‬瘶ִ‫׾‬䖤‫ְ׋‬! 姻瘶‫׾‬濼‫׷ְג׏‬㼔Ꟍ㹺ָ㼰侧崢‫ה׌‬ծ㢳侧寸‫כ‬㣟侁‫׷ׅ‬
WorkerQuestion ㉏겗

1 A A A E E A E D C A D C D D B C D B B E
2 A A B B C A D E B E E E E B B C D D E B
3 A A D C B E A E D C C C D E D E C D E D
4 A A A A D C D E B E A C E C B E D B D B

A A BⰋ‫㉏ךג‬겗‫ָ"ד‬姻瘶C B B C C A˟"։&‫ך‬䫛

D E C B A C A D E B E

A A A B E AC B B C E D A D A C E B C C A铎瘶ָ涪欰MVD㢳侧寸BDACAQuestionꬊ㼔Ꟍ㹺 ٓٝ‫חيت‬㔐瘶Question{䌢‫ח‬姻瘶㼔Ꟍ㹺Experts)ZQFS2VFTUJPOT6OTVQFSWJTFE5BSHFUJOHPGB'FX
&YQFSUTJO$SPXETPVSDJOH<$*,.ˏ>+JZJ -J :VLJOP#BCB )JTBTIJ ,BTIJNB ,ZPUP6OJW醱侧㉏‫ךד‬㔐瘶♧荜䚍‫ⵃ׾‬欽‫׃‬㼔Ꟍ㹺‫ך‬㔐瘶‫׾‬䓼锃! 㼔Ꟍ㹺ず㡦‫ך‬㔐瘶‫כ‬醱侧㉏‫♧ד‬荜‫ְָׅװ׃‬ծꬊ㼔Ꟍ㹺ず㡦‫ך‬㔐瘶‫♧כ‬荜‫ְֻח׃‬☞ 醱侧㉏‫㉏ךא♧ג׭הת׾‬겗‫׋׃ז׫ה‬ծ㉏겗)ZQFSRVFTUJPO ‫ח‬㼎‫׷ׅ‬㔐瘶‫ד‬㢳侧寸‫׷《׾‬1234(1, 2, 3)(1, 2, 4))ZQFSRVFTUJPO‫ח‬㢌䳔

(1, 3, 4)(2, 3, 4)Stochastic Packing Integer Programs with Few Queries
前原 貴憲 (理研AIP) 山口 勇太郎 (大阪大学, 理研AIP, ACT-I, 河原林ERATO, 岩田CREST)

Stochastic Matching Problem (with Few Queries)[Blum, Dickerson, Haghtalab, Procaccia, Sandholm, Sharma 2015]

入力 無向グラフ 𝐺෨ = 𝑉, 𝐸෨ , 適合確率 𝑝 ∈ 0, 1
出力 適合枝のみからなるマッチング 𝑀 ⊆ 𝐸

クエリ
（検査）

𝐺෨ = 𝑉, 𝐸෨

𝐺 = 𝑉, 𝐸• ペア臓器交換のモデル化の一種• 検査コストが高い → クエリ回数を減らしたいStochastic Packing Integer Programs with Few Queries
𝑛×𝑚𝑛𝐴 ∈ 𝐙+, 𝑏 ∈ 𝐙+;
𝑚𝑐ǁ ∈ 𝐙+: 確率的目的関数ベクトル• 各 𝑐𝑗ǁ は独立な確率変数で，クエリにより実現値を得られる• 各 𝑐𝑗ǁ の実現値は 𝑐𝑗− ≤ 𝑐𝑗ǁ ≤ 𝑐𝑗+ を満たす（𝑐𝑗± は入力の一部）• 𝑐𝑗ǁ = 𝑐𝑗+ となる確率は 𝑝 以上（𝑝 ∈ 0, 1 は入力の一部）

Q. クエリ回数と解の品質のトレードオフは？
• 全ての成分にクエリする → 普通の整数計画問題• 少ないクエリ回数で，それと遜色ない解を得たい

Approximately Stable Matchings with Budget Constraints
AAAI2018 accepted河瀬康志 (東京工業大学)

岩崎敦 (電気通信大学)

budget= 10:

cost
7util.
8:

6

5:

4

4:

3

5:

1

2

Nurse

Nurse

≻
budget= 3≻

1/1

Approximately Stable Matchings with Budget Constraints
AAAI2018 accepted河瀬康志 (東京工業大学)

岩崎敦 (電気通信大学)▶ 近似的に安定なマッチングを求めるメカニズムを構築▶ オンラインナップサック問題に対するアルゴリズムを応用

Hosp. Util.

Approximation Ratio
Non-Strategy-Proof mechanisms

Strategy-Proof mechanisms

Additive1
UB: 1−s

UB: ⌈ 1+ln(|D|−1)⌉1−s(incl. Proportional)1
LB: 1−s

Proportional

UB: 1+2 5 (≈ 1.618)(util.∝cost)√costs = max budget(if s > 1/2)√
LB: 1+2 5 (≈ 1.618)

LB: open1
UB: 1−s

LB: open

1/1計算量理論と回路最小化問題
平原秀一

東京大学 博士課程2年
日本学術振興会 特別研究員（DC1）
ACT-I 「情報と未来」研究者

Winter Festa Episode 3

2017年12月26日

論理回路• 論理回路は論理ゲートを組み合わせて構成される

例: 2入力XORを計算する回路

𝑥1 ⊕ 𝑥2∨
ORゲート

ANDゲート NOTゲート∧∧

𝑥1 ∨ 𝑥2𝑥1 ∧ 𝑥2

¬𝑥∨

∧

¬

¬

𝑥2
1
https://en.wikipedia.org/wiki/VLSI_Technology

𝑥1𝑥2

𝑥1𝑥2

¬𝑥𝑥➢ 出来る限り小さいサイズ（ゲート数）の回路を求めたい。

➢ コンピュータで自動的にそのような回路を求めたい。

回路最小化問題（Minimum Circuit Size Problem; MCSP）
入力

出力実現したい関数
𝑓: 0,1 𝑛 → {0, 1}の真理値表と自然数𝑠 ∈ ℕ

関数𝑓を計算するサイズ𝑠以下の（最小の）回路が存在するか？

（入力例）
𝑠=5

𝑓=

（出力）

“YES”

𝒙𝟏𝒙𝟐𝒙𝟏 ⊕ 𝒙𝟐000011101110(実際にXORを計算する右図のような回路が存在するので。)

我々の成果について
成果1：現在の証明技法の限界について[H. & Watanabe (CCC 2016)]✓ 乱択帰着の限界を示す初めての結果。

成果2：平均計算量と回路最小化問題の関係[H. & Santhanam (CCC 2017)]✓ MKTP ∉ coNPを示唆する初めての結果。

成果3：NPの中間の問題[Allender & H. (MFCS 2017)]✓ （任意の一方向性関数の存在の下で）初めて自然なNPの中間の問題GapMCSPを構成。