• The University of Tokyo / RIKEN
  • tsuzukums.k.u-tokyo.ac.jp

Sinkhorn's theorem

Sinkhorn’s theorem

Sinkhorn’s theorem というのがある。Statementは以下(Wikipediaからコピペ)。

If A is an n × n matrix with strictly positive elements, then there exist diagonal matrices D1 and D2 with strictly positive diagonal elements such that D1AD2 is doubly stochastic. The matrices D1 and D2 are unique modulo multiplying the first matrix by a positive number and dividing the second one by the same number.

ここでいうDoubly stochastic matrix(二重確率行列)というのは、全要素が非負の行列であって、各行の和や各列の和が 全て$1$であるような行列のこと。

この定理を使うと、以下のようなことが言える。

全ての要素が非零の任意の$n\times n$複素行列$A$について、ある正実対角行列$D_1$と$D_2$が存在し、 の各行と列の全ての$\ell_2$-normが1になるようにできる。

これは$A$の各要素のノルムを要素とする行列に対してSinkhorn’s theoremを適用することでわかる。

以下はなぜこういうことを考えたくなるかという話。

問題

まず、でかいneural netが汎化しやすいのは初期値からあまりパラメータが動かないからではないかという話がある。 これは3-layer MLPとかでは実際に成り立っているっぽい。 一方で、より深くなったりすると成り立たなない。 特にnormalization layerとかがあるとまあダメそうだなというのは直感的にもわかる。 実際、実験したら初期値と最終的なoutputに相関が全然なかった。

fix

ところでWeight matrixは行や列ごとにscale dependenceがあるので、それを取り除いたら実は初期値と近いということもありうるのでは? という疑問が出てくる。 しかし、scaleを行や列から取り除くとはいかなることか、という問題が生じる。 そこでSinkhorn’s theoremにたどり着く。 どうも$0$要素があるときはうまく行かないっぽいが(これは元論文を読むとより納得がいく)、 適用範囲は十分に広いように思える。 この定理を無理やり適用して(実際に$D_1$と$D_2$を反復法で求めることができる)から 色々なバウンドを計算すると新たな知見が得られるかもしれないし、得られないかもしれない。 あと、Sinkhorn’s theoremの仮定はtraining methodにこれを利用して何かのregularizationをかけよう という時には問題にならない。詳細は略す。

Refs

この手の問題をmatrix scalingというらしく、surveyが手に入る。