

gR"oiwjyO>`df
+/Bpsnj.jvlmwzk
6!E~4)3uox

~=S~ G<4U|1}

000

+/@

+/jvlmU+/jvlm;

000

000

+/jvlmwzk
 h0P
[fdW`A

90< 90@

psnjK2 psnj:+/jvlm<000 000

90<90> 90;90?

90=

psnj;

psnj<psnj=

•+/jvlm*_psnj*bo{mXeD^([f•L9a\caqzrvtpwnj7uoxa)3
•!%&2$$$& $"%%3! 4 ,&*$%
•Q%$^a(MYC

000



gR"oiwjyO>`df+/2psnj.jvlmwzkU

 VM+*jvlmwzk '?

90=<

90>@

*%&$:?

0 "$!
0%"#0$ !

0!
0$&"
0%&%%0 "0""#0#!0%0 $!#0*!

90=<

90>@

90<:
:

909:

psnj

!$
$ %

8T 2$%
"!'"!$"%'
"

90=>

90>>

90?A

!"$2

 
!&
$!!

000*%&$:=

000

*%&$@

000

000

0 ## !
0
jvlma
H;FB 0!"*%&$=000

*%&$;

90??


*##"$&&
&"$!

90<=

*$$!&*$
&+"$

$2+"$"2""&"&%&&%&






V  

2@0A=C90;?

2A0:;C90;9

2A09;C90;=

•-apsnjuox_5NZ~,Jo{ma8&CYV:)#/11""%0!#%01V;5N:` a#h!%&

5<6_Z]I

5:60 0 0;9:95;6!0;9::5<6"$*-0 0;99A

T-34: On Dimensionality
Recovery Guarantee of
Variational Bayesian PCA
Shinichi Nakajima (Nikon), Ryota Tomioka (Tokyo Univ.),
Masashi Sugiyama (Tokyo Tech.), S. D. Babacan (Illinois Univ.)
T HEORETICAL A NALYSIS OF BAYESIAN M ATRIX FACTORIZATION

Bayes posterior
0.2

B
0.3
0.2
0.1

0.1

0.2

0.2
0.3

0.1

0.3

0
0.1 .2

3

−2

VB

0.1

2

0.2

−2

1

Bayes

0.3
0.2
0.1

2

0.1

−1 0.0.23

0.30.2
0.1

0
A

0 0.1

0.3

−1

0.3

0.3

−2

1

0.3
0.2
0.1

0.3
0.2

−1 0.1

0.3 0.2
0.1

0.2 .1
0

−3
−3

0.3

0.2

0.3

−2

0.1
0.2
0.3

0.1

0.2

B

0.2
0.3

0.1

B

0.3
0.2
0.1

−1

0.
0.32

0.2

0.1

0.2
0 0.3

0.3

1

0

0.1.2
0 0.3

2 (A, B ) ≈ (± 1, ± 1)

0.1
0.2
0.3

0.1
0.2
0.3

MAP estimators:√√
2 (A, B ) ≈ (± 2, ± 2)

0.3

0.3

1

0.1

0.3

0.1 .20

2 (A, B ) = (0, 0)

FB
MAP
VB
PB

Bayes p osterior (V = 2)

3
MAP estimators:

0.1 0.2

VB-PCA (matrix factorization)

3

Bayes p osterior (V = 1)

3
MAP estimator:!
U

Bayes p osterior (V = 0)3

−3
−3
T HEORETICAL
OF
M
−3
−2
−1 A NALYSIS
01
2 BAYESIAN
3−3−2 ATRIX−1 FACTORIZATION
0
1
2
3
A

1

A

VB posterior

Figure 4: Bayes posteriors with ca = cb = 100 (i.e., almost flat priors). The asterisks are the MAP
solutions, and the dashed lines indicate
the ML(the modes
the contour
VB p osterior(V = solutions
0)
VB of
p osterior(V = 1) when33ca = cb = c → ∞).

0
A

B

2

3

0.05

B

0.1

0.1

0.1

5
0.0

0.1

−2

−1
0
1
2
A
VB p osterior (V = 2)
3
−3
−3
−2
−1
0
1
2
2 VB estimator : A√√(A, B ) ≈ (− 1.5, − 1.5)
1

3

−2

0.1

0.2

0.1

0.05

5

0.1

1

0.2

−3
−3

3

Like to directly prove good
property of VB!
−2

−1

0
A

10.1

2

3

0.1
5

5

0.05

0.25

0.3

0.1

0.2

0.1

0.25

−1

−1
0
1
2
A
0.2
VB p osterior (V = 2)

0.1

−2

−2

0.1

sparsity!

0.1−1 0.1

0.1

0.2
0.1

−3
−3

3
−3
−3
2

0.1

0.1

−2

0.2

0.3

0.1

−2

0.2

0.05

0.2

0.2
0.1

3

Figure 5: Bayes posteriors with ca 1= cb = 2. The dashed lines indicating the ML solutions are
identical to those in Figure0 4.
0
5
0.1
0.1 5
0.0

0.05

5

0.15

0.0

−2

0.0

−3
−3

−2

5

0.2

0.1

−2

−1

VB estimator :√√(A, B ) ≈ ( 1.5, 1.5)

0.2

0.0

−1

0.15 0.1
0.2

0.1

5

0.3

0.2
5

0.2

0.05

0.2

0.1 0.15
0.0
5

0.1
5
0.1

B

B

0.05

Bayes and VB behave
quite differently!

−1
−3
−3

0.3

−1

0.1

0.0

0.1

0.1

0.2

0.1

0
−2 0.1

3

0.2

0.1

0.0

5

0.2

0.2

0.0
5

B

B

B

0.2
0.1
0.3
0.3

0
−2

0.1

0.2

1
−1

0.1

0.3

0.05

2
V

5

0.2

0.1

00.1.0
5

1

0.0

0.1
0.15

0.15

0.1

1
−1
0.1

0.3

2
0

0.05

0.2

0.2

0

0.2

0.2

0.15

0.1

0.1

5

0.15

0.1

1

2
0

0.05

2

Bayes p osterior(V = 2)
0.05

3
1

0.0

0.1

VB estimator : (A, B ) = (0, 0)

2Bayes p osterior(V = 1)
0.05

3
1

0.05

VB estimator : (A, B ) = (0, 0)

2Bayes p osterior (V = 0)
3

0.15
0.1
0.05

When L = M = H = 1, Eq.(19) yields that the Bayes posterior p(A, B|V ) is given as
−3
−3

−2

!

−1

0
A

1

2

3

5

−1

0
A

1

2

3

"
1
A2
B2
p(A,
B|Vposteriors) ∝ exp and− VB(Vsolutions− BA)2when− 2L −= M2 =. 1 (i.e., the matrices(59)V , U , A, and B
Figure6: VB
2σ 2
2ca 2cbare scalars). When V = 2, VB gives either one of the two solutions shown in the bottomrow.

1

NIKON CORPORATIONCore Technology Center
November 8, 2012

Perfect dimensionality recovery
Theorem: In the large scale limit when,
the true PCA-dimensionality is recovered if1
ξ = 0.0
ξ = 0.1
ξ = 0.2
ξ = 0.4
ξ = 0.6
ξ = 0.8

0.5
0
0

1

2

3

4

5

y

(a) α = 1

Succes s Rate

Succes s Rate

Succes s Rateand1
ξ = 0.0
ξ = 0.1
ξ = 0.2
ξ = 0.4
ξ = 0.6
ξ = 0.8

0.5
0
0

1

2

3
y

(b) α = 0.5

451ξ = 0.0
ξ = 0.1
ξ = 0.2
ξ = 0.4
ξ = 0.6
ξ = 0.8

0.5
0
0

1

2

3

4

5

y

(c) α = 0.1

Figure 5: Success rate of dimensionality recovery in numerical simulation for M = 200. The
Weforderived
a sufficientconditionfor
VB-PCA
thresholdthe guaranteed
recovery (the second
inequality inEq.(28))is depictedto
with a verticalbar withthe same colorand line style.
perfectly
recover
the true dimensionality.
4.2

Perfect Recovery Condition2

T-35 Concurrent Q LearningとSarsa、Q学習の動的環境への適応能力
村上和謙 尾関智子 （東海大学）

Concurrent Q Learning
あらゆるゴールの可能性を同時に解決する強化学習手法
Q Goal1 s, a  と、 Q Goal 2 s, a 

Relaxation
AC  AB  BC

ならQ C  A, a   Q B  A, a * max Q C B, a  である
aの両方の価値を同時に学習する
A

B

Start
上式を
満たすように
修正する
C
Goal1

Goal2

実験

実験結果
ゴール位置変化
ゴールするまでのステップ数

ゴール位置変化

ゴール回数

200回ゴールで
環境変化

障害物変化

ゴールするまでのステップ数■：スタート
■：ゴール
｜：壁

障害物変化

ゴール回数

まとめ
 CQL-eはゴール位置の変化に対し、ほかの手法より対応が速い
 しかし、障害物の変化への対応について、優位性は見られない

T-­‐36	
  	
  	
  Eﬃcient	
  AUC	  Maximiza5on	
  by	
  Approxima5on	
  	
  	
  	
  
	
  	
  	
  	
  	
  	
  	
  Reduc5on	
  of	
  Ranking	
  SVMs	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  末廣大貴・畑埜晃平・瀧本英二（九州大学）	
Ranking	  SVM	

２部ランキング問題	
  
帰着	
  

ρ	

（正例と負例の各ペアに対し，	
  １つの正例を作成）	

ξi	

α	

O	

入力：p	
  個の正例と n	  個の負例	  
出力：線形関数 α	
  	
  
目標：	
  

問題点	

α	
入力：pn	
  個の正例	  
出力：線形関数 α	
  	
  
目標：	
  

! 問題のサイズが p	
  +	
  n	
  から pn	
  に増大	  
! 既存の効率化手法はマージンに関する理論保証なし	

提案手法	
  ・最適化問題の p	
  ×	
  n	
  制約条件を p	
  +	
  n	
  制約条件に近似（計算量改善）	
  ・非凸な制約条件を線形制約に近似（マージンに理論保証有り）	
  

	
  	
実験結果	
AUC比較	
Datasets	

Ranking	  SVM	

計算時間比較	(sec.)	
Our	
  Method	Ranking	  SVM	

Sample	  size	Our	
  Method	Noise	

K	

	
  
5%	

10	
  

0.9891	

0.9909	25	

0.206	

0.104	

30	

0.9611	

0.9648	50	
  	

0.3014	

0.162	

50	

0.8465	

0.8687	

100	

49.328	

0.238	

10	

0.9836	

0.9873	

200	

809.506	

0.530	

30	

0.9109	

0.9055	

400	

N/A	

1.814	

50	0.8759	

0.8852	

	
  
10%	

・AUC	
  はナイーブな手法に匹敵	
  ・計算時間はナイーブより超高速	
  ※共にノイズ5%の人工データ	

T-37 線形代数的アプローチによるノード置換不変な行列カーネルの構築
広瀬俊亮 (SAS Institute Japan)
行列を引数とするカーネルを構築したい
 構造データの比較は、データマイニングの重要な応用の一つ。
» NWの隣接行列や変数間の相関行列など、行列型のデータは多い。

要請： ノード置換不変な行列カーネル
1. 追加の情報なしで、単に行列同士を比較できること。
2. 次元の異なる行列を入力とできること。
3. ノード置換不変性» ノード置換をしてもカーネル
関数の値が不変：ノード置換
行列成分のラベルを入れ換え。
構造の実体は同じでも表現行列は変化。
1
Copyright © 2010, SAS Institute Inc. All rights reserved.

T-37 線形代数的アプローチによるノード置換不変な行列カーネルの構築
提案手法: 線形代数的なアプローチで行列カーネルを構成
 射影演算子： 入力行列を形式的に同じ次元に揃える。
» 異なる次元の行列を比較することが可能に。

 固有値分解： 射影演算子の作用を見え易くする。
固有値

n次元空間からs次元空間への射影演算子
固有ベクトル

 確率分布： 射影後のベクトルとして確率密度関数（無限次元）を採用。

提案手法 1. 入力行列以外の情報を必要としない。
（カーネル） 2. 異なる次元の行列を入力とできる。
の特長
3. ノード置換に対して不変である。

ノード置換不変かつ元のベクトルの情報をある程度保持している。

2
Copyright © 2010, SAS Institute Inc. All rights reserved.

T38 逐次的な重点サンプリングを用いたWAIC計算法
三木・渡辺[東工大]•WAIC(広く使える情報量規準)•任意の真の分布・学習モデル・事前分布に対して汎化誤差の不偏推定量となる•事後分布での期待値計算を含むので計算に時間がかかる•提案•逐次的重点サンプリング法を用いて事後分布を構成し，WAICを計算する•結論•十分な精度で効率的に計算できることが分かった

T38 人工データを用いた実験•混合正規分布モデル•真のコンポーネント数2•データ数1000•120セットの平均

コンポーネント数

1

2

3

4

計算時間[秒/セット]

34

62

96

136

汎化誤差

WAIC

コンポーネント数

T-39 パス追跡を用いた再重み付け

最小化アルゴリズム

新村 祐紀, 竹内一郎(名工大) 圧縮センシング スパースな信号の再現

 再重み付け
重み付き最小化

最小化 (従来法)
重みの更新

よりスパースな解を得られることが知られている

T-39 パス追跡を用いた再重み付け

最小化アルゴリズム

新村 祐紀, 竹内一郎(名工大) 従来法の問題点
 繰り返し線形計画問題を解くため, コストがかかる 本研究の目的
効率的な重みの更新を行い, 計算コストの削減を図る

 提案手法 パラメトリック計画法 (パス追跡) を利用

T-40

パラメトリック計画法を用いたマルチインスタンス SVM
石原 直樹, 久留美 里織, 竹内 一郎 (名工大)マルチインスタンス学習
バッグに対する 2 クラス分類問題
バッグ : インスタンスの集合 ⇒ 写真
インスタンス ⇒ 分割領域
バッグのラベル
正 : 少なくとも一つのインスタンスが正
負 : 全てのインスタンスが負インスタンスのラベルは未知.

Naoki ISHIHARAIBISML 2012

.

.

.

.

November 8, 2012

.

1/2

T-40

パラメトリック計画法を用いたマルチインスタンス SVM
石原 直樹, 久留美 里織, 竹内 一郎 (名工大)マルチインスタンス SVM

SVM の概念をマルチインスタンス学習に適用
非凸最適化問題
より良い局所解を求める
提案法
パラメトリック計画法
シミュレーテッドアニーリング.

Naoki ISHIHARAIBISML 2012

.

.

.

.

November 8, 2012

.

2/2

T-41

パラメトリック計画法を用いたSVMブートストラップ計算の高速化
鈴木 良規, 小川 晃平, 竹内 一郎(名工大)問題設定
ブートストラップ法を用いたSVMの統計的バラツキの推定
サンプル1

サンプル2

サンプル1000

・・・

多数回の学習に伴う計算コスト
2012/11/08

2012 IBISML

1

T-41

パラメトリック計画法を用いたSVMブートストラップ計算の高速化
鈴木 良規, 小川 晃平, 竹内 一郎(名工大)提案手法
パラメトリック計画法による効率的な学習
問題の変化量から解を追跡
解の変化が小さいときに効率的
より効率的な学習のためのスケジューリング
解の近さ

2012/11/08



アクティブセットの変化を予測



MSTに基づくスケジューリング

アクティブセットの違い

2012 IBISML

2

42
I-4-06

圧縮センシングに基づく自由視点画像合成の高効率化
Efficient free-view image synthesis based on the compressed sensing
東京理科大学大学院 工学研究科 電気工学専攻
苫米地 大 保坂 忠明 浜本 隆之
提案手法

自由視点画像合成
複数の実画像を基に，カメラの存在しない仮想視点からの画像を推定する技術
自由視点画像合成の手順
・複数の実視点画像を用いて被写体までの距離を推定
・三次元幾何を基に仮想カメラの画像を推定

研究目的
圧縮センシングに基づいてデータ量を削減提案手法の手順
・少数の線形観測値で距離を推定
・l1ノルム最小化により自由視点画像を再構成

問題点
被写体

自由視点画像合成におけるデータ量の増大
単画素カメラ1

被写体
実カメラ1

仮想カメラ

仮想単画素カメラ

単画素カメラ2

実カメラ2

圧縮センシングに基づき再構成推定された仮想カメラの画像推定された仮想カメラの画像

圧縮センシングに基づく自由視点画像合成の高効率化
Efficient free-view image synthesis based on the compressed sensing
東京理科大学大学院 工学研究科 電気工学専攻
苫米地 大 保坂 忠明 浜本 隆之

42

評価実験
実カメラと単画素カメラから取得されるデータ量の比を圧縮率Rと定義(R≦1)

Ground Truth

R=1/1627.69[dB]R=1/4
28.04[dB]R=1/2
28.24[dB]

・圧縮率Rを下げることに伴う画像劣化の程度が小さい・データ量を1/16に削減しても視覚的に良好な仮想視点画像が得られる

圧縮率Rと画質の関係(Wはパラメータ)

自由視点画像合成におけるデータ量の削減が可能

T-43: An Efficient Sampling
Algorithm for Bayesian Variable
Selection
荒木貴光 池田和司
奈良先端科学技術大学院大学

ギブス変数選択法
ベイジアン変数選択におけるサンプリング法
特徴：効率性が擬似事前分布，提案分布のパラメータに強く依存する．
従来法
これらパラメータをフルモデルに対する予備解析で決定パラメータが不適切な値となりアルゴリズムの効率
が下がる.

提案法
適応的ギブス変数選択法… サンプリングしながら擬似事前分布，提案分布のパラメータを自動調整する．

数値実験
予
測
分
布
推
定
値

非
効
率
因
子

提案法

提案法
従来法

iteration
s

従来法

まとめ
適切なパラメータ値を自動で獲得
効率性が向上反復回数

事後確率最大化推定に基づく圧縮センシングのデータ復元アルゴリズム

T-44

竹田晃人・樺島祥介 （東工大）★圧縮センシングy

低次元のy と F から
x 0が知りたい!

F

x

0

0

但し x は疎★  1 ノルム最小化解法

 ノルム  | x | を最小にする y = Fx の解を求める
i1i

線型計画問題… 計算量がデータサイズの3乗
データサイズが大きい場合は計算量がさらに小さい方が良い★ 事後確率最大化に基づく解法を提案
計算量がデータサイズの2乗(Fが疎行列ならデータサイズの1乗)★ 事後確率最大化解法の性能 (Fがi.i.d.ランダム行列の場合)
成功領域

成功率

 限界線
1

圧縮率

失敗領域

 ノルム最小化と1

ほぼ同じ性能が出る
x 0 の非零成分比★ 既知の確率伝搬法に基づくアルゴリズムとの関係も議論可能T45 疎データに対する並列 SGD のための属性割当最適化○林浩平 (東大)，藤巻遼平 (NECLA)

目的：SGD を並列化し高速計算

課題：計算時間が属性の割当て方に大きく依存
1/2

属性割当を最適化問題として定式化• 2 つの近似的解法を理論的・実験的に比較

2/2

T-46 新グラフィカルモデル「発火過程ネットワーク」

E(θ0 )ππ′MG

πE(θ1 )

E(θ2 )

E(θ3 )

従来のグラフィカルモデル 系全体で作られる単一のモデル多様体．学習は系全体に関わる重い処理．
提案モデル ノード毎の多様体．学習はノード毎の軽い処理．
.

高畠 一哉，赤穂 昭太郎 (産総研)

T-46

.

.

.

.

2012/11/08.

1/2

モデル分布の性質) データ分布 π と提案モデルが学習したモデル分布 π ′間の擬距離は π と各ノードの多様体間の KL ダイバージェ
ンスにより抑えられる．
∑
F CD(π||π ′ ) ≤c(i)KL(π||E(θi ))i

またデータ数無限大の極限では π ′ は π とともにデータが従う真の分布 πreal に概収束する．
実験結果) ちゃんと動く．
N = 726

N = 1000

アステラス
ドコモ

au TOPIX
ソフトバンク三菱商事

5x5 イジングモデル学習結果
高畠 一哉，赤穂 昭太郎 (産総研)

T-46

.

武田
日産
ホンダ
トヨタ
三井物産

11 銘柄株価陰陽学習結果.
.
.
.
2012/11/08.

2/2

漸近展開による近似精度の予測可能性

T-47

野村亮介 (東京大学)，日野英逸 (早稲田大学)，村田昇 (早稲田大学)，吉田朋広 (東京大学)

1．ヨーロピアン・プット・オプション

2．数値実験

確率微分方程式:{
dXtϵ = V0(Xtϵ, ϵ)dt + V (Xtϵ, ϵ)dwt, t ∈ [0, T ]2 次漸近展開の値 AE とモンテカルロ法の結果
M C の誤差率を|M C − AE|/|M C|

X0ϵ = x0となめらかな実数値関数 F に対して，期待値

E[max(K − F (XTϵ ), 0)]をヨーロピアン・プット・オプションと呼ぶ．ここで，K は権利行使価格 (ストライク) と呼ばれる定数である．

で定義し，この値が 1% を超えるかどうかをラン
ダムフォレストを用いて判別する．

Black–Scholes (BS) モデル:{
dXtϵ = aXtϵdt + ϵXtϵdwt, t ∈ [0, T ]X0ϵ = x0と，Constant Elasticity of Variance (CEV) モデル:
{
√ ϵ
ϵ
ϵ
dXt = aXt dt + ϵ Xt dwt, t ∈ [0, T ]つであるが，その精度は厳密に評価はできない．
ϵ
X
= x0
0
そこで，漸近展開による近似値をモンテカルロ法
漸近展開はこのような期待値を求める手法の一による値と比較する．

に対して，ヨーロピアン・プット・オプション

E[max(K − XTϵ , 0)] を求める問題を考える．

T-47
3．実験結果特徴量として，モデルのパラメータに加えて漸近展開で得られるいくつかの値を用いた．また，それらの二次の交互作用 (各特徴量の積を新たな特徴量とみなす) を考慮した．

4v.

10v.

15v.

14v.

120v.

図1

105v.

0.8
0.0

0.2

0.4

0.6

0.8
0.6
0.4
0.2
0.0

0.0

0.2

0.4

0.6

0.8

1.0

FPR=0.05

1.0

FPR=0.01

1.0

FPR=0.001

4v.

10v.

15v.

14v.

120v.

105v.

14v.

120v.

図2

14v.

120v.

105v.

120v.

105v.

105v.

1.0
0.0

0.2

0.4

0.6

0.8

1.0
0.8
0.6
0.4
0.2
15v.

15v.

FPR=0.05

0.0

0.2

0.4

0.6

0.8

1.0

FPR=0.01

0.0

10v.

10v.

BS モデルにおける各 FPR での TPR の比較

FPR=0.001

4v.

4v.

4v.

10v.

15v.

14v.

120v.

105v.

4v.

10v.

15v.

14v.

CEV モデルにおける各 FPR での TPR の比較

FPR: 誤差率 1% 以上であるデータ (Negative) を誤って判断する割合
TPR: 誤差率 1% 未満であるデータ (Positive) を正しく判断する割合

収益率が相互に影響する銘柄群と複数の制約条件を持つ
ポートフォリオ最適化問題の情報統計力学

先行研究（Cilibertiら，新里ら）

新里隆＠秋田県立大学
第15回情報論的学習理論ワークショップ
筑波大学東京キャンパス，発表番号T-48

各銘柄の収益率に独立同一分布を仮定し，期待収益率も0と仮定し，拘束条件が予算制約のみのポートフォリオ最適化問題について，最適解の最小リスクと分散投資達成度の典型的な振る舞いを 情報統計力学的手法を用いて解析してきた．しかしながら，実際の投資市場の特性である，
1.銘柄間に相関関係が含まれている
2.期待収益率が0でない
3.複数の線形不等式制約が課されているにおけるポートフォリオ最適化問題について十分に議論されているとは限らない．
研究目的
各銘柄の(1)収益率に相関構造を仮定し，(2)期待収益率も0ではなく，(3)拘束条件が予算制約と複数の線形不等式制約のあるポートフォ
リオ最適化問題について，最適解の典型的な振る舞いを情報統計力学的手法を用いて解析する．

得られた結果
1.
2.

先行研究[1,2]で議論した結果を含むことが示された．
先行研究[3]で提案された「今野・山崎予想」において，
平均分散モデル

平均絶対偏差モデル

今野・山崎予想が得られた．
平均分散モデルと平均絶対偏差モデルの最適解が一致する
参考文献[1]新里隆，安田宗樹：信学技報，Vol. 110, No. 265, pp. 257-264, (2010).
[2]新里隆，若井亮介，嶋崎善章，信学技報，Vol. 111, No. 96, pp. 125-130,(2011).
[3]H. Konno and H. Yamazaki: Man. Sci. Vol. 37, No. 5, pp. 519-531, (1991).

E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING

E-LEARNI G

E-LEARNI G

E-LEARNI G

E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNINGJICA Technical Cooperation Project for Research and Education
Development on Information and Communication Technology(PREDICT) Phase 2 (2012-2015) INDONESIA - JAPAN

Usage of Winnowing Algorithm and WordNet for Recognizing
the Possibilities of Paraphrasing Sentences in Academic Papers
Diana Purwitasari(1), Umi Laili Yuhana(1), Daniel Oranova Siahaan(1), Achmad Affandi(1),Yoshifumi Chisaki(2), Tsuyoshi Usagawa(2)T-49(1)Institut Teknologi Sepuluh Nopember, Surabaya-IndonesiA, (2) Kumamoto University, Japan
E-mail: (1)(diana, yuhana, daniel)@if.its.ac.id, affandi@ee.its.ac.id, (2) (chisaki, tuie)@cs.kumamoto-u.ac.jp

PROBLEM STATEMENTBACKGROUND
With Moodle …
lecturer could share learning materials, student could
send assigment reports...to support ecocampus.
As issue of plagiarism is getting popular, Moodle does
not have feature to help lecturer for checking thesimilarities of submitted reports.
Example: undergraduate students must sendreferenced papers and final report for their thesis;
students might translate referenced texts and submit
them as part of the report

IS PLAGIARISM HAPPENED ?
[DOCUMENT A]ENGLISH TEXTS[DOCUMENT B]
INDONESIAN TEXTSHow to recognize the possibilities of crossplagiarism?
(from English-Indonesian texts)
Note: reference texts are written in English andthe student might …
- translate the texts into another language(Indonesian) OR- make the (Indonesian) translation asparaphrased sentences(Kent & Salim, 2009) used ALMOST similar
procedures for cross-plagiarism between EnglishMalayu

SOLUTION
recognize paraphrased sentences byconsidering the usage of words withsimilar meaning(ADDITIONAL STEP from proceduresof (Kent & Salim, 2009))··

compare fingerprint of documents
NOT
directly compare sequences of text

USED LIBRARY:GOOGLE TRANSLATOR, WORDNET

PROCEDURES
1. translate Indonesian Texts of Document B into English Texts of Document B’ using Google Translator
Based on WordNet Library,
2. find pairs of sentences that semantically similar from A and B’
3. replace words inside each pair of sentences from A-B’ with their hypernim words… use semantic similarity value of words from WordNet to identify paraphrased sentences[DOCUMENT B’]ENGLISHTRANSLATED TEXTSBased on Winnowing Algorithm,
4. create fingerprints of document A and document B’
5. check similarity between fingerprints… ASCII values of n-grams from texts become document features

E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING

E-LEARNI G

E-LEARNI G

E-LEARNI G

E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNING
E-LEARNINGJICA Technical Cooperation Project for Research and Education
Development on Information and Communication Technology(PREDICT) Phase 2 (2012-2015) INDONESIA - JAPAN

Usage of Winnowing Algorithm and WordNet for Recognizing
the Possibilities of Paraphrasing Sentences in Academic Papers

T-49

Diana Purwitasari(1), Umi Laili Yuhana(1), Daniel Oranova Siahaan(1), Achmad Affandi(1),Yoshifumi Chisaki(2), Tsuyoshi Usagawa(2)(1)Institut Teknologi Sepuluh Nopember, Surabaya-IndonesiA, (2) Kumamoto University, Japan
E-mail: (1)(diana, yuhana, daniel)@if.its.ac.id, affandi@ee.its.ac.id, (2) (chisaki, tuie)@cs.kumamoto-u.ac.jp

CHECK PARAPHASED TEXTS[DOCUMENT A]… We propose several heuristics to predictchange propagation. We present aframework to measure the performance ofour proposed heuristics. ...

[DOCUMENT B]-INDONESIAN… Kami mengusulkan beberapa cara heuristik untuk
memperkirakan penyebaran perubahan, dan juga menyajikan
suatu kerangka kerja untuk mengukur kinerja cara heuristik. ...
[DOCUMENT B’]-ENGLISH… We propose a heuristic method to estimate thespread of the change, and also presents a framework
for measuring the performance of a heuristic way. ...
[DOCUMENT B*]… [some words in Document B’ have beenchanged with their hypernim words] ...

EXPERIMENT RESULTS
1.
Using 2 datasets: Set A (English Texts) and Set B (Indonesian Texts). Each set
contains 20 undergraduate thesis abstracts with 200-300 words.
The result is to set parameter for recognizing similarity of fingerprints:(i) window length = 10-grams; threshold for (ii) semantic similarity of sentences = 0.87
and (iii) fingerprint similarity of documents = 0.89
2.
Based on 10 abstracts of computer science journals and 5 abstracts of non-computerscience journals as Set A (English ver.), our experts create Set B (Indonesian ver.)The result is our system could not recognize some abstracts that have paraphrased
sentences (fingerprint similarity = 0.27) because there are significant changes on theirstructures and terms
3.
Using the same dataset from previous experiment, we compared results withprocedures of (Kent & Salim, 2009) based on Kappa Index (a kind of agreement between
two experts: the system and our experts).
Kappa Index for (Kent & Salim, 2009) = 0.55 while Kappa Index for our system = 0.92.
Therefore our proposed procedures still can identify plagiarism with paraphrased sentences
to some extent (no significant changes on structures and terms).

CREATE DOCUMENT FINGERPRINT , CHECK[A DOCUMENT][A DOCUMENT FINGERPRINT]

Winnowing
Algorithm
the classic problem inmachine learning(5-grams)"thecl"-" hecla"-" eclas""class"-"lassi"-"assic"- …

thethe classic
classic problem
problem ininmachinemachine learninglearning
thethe classic
classic problem
problem ininmachinemachine learninglearning thethe classic
classic
problemproblem inin machinemachine learninglearning
thethe classic
classic problem
problem ininmachinemachine learninglearning thethe classic
classic
problemproblem inin machinemachine learninglearning
thethe classic
classic problem
problem ininmachinemachine learninglearning
thethe classic
classic problem
problem ininmachinemachine learninglearning

12232-12268-1241112500-12195-1250812756-…...-12261

]
TA
EN
M
U
OC
[D

]
B*
NT
E
UM
OC
[D

REFERENCES
Myers, E. W. "An O(ND) Difference Algorithm and Its Variations",
Algorithmica 1(2): 251-266, 1986.
Schleimer, S., Wilkerson, D.S., & Aiken, A. " Winnowing: Local
Algorithms for Document Fingerprinting", Proc. of the 2003 ACM
SIGMOD Intl. Conf. on Management of Data, 76-85, 2003
Kent, C., & Salim, N. "Web Based Cross Language Plagiarism
Detection", Journal of Computing, 1(1): 39-43, 2009.
Parapar, J. & Barreiro, A. "Evaluation of Text Clustering Algorithms
with N-Gram based Document Fingerprints", Proc. of the 31st
European Conf. on Information Retrieval Research (ECIR), 645-653,
2009
Barron-Cedeno, A. "On the Mono-and Cross-Language Detection of
Text Reuse and Plagiarism", Proc. of the 33rd Intl. ACM SIGIR Conf.
on Research and Development in Information Retrieval, 914, 2010.
Pereira, R.C., Moreira, V.P. & Galante, R. " A New Approach for
Cross-Language Plagiarism Analysis", Multilingual and Multimodal
Information Access Evaluation, Lecture Notes in Computer Science
6360: 15-26, 2010.
Purwitasari, D., Priantara, W.S., Kusmawan, P.Y., Yuhana, U.L., &Siahaan, D.O. "The Use of Hartigan Index for Initializing K-Means++
in Detecting Similar Texts of Clustered Documents as a Plagiarism
Indicator", Asian Journal of Information Technology, 10(8-12): 341347, 2011.

.

T-50
.

スパースコーディングにおける基底行列生成のための単一母基底の学習
有竹俊光，日野 英逸，村田昇（早稲田大学）

スパースコーディングは少数の基底で信号を表現する枠組み

min ||y − Dx||22 subject to ||x||0 ≤ k0
x

y：観測信号，D：基底行列，x：係数ベクトル

基底行列を学習により獲得

提案手法
各基底が母基底と呼ばれるベクトルから窓の移動とダウンサンプリングを繰り返して生成されると仮定．
（下図）

アルゴリズムの幾何的解釈

母基底は• 基底行列の生成，• 基底行列の更新，• 基底行列の平均化の繰り返しで更新される．
また，直感的な幾何的解釈を与えることができる．

母基底からの基底行列の生成 D，基底行列の更新

U，母基底の更新 M の繰り返しで，母基底の空間
A，構造化した基底の空間 S，基底行列全体の空間
D を遷移しながら更新を行う．

T-51 特定物体認識とマルコフ確率場によるモノクロ画像の自動彩色法

松尾恒（東京大学教養課程）、牧野貴樹（東京大学生産技術研究所）

提案手法
入力のモノクロ画像について、参照画像を用いた特定物体認識の結果を考慮してマルコフ確率場による領域単位の色成分推定を行うことで自動的に彩色する
手法の概略①参照画像のSIFT特徴量と周辺の色情報の組を抽出してデータベースに格納 [事前処理]②彩色対象のモノクロ画像の
SIFT特徴点を検出③対象画像の領域分割④参照画像の絞込み＋
対応点検出で、領域に色成分と信頼度を設定⑤マルコフ確率場で色の補完と補正を行い合成する

T-51 特定物体認識とマルコフ確率場によるモノクロ画像の自動彩色法

松尾恒（東京大学教養課程）、牧野貴樹（東京大学生産技術研究所）
色の補完、補正のマルコフ確率場モデル

𝑎𝑟𝑔𝑚𝑖𝑛𝐶𝑟 1..,𝑛𝑘1 𝐶𝑟𝑖 −𝐶𝑟𝑗

𝑘2 𝐶𝑟𝑖 − 𝐶𝑟𝑖 ∗ 𝑐𝑜𝑛𝑓 𝑖 +𝑖subject to 0 ≤ 𝐶𝑟𝑖 ≤ 255 1 ≤ 𝑖 ≤ 𝑛𝑗 ∈𝑛(𝑖)

𝐷𝑖𝑓 𝑖, 𝑗 ∗ 𝐷𝑖𝑓(𝑖, 𝑗)

物体認識による信頼度付き色情報推定

𝐶𝑟𝑖 領域 𝑟𝑖 の色成分
𝐶𝑟𝑖 物体認識で推定された領域 𝑟𝑖 の色成分
𝑐𝑜𝑛𝑓 𝑖 領域 𝑟𝑖 の色成分の推定の信頼度
𝑛 𝑖 領域 𝑟𝑖 に近接する領域の集合
𝐷𝑖𝑓 𝑖, 𝑗 領域 𝑟𝑖 と領域 𝑟𝑗 の境界上でのモノクロ成分の最大の隔たり
𝑘1 , 𝑘2 パラメータ―

適用後

入力画像の特徴点周りのヒストグラムと参照画像で対応する特徴点周りのヒストグラムをマッチさせることにより領域単位の色成分推定を行う

まとめ• 高速かつ領域に忠実で物体認識を考慮した彩色が可能• 同一カテゴリーの画像を参照できないと良好な画像を得られない

T-52

線形回帰モデルにおけるNCスペクトラル
クラスタリングを用いた入力変数選択
京都大学 藤原幸一
線形回帰モデル（392）
物理モデル（25）
非線形回帰モデル（12）グレイボックスモデル（9）

産業界における数理モデルの利用（JSPS143委員会調査）

生産性向上のために線形回帰モデルの効率的構築が必要

入力変数のクラスタリング・選択
1. 入力変数を相関関係に従ってクラスタリング
2. 出力予測の寄与の降順に，変数グループを選択
3. 選択された変数を用いて，線形回帰モデルを構築
Purge
T431

Feed

RMSE

T432

Product Etylene

C351
Propylene compressor

R

PLS

28.7

0.88

物理知識

23.8

0.88

Lasso

28.1

0.88

Stepwise

26.6

0.89

提案法

18.0

0.92

Ethane

昭和電工エチレン精留塔のエタン濃度予測モデル

T-53

M元位相偏移変調によるCDMA通信のレプリカ解析
加藤 弘之(関西大学大学院)

岡田 真人(東京大学，理研)

三好 誠司(関西大学)

Q
010

・Q状態連想記憶モデルのレプリカ法による解析
・BPSK/CDMAのレプリカ法による解析(J.Cook, 1989)(T.Tanaka, 2002)→M元位相偏移変調によるCDMA通信のレプリカ解析

110

111

001

000

101

I

100

M元位相偏移変調(M=8)

Overlap

Overlap

RS解011

復調の逆温度

T-54

クラスタリングに基づく
局所的半教師付きガウス過程回帰
カク シンロ（神戸大） 安村 禎明（芝浦工大） 上原 邦昭（神戸大）

背景

目的• 回帰とは，既存の訓練データに基づいて，新たな• ラベルなしデータを利用するために隣接グラフを定義

入力に対する出力値を予測することである• 隣接グラフの情報をガウス過程の枠組みに組み入れ• グラフを用いた半教師付き手法が分類問題に適用

半教師付き回帰で用いる分布を導く• ガウス過程の計算効率問題を解決するために，クラ• 半教師付き回帰に関する研究が注目

スタリングの枠組みを導入 x − x 2j
exp− i 隣接
w ij = 


2δ



非隣接
0


提案手法
w ij

Dii = ∑ j wijX

L = D −W⇒

∆ = λ ⋅ Lυ

ラベルなしデータから学習するために隣接グラフを利用
目的関数：

p( y | G ) = Ν (0, Σ )p( f* | x* , X , y, G ) = Ν (µˆ , C )勾配下降法によって最適パラメータを求める

なお，出力の予測平均値と標準偏差~ T −1µˆ = k* Σ y~ ~~C = k** − k*T Σ −1k*

ここで，

(

Σ = K −1 + ∆) +σ I−1(

グラフの隣接情報を目的関数に組み入れた

2

kij = c ⋅ exp − ∑d =1 bd ( xid − x dj ) 2
D~−1
kij = kij − kiT (I + ∆K ) ∆ k j

)

T-54

クラスタリングに基づく局所的半教師付きガウス過程回帰
カク シンロ（神戸大） 安村 禎明（芝浦工大） 上原 邦昭（神戸大）

クラスタリング

数値実験
提案手法の回帰誤差

入力X

クラスタリングを導入した場合の実行時間

クラスタリング
X1

X2

…

Xk
y

半教師回帰
M1

M2

…

Mk

クラスタリングを導入した場合の回帰誤差
xt

yt = ∑ x ∈i pti ∗ M i ( xt )tまとめ ラベルなしデータには，モデルの訓練に役に立つ情報が含まれ，この情報を有効に利用している 従来手法よりも上か同等であり，多くのデータセットにおいて，精度が改善（平均 12.98%）
 クラスタリングの枠組みを導入すれば，計算時間を最低2/3に短縮，精度向上する可能性もあるT-55

ロジスティック回帰モデルを組み合わせた
順序回帰モデルと高速な疎Bayes学習

長島主尚，井上真郷（早稲田大学）• 順序データとは– 出力ラベル間に既知の順序関係があるデータ例）レビューのランク，学校の成績，出世魚など
不
可

可

良

優
試験の点数など• 順序回帰問題とは– 順序データのマイニングや予測を行う問題設定

T-55

ロジスティック回帰モデルを組み合わせた
順序回帰モデルと高速な疎Bayes学習

長島主尚，井上真郷（早稲田大学）

Automatic Relevance Determination（ARD）との相性• 既存モデル– 𝑃 𝐭|𝐗 ≡ 𝑁
𝑛=1 𝑓1 𝑥𝑛 − 𝑓2 𝑥𝑛– 解析が困難• ARD事前分布の導入は可能だが、高速な解法は得られない• 提案モデル– 𝑃 𝐭|𝐗 ≡ 𝑁
𝑛=1 𝑔1 𝑥𝑛 𝑔2 𝑥𝑛– 解析が容易• ARD事前分布の導入と簡単な近似により、高速に解けるT-56	

経路路アノテーションからの学習による無線LAN位置推定の簡易易な構築
川尻亮亮真，下坂正倫倫，福井類，佐藤知正  (東⼤大)•背景:  無線LAN位置推定のための訓練データ収集コストが⾼高い– 機械学習を⽤用いて実測したデータから推定する研究が主流流••提案:  経路路アノテーションを⽤用いた無線LAN位置推定の簡易易な構築
貢献:– 経路路アノテーションによる簡易易な訓練データを収集⼿手法を⽰示した– 経路路アノテーションのための機械学習をSelf-‐‑‒Trainingとして定式化
従来⼿手法
全ての電波情報に位置情報を付与
時間がかかる

提案⼿手法:  経路路アノテーション
・移動しながら電波測定
・ときどき移動した        経路路を描くだけ
・短時間に多量量のデータ
・経路路ラベルの割り当てを推定・学習する問題に

ICS	
 Intelligent  Cooperative  Systems  Lab.  The  University  of  Tokyo1隠れ変数を持つ構造推定の学習として定式化	
  1.  隠れラベル推定

2.  パラメータ更更新

経路路制約の下で⾼高速かつ安定に解ける

Route Labels

Time

Fingerprints

距離離誤差を組み込んだコスト考慮型最⼤大マージン法

繰り返し

start

end

距離離誤差

損失

マージン

実験	
  

40 m

提案⼿手法により，	
  
短い時間で収集した
データにおいても	  ⾼高精度度での推定を実現	
  

環境地図
ICS	
 Intelligent  Cooperative  Systems  Lab.  The  University  of  Tokyo

高精度	

50 m

Mean error [m]10010Commercial
Systems

5
Label Propagation
2.5

k-NN

Gaussian Process
Route Annotation

1.0
0
100
300
Deployment Time for 1 Floor [min]短時間での収集	2

T‐57 解の多重度を考慮した混合分布モデルはより良い解をもたらす
古川徹生（九州工業大学）

何が問題か
ラベルを付け替えたものは
本当に同じと思って良いのか？

２つは同じ
こと？

ケース１

ケース２



(a)

(b)









(c)



෥
࢟



(a)








真の事後分布

y*

変分ベイズ



(b)


y*



(c)



෥
࢟
෥
࢟

෥
࢟

多重度考慮
変分ベイズ

多重度を考慮しなくても推定結果は同じ

真の事後分布

変分ベイズ

多重度考慮
変分ベイズ

多重度を考慮すると推定結果が変わるT‐57 解の多重度を考慮した混合分布モデルはより良い解をもたらす
古川徹生（九州工業大学）

提案手法

ラベル置換を表現する潜在変数 π を追加
逆温度パラメータ  を見かけ上大きくすることに相当
通常の責任率

多重度考慮型責任率

数値実験
さまざまな初期値から計算．
局所解（赤）に陥るケースがなくなった．







従来法







提案法

59

MCMC Strategy for Protein Complex Prediction
Using Cluster Size Frequency
Daisuke Tatsuke and Osamu Maruyama (Kyushu Univ.)

We propose a sampling method, called PPSampler, for predicting protein complexes
using the following two prior knowledge:
PPI network:

6

densely connected
subgraph

1

2

known
protein complex

9

7

4

3

8
5

power-law: 𝑦 ∝ 𝑥 −𝛾

Well-known observation: Dense subgraphs andknown complexes often overlap each other.
scoring subfunction f1(C)𝑓1 𝐶 ≡𝑑∈𝐶 𝑓1 𝑑

where C is a partition of a given set of proteins.

𝑤 𝑢, 𝑣 : weight of the interaction between proteins 𝑢 and 𝑣.
𝑁: upper bound on the size of a cluster0
𝑖𝑓 𝑑 = 1−∞
𝑒𝑙𝑠𝑒 𝑖𝑓 𝑑 > 𝑁 𝑜𝑟 ∃𝑢 ∈ 𝑑, ∀𝑣 ≠ 𝑢 ∈ 𝑑, 𝑤 𝑢, 𝑣 = 0
𝑓1 (𝑑) ≡𝑤(𝑢, 𝑣)𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒𝑢,𝑣(≠𝑢)∈𝑑

New observation: The distribution of thefrequency of protein complexes w.r.t.
complex size is power-law.

59

MCMC Strategy for Protein Complex Prediction
Using Cluster Size Frequency
Daisuke Tatsuke and Osamu Maruyama (Kyushu Univ.)
scoring subfunction f2(C)𝜓𝐶 𝑖 : relative frequency of clusters of size 𝑖 in 𝐶
𝜓 𝑖 : predefined target number for relative frequency for size 𝑖
𝑓2 𝐶 ≡

𝑁
𝑖=2

Results:12
1+𝑖 2 ∙ 𝜓 𝑖 −𝜓𝐶 (𝑖)scoring subfunction f3(C)𝑠 𝐶 : number of proteins within clusters of size 2 or more in 𝐶
𝜆 : predefined target number for 𝑠(𝐶)1𝑓3 𝐶 ≡(𝑠 𝐶 − 𝜆)2
1+
103

scoring function and its probability

𝑓 𝐶 ≡ −𝑓1 (𝐶) ∙ 𝑓2 (𝐶) ∙ 𝑓3 (𝐶)𝑓(𝐶)
𝑃(𝐶) ∝ exp −𝑇
Partitions of proteins are generated as samples from P(C)by the Metropolis-Hastings algorithm.

••

Precision of PPSampler is 70% higher than
the second one.
F-measure of PPSampler is 30% higher than
the second one.

Concluding Remarks:•

About half of predicted clusters notmatched with any known complexes are
statistically significant wrt Gene Ontology.

T-­‐60	

Cavity法による次数相関のある
相互依存型ネットワークの解析
渡辺駿介

樺島祥介

東京工業大学大学院

2010年，S.V.Buldyrevらは，少数のサイトの故障がネットワーク全体に連鎖する現象の数理モデルとして相互依存型ネットワークを提案した． （Nature,
vol464,	
  pp1025~1028,	
  2010）．	
  cascade phenomena	

本研究では，次数（各サイトが持つ結合数）の相関がこの現象に与える影響を調べる	
  

概要	

結果	

結論	

the most robust	

“内”での相関が正に高く，“間”での相関が負に高いシステムが最もロバストである．