Identifying statistically significant combinatorial markers
Raissa T. Relator1, Aika Terada2,3,1, Jun Sese*1,4
for survival analysis
AIRC, AIST, JST-PRESTO, Univ. of Tokyo, AIST-Tokyo Tech RWBC-OIL
1Survival analysis for finding statistically significant
biomarkers that statistically significantly affectsurvival of affected individuals
clinical data
genomic data(time+status)
A B C

68C1

C1

1: with marker
0: without marker

Survival Probability

Survival Probability

i+1

… CK

… C C

i+1

… CKiC2ifrequent
less frequentcombinations of Si’s combinations of Si’s

SNP_D,SNP_E
p=1.51e−11

SNP_A,SNP_B,SNP_C
p=7.03e−09
SNP_A*SNP_B*SNP_C=0
SNP_A*SNP_B*SNP_C=10Time… C C

Results show steep decline in survival probability oftargeted individuals

TimeTimeC2

PROPOSED METHOD
p-values

Survival Probability

survival time (yr)001
1001204060

80100Survival Time (months)

120

140

0.0 0.2 0.4 0.6 0.8 1.04

Conventional methodp-values

0.0 0.2 0.4 0.6 0.8 1.024High-order marker combinations are identified while
correcting for multiple testing

Survival Probability

011
100113

Survival Probability

censored(y = 0)

failed(y = 1)

0
1
10
1002

SNP_D*SNP_E=0
SNP_D*SNP_E=1

0

50

100

Survival Time (months)150正例度データからの二値分類
石田 隆(1,2,3) ニュー ガン(2,3) 杉山 将(3,2)(1) 三井住友アセット(2) 東京大学(3) 理化学研究所

正例は簡単に集められるが、負例は集められない！
そんな時、どうする？
通常の分類

アプリケーション

解きたい問題
正例

正例

マーケティング（購買予測）：••

負例

自社のお客様のデータ→アクセス可能ライバル会社のデータ→アクセス不可正例度データからの二値分類
石田 隆(1,2,3) ニュー ガン(2,3) 杉山 将(3,2)(1) 三井住友アセット(2) 東京大学(3) 理化学研究所

正例度の付いた正例から分類器を学習しよう！
正例度の例：自社の商品を過去に購入したお客様のアンケート情報など

提案法
正例度！

• 経験リスク最小化で実現• 最適な1/ 𝒏収束を達成
詳しくはポスターまで！

関係データに向けた混合エキスパートモデル (ICDM’17)

小山田 昌史 (NECデータサイエンス研)

 取り組む問題: ユーザ属性の推定
ユーザ属性行列（欠損あり）

購買履歴

 従来法 [Zhong+ WSDM’15]
 ユーザ属性間の相関を活用 (教師あり学習) Age, Income  Occupation

 購買履歴も因子分解し説明変数に
 Age, Income, a1, a2, …  Occupation

 課題: 因子を含む予測式は解釈が困難
𝐬𝐜𝐨𝐫𝐞[𝐨𝐜𝐜𝐮𝐩𝐚𝐭𝐢𝐨𝐧 = 𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐞𝐫]= 0.4 𝒂𝟑 + 2.3 𝐚𝐠𝐞 − 1.1 𝐢𝐧𝐜𝐨𝐦𝐞 …

商品属性行列

説明変数(ユーザ属性 + 因子) 目的変数

提案: 関係データ向け混合エキスパート
 従来法 (購買履歴の因子分解 + 説明変数化)
𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐞𝐫 = 3.4 𝒂𝟕𝟎 + 2.1 𝒂𝟐 + 1.5 𝐌𝐚𝐥𝐞 + ⋯解釈が困難な因子が予測式に出現

 提案法 (購買履歴に応じ、予測式を変える) スターウォーズを好むユーザの場合

𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐞𝐫 = 4.2 age_35−44 + 2.3 𝐌𝐚𝐥𝐞 + ⋯ 映画をあまりレビューしないユーザの場合

𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐞𝐫 = 1.2 age_25−34 − 0.1 𝐌𝐚𝐥𝐞 + ⋯2

Efficient Sublinear-Regret Algorithms for Online
Sparse Linear Regression with Limited Observation
伊藤 伸志(NEC) 波多野 大督(NII) 澄田 範奈(NII) 矢部 顕大(NEC)
福永 拓郎(JSTさきがけ) 垣村 尚徳(慶應義塾大学) 河原林 健一(NII)

問題設定-入力パラメータ 𝑘：
観測可能な特徴量の数-

入力データ（逐次的入力）：- タスク：逐次的にラベルの予測値を出力
For 𝑡 = 1,2,3, …
1. 特徴量の部分集合 𝑆𝑡 を選択（ 𝑆𝑡 ≤ 𝑘）
Output: 𝑆𝑡 = {1,4}
2. 選んだ特徴量だけを観測
Input: 𝑥𝑡1 𝑥𝑡2 𝑥𝑡3 𝑥𝑡4 𝑥𝑡5

𝒕 + 2-th example
𝒕 + 1-th example
𝒕-th example

3. 𝑦𝑡 の予測値 𝑦𝑡 を出力
Output: 𝑦𝑡

特徴ベクトル：𝑥𝑡 ∈ ℝ𝑑
𝑥𝑡1 𝑥𝑡2 𝑥𝑡3 𝑥𝑡4 𝑥𝑡5
ラベル： 𝑦𝑡 ∈ ℝ

データ元

4. ラベル 𝑦𝑡 を観測
Input: 𝑦𝑡

EndFor学習者目標- リグレット 𝑅𝑇 をできるだけ小さくしたい
𝑇𝑇𝑦𝑡 − 𝑦𝑡 2 −𝑅𝑇 =𝑡=1

アルゴリズムの出力（k 個の観測に基づく）

既存研究min𝑑𝑤∈ℝ , 𝑤 0 ≤𝑘𝑤 ⊤ 𝑥𝑡 − 𝑦𝑡 2
𝑡=1

最良の 𝑘-スパース線形回帰

非実用的- 劣線形リグレット（𝑅𝑇 = 𝑂(𝑇 1−𝛿 )）を達成する指数時間アルゴリズムが存在[Kale In COLT2014, Foster et al. In COLT2016]- 劣線形リグレットを達成する多項式時間アルゴリズムの構築は計算量的に困難[Foster et al. In COLT2016]（NP⊆BPPでない限り不可能）

本研究
入力データに仮定（スパースな生成モデルの存在など）をおいたうえで，劣線形リグレット を達成する 多項式時間 アルゴリズムを提案

Optimizing Network Reliability
via Best-ﬁrst Search over Decision Diagrams⻄野 正彬，井上 武，安⽥ 宜仁，永⽥ 昌明（NTT），湊 真⼀（北⼤）ネットワーク信頼性とはIEEE INFOCOM 2018で発表予定

リンクが確率的に故障するときに通信可能となる確率

2つの端点を結ぶ
通信ネットワーク

通信可能な故障パタン

通信不可能な故障パタン

ネットワーク信頼性を計算するためには通信可能な故障パタンをすべて数え上げる必要がある
Copyright©2017 NTT corp. All Rights Reserved.

1

Optimizing Network Reliability
via Best-ﬁrst Search over Decision Diagrams⻄野 正彬，井上 武，安⽥ 宜仁，永⽥ 昌明（NTT），湊 真⼀（北⼤）ネットワーク信頼性最⼤化問題
信頼性を最⼤とするNWの構成を求める問題

信頼性:

90%

信頼性:

91%

信頼性:

97%

解の候補の数だけNW信頼性の計算を繰り返す必要がある
難しい問題
⼆分決定グラフ(BDD)とA*探索を組み合わせることで、信頼性最⼤化問題の厳密解を⾼速に計算する⽅法を提案
Copyright©2017 NTT corp. All Rights Reserved.

2

スパースな情報源の可逆圧縮のための複数の木構造に基づく拡張Golomb-Rice符号
杉浦 亮介、鎌本 優、原田 登、守谷 健弘 （NTT CS研）


可逆圧縮に広く用いられるGolomb-Rice符号 [Rice 1961]

入力 𝑥012符号符号

符号（𝑟 = 0） （𝑟 = 1）

（𝑟 = 2）1101001

11013000101：：：

0101111

符号化のパラメータ𝑟(≥ 0)を増やせば分散の大きい情報源に対して最適
 𝑟 < 0となる符号は構成可能？

00
小さい分散だと？
𝑟 < 0？
入力 𝑥 の011001

指数分布に対して最適な
符号長：2017/12/25 情報系WINTER FESTA Episode3

𝑟=0
𝑟=1

確率分布
1𝑟
𝑝 𝑥 = 2−𝑥/2
𝑍𝑟

𝑟=2

入力 𝑥Copyright©2017 NTT corp. All Rights Reserved.

1

スパースな情報源の可逆圧縮のための複数の木構造に基づく拡張Golomb-Rice符号
杉浦 亮介、鎌本 優、原田 登、守谷 健弘 （NTT CS研）
XDGR (Extended-Domain Golomb-Rice) 符号の提案
𝑇0𝑇1100
𝐾 0010𝐾 0020𝐾 00300
𝐾 01 10
𝐾 0020
𝐾 00 3000

𝑇200
𝐾 10 10
𝐾 0020
𝐾 00 300

𝑇300
𝐾 1
1 10
𝐾 0020
𝐾 00 300

2017/12/25 情報系WINTER FESTA Episode3

複数の単純な木構造の組合せに基づいた符号化規則
スパースな指数分布
1 − 𝑥𝑟𝑝 𝑥 = 2 2 (𝑟 <0)
𝑍𝑟に従う情報源に対して最適な符号が簡単な構造で実現可能

入力：ノード （0, 1, 2, 3, …）
符号：エッジ （{0, 1}）
Copyright©2017 NTT corp. All Rights Reserved.

2

Published inOn the Model Shrinkage Effect of NIPS2017
Gamma Process Edge Partition Models
大濵 郁 (パナソニック/北大), 佐藤 一誠 (東大/理研), 喜田 拓也 (北大), 有村 博紀 (北大)

背景: 二値行列の重複構造分析

主結果: モデル縮退効果の解析と改良• 𝚪P Edge Partition Model (EPM) [Zhou, 15]• EPMのIntensity Function (IF)の解析– 二値行列に潜在する重複構造を抽出– 有効な基底数を自動的に推定することが可能
𝐽

EPMの生成モデル(二値化)(𝑇-Truncated ΓP)(gamma prior)(gamma prior)

3つの非負値項の積

Intensity Function (IF)𝐼𝐼 × 𝐽 Relational Data 𝒙

Overlapping Structure• EPMの問題点– モデル縮退が働かず有効基底数を過大評価– 結果として過学習を起こしやすい98個もの基底が有効と判断超パラメタの選択次第で縮退が妨害されることが判明• 効果的にモデル縮退が働くEPMの構成を複数提案– CEPM: ガンマ事前分布に制約を与えるモデル (Gibbs)– DEPM: 解が一意に決まるように問題を変換したモデル (Gibbs)– IDEPM: DEPMの無限極限を取った
モデル (Collapsed Gibbs)

IDEPM Solution

IDEPMはガンマ過程の無限個の基底を含めて全パラメータを周辺化できるため効率的に学習可能
Synthetic Data

EPM Solution

ArXiv Paper: https://arxiv.org/abs/1709.08770

p. 1/2

Published inOn the Model Shrinkage Effect of NIPS2017
Gamma Process Edge Partition Models
大濵 郁 (パナソニック/北大), 佐藤 一誠 (東大/理研), 喜田 拓也 (北大), 有村 博紀 (北大)

実験結果 (Enronデータの結果のみ抜粋)■テスト尤度 vs # of Epoch -0.055 0
IDEPMはDEPMよりも効率的 -0.060に収束することを確認
-0.065IDEPM
DEPM-T
CEPM-T
EPM-T

64
32100200300

400

168

IDEPM

-0.075

DEPM-128
248163264

Gibbs sampling iteration■テスト尤度 vs 経過時間
0-0.055
IDEPMはDEPMよりも高速に計-0.060
算できることを確認
-0.050-0.040-0.050 248163264

128-0.060TDLL-0.070TDLL-0.080128

Truncation level T-0.080-0.090-0.070-0.075-0.110-0.080
Truncation level T

0.350
0.300

TDAUC-PR0.2500.200
0.150
0.100
0.050
0.0002481632
Truncation level T64128

1020304050-0.065-0.100-0.120■リンク予測性能
提案モデルはリンク予測性能が改善．特にIDEPMは最も高いリンク
予測能力を示すことを確認

600-0.070

42■汎化性能提案モデルは汎化性能が改善．特にIDEPMは最も高い汎化能力を示すことを確認

500

TDLL

Estimated # of K

■モデル縮退効果
提案モデルであるCEPM,DEPM, IDEPMは正しくモデル縮退効果が働くことを確認

-0.050128

IDEPM
DEPM-64
DEPM-16
DEPM-4
Elapsed time (sec)

DEPM-128
DEPM-32
DEPM-8
DEPM-2

結論:・EPMのモデル縮退が働かない理由を解析・解析で得た知見に基づきCEPM, DEPMを提案
・近似無しの無限モデルであるIDEPMを提案
・IDEPMが汎化性能，リンク予測性能，計算速度の全てにおいて最高性能を示すことを確認
ArXiv Paper: https://arxiv.org/abs/1709.08770

p. 2/2