ERATO感謝祭
Convex Factorization Machine
for Toxicogenomics Prediction
Makoto Yamada, Wenzhao Lian, Amit Goyal, Jianhui Chen,Kishan Wimalawarne, Suleiman Khan,Samuel Kaski, Hiroshi Mamitsuka, Yi Chang

2Ad recommendation

Image recommendation

Yahoo!社ホームページ
https://www.yahoo.com/から転載

News recommendation

Recommendation• User-item matrix.
Item1
User1

A=

5

User2
User3

3

Item3
24

1

Item5

Item6223534

1

Item4

1
3

User4
User5

Item2

1543

• Goal: impute un-observed elements from theobserved data.
• Matrix completion has been widely used.

Factorization Machines

Rendle, ICDM 2010

• FM: A generalization of matrix completion.
k 0 item

A=zxi = [0 · · · 0yi = [A]k,k0 .

[A]k,k0user

k|U |}|
1|{z}k-th user{ z0 ···0 0 ···0|I|}|1|{z}k0 -th item

{0 · · · 0]> 2 Rd ,

Factorization Machines
Rendle, ICDM 2010

• Modeldd User item interactionXX>f (x; w, G) = w0 + w>
x+g0
` g `0 x ` x `0 ,User and item bias`=1 `0 =`+1

• FM is equivalent to matrix completion algorithm.
b k,k0 = w0 + [w0 ]k + [w0 ]|U |+k0 + g > gAk |U |+k0 ,• We can incorporate side information by simply
concatenating the information to input vector.
• However, it is non-convex algorithm L.

Convex Factorization Machine• Contributions of our paper are– We propose a convex variant of FMs, which is convex
and can get a globally optimal solution.
– The proposed algorithm is simple yet efficient.
– We show a convex Tucker-based tensor completion canbe solved through CFM.
– We applied the CFM to a toxicogenomics predictiontask. Then, it outperformed a state-of-the-art method.

• We want to convert all completion problem to FM
format and solve it with FM

Convex Factorization Machine• ModelBlondel et al., ECML 2015
Yamada et al. KDD 2017, arXiv 2015

f (x; w, W ) = w0 + w0> x +dd
X
X

W`,`0 x` x`0`=1 `0 =`+1

• CFM is equivalent to a convex matrix
completion algorithm.
bk,k0 = w0 + [w0 ]k + [w0 ]|U |+k0 + [W ]k,|U |+k0A• We formulate the optimization problem as asemi-definite programming and solve it withHazan’s algorithm (Frank-Wolfe).

Convex Factorization Machine: Updatingformula• Optimization problem: w, W
min kyw,Wf (X; w, W )k22 +2kwk
1
2s.t. W ⌫ 0 and kW ktr = ⌘• Eliminating w vector and only updates w.r.t. W.
w⇤ = (ZZ > +1I)
Z(y1 d+1fQ (X; W ) = [fQ (x1 ; W ), . . . , fQ (xn ; W )]> 2 Rn ,1fQ (x; W ) = tr(W (xx> diag(x x)))2z = [1 x> ]> 2 Rd+1 , Z = [z1 , . . . , zn ] 2 R(d+1)⇥nfQ (X; W ))8

Convex Factorization Machine: Updatingformula• Optimization problem w.r.t. W
min J(W ) s.t. W ⌫ 0 and kW ktr = ⌘W

J(W ) = (yfQ (X; W ))> C(yC = R> R +R = In1H>

H,Z > (ZZ > +H = (ZZ > +fQ (X; W )),1 Id+1 )1 Id+1 )11ZZ• We can efficiently solve it with Hazan’s algorithm.

9

10Frank-Wolfe algorithm

Frank & Wolfe 1956Algorithm 1 Frank Wolfe 1956
Let x(0) 2 D
for all t = 0, 1 . . . , T do
Compute s = argmin s2D hs, rf (x)i.
2
Update x(t+1) := (1)x(t) + s, =:= t+2.
end forConvergenceFW• Scale✓ ◆well.
1O• Easy
JO (n)✏SVT(ADMM)
Jaggi ICML 2013の図から転載

ComputationO✓

1p
✏

◆

O |U ||I|2

Memory(|U | + |I|)T|U | ⇥ |I|

Hazan’s Algorithm (Frank-Wolfe)
Algorithm 1 CFM with Hazan’s Algorithm
Rescale loss function J⌘ (W ) = J(⌘W ).
Initialize W (1) , the curvature parameter Cf = 1, and the number of iterations
T.
for all t = 0, 1 . . . , T do
Cf
Compute p(t) = approxEV
rJ⌘ (W (t) ), (t+1)
2 .
2↵
bt := t+2(or ↵bt = argmin ↵ J⌘ (W (t) + ↵(p(t) p(t)>W (t+1) = W (t) + ↵bt (p(t) p(t)> W (t) ).
end forreturn W (T ) .

W (t) ))).

• Key point: The approximated eigenvalue
decomposition can be estimated efficiently!
rJ(W (t) ) = XD (t) X > , D (t) = diag(ȳ (t)b (t) = (ZZ > ) 1 Z ȳ (t) , ȳ (t) = ywb (t) ),Z >w

fQ (X; W (t) )

11

12

CFM for tensor completion• Tucker-based decomposition can be written in FM!2
format! X
33XX
min{M(m) }3m=03
X

m=1[M(m) ]i,j,k =[M(0) ]i,j,k[Y]i,j,kz(1)
xi,j,k = [0diag(xi,j,kn1n2 n3}|
{ z· · · 0 |{z}1 0 ···0 0 ···0z}|1|{z}in2 (k 1)+jn2n1 n3jn3 (i 1)+kn3

n1 n2

kn1 (j 1)+iz}|{ z(2)
xi,j,k = [0 · · · 0 |{z}1 0 ···0 0 ···0
(3)xi,j,k = [0xi,j,k )) ,}|{ z· · · 0 |{z}1 0 ···0 0 ···0}|1|{z}(1) > (2) > (3) >xi,j,k = [xi,j,k xi,j,k xi,j,k ]> 2 Rd .

}|
1|{z}

{0 · · · 0]> ,{0 · · · 0]> ,(m)+m=1(i,j,k)2⌦

1tr W (xi,j,k x>i,j,k2[M(m) ]i,j,km=1

kM(m) ktr

(1)

[M(1) ]i,j,k = [M(1) ]i,n2 (k 1)+j ,(2)[M(2) ]i,j,k = [M(2) ]j,n3 (i 1)+k ,(3)[M(3) ]i,j,k = [M(3) ]k,n1 (j 1)+i .

{0 · · · 0]> ,• We can also write another tensor completion byFM.

13

Comparison to existing work
• Comparison to Blondel et al. 2015
Loss function

Optimization

Complexity

This work

Regression

Frank Wolfe W

O(T n)○Blondel et al.
2015

Regression/Classification

Coordinate
descentO(Tout Tin n)??

w, WTensor
Completion• Our method is much more simpler.
• Can be further speed up easily if we have betterFrank Wolfe algorithms.
• We applied CFM for biology data.

Movie Lens
• Movielens (100000〜20milion Ratings)

14

Toxicogenomics Prediction• Predict toxicity from data (Completion)2

6
A=4(1)
A1(1)
A2(1)
A3(2)
A1(2)
A2(2)
A3

Genome data Toxicity

zx = [0 · · · 0y = [A]i,j ,3327}|
1|{z}i-th gene37
5{ z0···0 0 ···078}|
1|{z}j-th drug2{ z }| {0 · · · 0 |{z}10]> ,
1st view

15

Toxicogenomics Prediction• Predict toxicity from data (Prediction)
2(1)A16A = 4 A(1)2(1)
A33(2)

A1(2) 7A2 5(2)A3Genome data Toxicity
78z}|{ zx = [0 · · · 0 |{z}10 ···0 0i-th drug(2)y = [Al ]i,k3}|
1|{z}k-th sensit.

{ z0 03}|1|{z}l-th cancer

2{ z }|{>0 xmean xstd ] ,16

Takehome message• Convex factorization Machine– We propose a convex variant of FMs, which is convex andcan get a globally optimal solution.
– The proposed algorithm is simple yet efficient.
– We show a convex Tucker-based tensor completion can besolved through CFM.
– We applied the CFM to a toxicogenomics prediction task.
Then, it outperformed a state-of-the-art method.

• The python code is available below:
http://www.makotoyamada-ml.com/cfm.html