読者です 読者をやめる 読者になる 読者になる

分からんこと多すぎ

何故か就職できたので技術磨く。一人前の多重線形代数使いを目指しつつ、機械学習、データマイニングをやる

ゼロから始めるDeepLearning_その2_ホップフィールドネットワークとは

はじめに

学部四年生向け。

ゼロから始めるDeepLearning_その1_ニューラルネットとは - 分からんこと多すぎ
→(Auto Encoder)
→(Denoising AutoEncoder)
→ホップフィールドネットワーク(この記事)
ゼロから始めるDeepLearning_その3_ボルツマンマシンとは - 分からんこと多すぎ
→Restricted ボルツマンマシン(後日)
→(Gaussian Binary - Restricted Boltzmann Machines)
→(Deep Belief Networks)
→(Deep Neural Networks)
→畳み込みニューラルネット(後日)

太線以外は読み飛ばしてOK

知識に乏しく深く踏み込めなかったので、間違ってたらごめんなさい。

参考図書

An Introduction to Restricted Boltzmann Machines

CiNii 論文 -  統計的モデルとしてのボルツマンマシン

やっぱり麻生先生はすごい。長岡先生も説明が分かりやすい。

この記事と次の記事の概要

ボルツマンマシンには、ホップフィールドネットワークという前身がある。

ホップフィールドネットワークとは、1つの行列に複数の画像を埋め込む技術である。

ホップフィールドネットワークは、ノイズありの画像から元々のノイズなしの画像を復元できる。

ホップフィールドネットワークには、古典的な評価関数が存在し、これはエネルギー関数と呼ばれている。

エネルギー関数の微分をすると、次の時刻での素子の出力(要するにノイズなしの画素値)を求めることができる。

この更新は、マルコフ連鎖モンテカルロ法(MCMC)である。

個人的には面白かったが、この記事を読まなくてもRBMが理解できる説はある。
(エネルギー関数だけは重要)

今回できるようになること

まず画像データをもらってくる。標準画像

今回はこの画像データを、脳的なもの(ネットワーク:マルコフ確率場)に記憶させるアルゴリズムの話をする。

ここでは、2つの画像データを1つの脳的なものに記憶させる例を上げる。

記憶させたイメージその1(LENAの一部111*111画素)

記憶させたイメージその2(Cameramanの一部111*111画素)

この脳は連想記憶というものをもっていて、
適当なデータを投げ込むと、記憶の中にあるものを勝手に思い出す。

脳に入ったデータ(いわば視覚)

この情報(脳に入ったデータ)が、脳の中で記憶と照らし合わされることを、想起と呼ぶことにする。
(何か覚えがあるけど、あれってなんだっけ…と頭を捻っている感じ。
 想起するごとにイメージが鮮明になり、最終的に思い出す(元画像が復元される))
(注・勝手に想起とか言っているだけで、全然厳密な意味ではない)

5,000回想起後

10,000回想起後       

100,000回想起後

適当な視覚データから、記憶させた画像が取り出せたことが分かる。
(枯れ木が幽霊に見える原理はたぶんこんな感じ)

こういうことができると、ノイズの除去なんかに役に立つ。
(砂嵐が混ざった画像から、綺麗な画像を取り出せる)

今回のメインは、どうやってネットワークに記憶を埋め込むのかという話。

ちなみに、画像は本当に実験した結果。

同じ脳(ネットワーク)は、もう1つの画像(カメラマン)も同時に覚えているので、
こういう画像を見せると

こういう画像を思い出してくれる。

概要・ボルツマンマシンってなに?

1985 年にヒントンが作ったアルゴリズム

ボルツマンマシンは、グラフ構造上での状態遷移を確率的に扱うためのものである。

ホップフィールドネットワークというものを下敷きにしている。

意味がわからないので、ホップフィールドネットワークの説明する。

ホップフィールドネットワーク

上図のような、交差点に相当するもの(ノード:今回はiやj)を、
道路に相当するもの(エッジ:今回はwij)がつないだものを、グラフ構造と呼ぶ。

今回はw_{ij}=w_{ji}なので、無向グラフと呼ばれる。(対義語は有向グラフw_{ij} \neq w_{ji}

グラフ理論とかは、このへんでちょっと触れた。
グラフ(ネットワーク状)構造のクラスタリング(グループ分け)基礎:The Markov Cluster Algorithm(MCL)まとめた - 分からんこと多すぎ


ノードiには観測可能な出力x_{i}={-1,1}と、観測不可能な内部状態yiが存在する。

結合係数wは、ノードiの観測可能な出力x_{i}={-1,1}
記憶させるイメージ名sを用いて、次の式で設定する。

f:id:rishida:20140301030330p:plain

安定なネットワークを作るために、自己想起w_{ii}=0


ホップフィールドネットワークとは、以上のような想定の下で、
ネットワークに情報を記憶させるもののことである。


ホップフィールドネットワークをフローチャート的に書くと、以下のようになる。


0.ネットワークに記憶させるデータにしたがって、結合係数w_{ij}を設定する

1.ランダムにノードiを選ぶ

2.ノードの状態y_{i} = \sum_{j=1}^{N} w_{ij} x_{j} - \theta_{i} を計算する

3.ノードの状態y_{i} < 0なら、出力x_{i} = -1
 ノードの状態y_{i} = 0なら、出力x_{i}はそのまま
 ノードの状態y_{i} > 0なら、出力x_{i} = 1

4.以上を繰り返すと、最終的に記憶させた状態(ある定常状態)に至る
 (最初に記憶させたデータが取り出せる=人間の記憶の仕組みっぽい)
 (一種のセルオートマトンとも言える)


図的に説明する。

まず、25個のノードに、以下の2つのイメージを記憶させる。

この時、重みwは以下のように設計される(25*25の行列)
このwは計算式から一意に定まる。

この重みwが定められている時、
ランダムな初期状態(下図の一番上の状態)からフローチャートの2.と3.の更新を繰り返すと、一番下の状態に至る。

一番下の状態は、最初に記憶させたイメージの片方と一致する。
(完全に一致させるのは、何か色々難しいらしい)

ネットワークに乱数を突っ込むと、予め定めた定常状態に至る = ネットワークが情報を記憶している。

このように、相互に結合のあるネットワークに情報を記憶させるのが、
ホップフィールドネットワークである。
(Rのコードは最後に載せる)


ちなみに、最終的に定常状態に至るのは、
更新によってネットワークのエネルギー関数が常に減少する(安定な状態になる)ためである。

  

エネルギー関数

  エネルギー関数とは、要するに評価関数のことで、以下の様なものである。
  (エネルギー関数はボルツマンマシンでも出てくるので重要)

  E = - \frac{1}{2} \sum_{ij} w_{ij} x_{i} x_{j} + \sum_{i} \theta_{i} x_{i}

  この関数が小さな値を取る時、ネットワークが安定となることから、この関数はエネルギー関数と呼ばれる。

  ホップフィールドネットワークでは、この関数の鞍点のうちの1つを求めることができるが、
  必ずしも最下点であるとは言えない。


  以下、エネルギー関数が更新によって常に減少することの説明

    2.ノードの状態y_{i} = \sum_{j=1}^{N} w_{ij} x_{j} - \theta_{i} を計算する

    3.ノードの状態y_{i} < 0なら、出力x_{i} = -1
     ノードの状態y_{i} = 0なら、出力x_{i}はそのまま
     ノードの状態y_{i} > 0なら、出力x_{i} = 1

  という更新がホップフィールドネットワークの中では行われる。

  実は、2番の式はエネルギー関数のx_{i}による微分と等しい。

  y_{i} = \sum_{j=1}^{N} w_{ij} x_{j} - \theta_{i} = - \frac{\partial E}{\partial x_{i}}

  1個の変数x_{1}を持つある関数f (x_{1})テイラー展開は、
  関数f (x_{1})微分を用いて、以下のように表される。

  f (x_{1} + \Delta x_{1} ) = f (x_{1} ) + \frac{\partial \hat{f}}{\partial x_{1}} ( x_{1}  ) \Delta x_{1} + \cdots

  したがって、エネルギー関数は以下のように一次近似できる。
  (エネルギー関数の二次微分以降は0)

  E (x_{i} + \Delta x_{i} ) = E (x_{i} ) - y_{i} \Delta x_{i}

  今、y_{i} = \sum_{j=1}^{N} w_{ij} x_{j} - \theta_{i} = - \frac{\partial E}{\partial x_{i}} < 0だったとする。

  y_{i} < 0 なので x_{i} は -1 の値に変更される。

  ①.x_{i} = 1からy_{i} < 0x_{i} = -1に変更された場合 \Delta x_{i} = -2
   したがって、E (x_{i} + \Delta x_{i} ) = E (x_{i} ) - y_{i} \Delta x_{i} = E (x_{i} ) - ( - ) (-2) < E (x_{i} )

  ②.x_{i} = -1からy_{i} < 0x_{i} = -1に変更された場合 \Delta x_{i} = 0
   したがって、E (x_{i} + \Delta x_{i} ) = E (x_{i} ) - y_{i} \Delta x_{i} = E (x_{i} ) - ( - ) (0) = E (x_{i} )

  ①,②より、E (x_{i} + \Delta x_{i} ) = E (x_{i} ) - y_{i} \Delta x_{i} \leq E (x_{i} )

  y_{i} > 0の場合も同様である。

  以上のことより、出力xの更新によって(想起を重ねることによって)
  エネルギー関数が常に減少することが示された。



思いがけず重たくなったので、今回はここで終了。

次回はボルツマンマシン。

実装

ホップフィールドネットワークをRで実装する。

#使い方
if(FALSE){
  library('bmp')
  data1 <- read.bmp('Downloads/mono/LENNA.bmp')
  data2 <- read.bmp('Downloads/mono/Cameraman.bmp')
  #実際には大きすぎてメモリが足りないので
  #dataの一部を小さく切り出してください
  Mem <- list(data1, data2)
  huga <- hop.net(memory = Mem)
  image(huga$state[[100]])
}

#Hopfield networks
  #必須項目
  #non
    #オプション
    #dims.vec:記憶させるイメージの大きさ
    #p:記憶させるイメージの1の割合
    #theta:発火のしきい値の値
    #mnum:記憶させるものの数(ニューロン数の15%あたりが限界らしい)
    #memory:記憶させるイメージのリスト(0と1だけで表現される同じサイズの行列のリスト)
hop.net <- function(dims.vec = c(5,5), p = 0.3, theta = 0.5, mnum = 2, memory = NULL){
  #set memory
  if(is.null(memory)){
    memory <- list(NULL)
    #layout(matrix(c(1:mnum),nrow=mnum))
    for(i in 1:mnum){
      memory[[i]] <- matrix(rbinom(n = prod(dims.vec), prob = p, size = 1), nrow = dims.vec[1], ncol = dims.vec[2])
      memory[[i]][memory[[i]] < 1] <- -1
      #image_text(memory[[i]])
    }
  }else{
    mnum <- length(memory)
    for(i in 1:mnum){
      memory[[i]] <- round(memory[[i]])
      memory[[i]][memory[[i]] < 1] <- -1
    }
    dims.vec <- dim(memory[[1]])
  }

  #set weight
  w <- matrix(0, nrow = prod(dims.vec), ncol = prod(dims.vec))
  for(i in 1:mnum){
    w <- w + (as.vector(memory[[i]]) ) %*% t(as.vector(memory[[i]]))
  }
  diag(w) <- 0
  #image_text(w)
  browser()

  #remember memory
  state <- list(NULL)
  #state[[1]] <- matrix(rbinom(n = prod(dims.vec), prob = p, size = 1), nrow = dims.vec[1], ncol = dims.vec[2])
  state[[1]] <- memory[[1]] + rnorm(mean=0,sd=0.3,n=prod(dims.vec))
  state[[1]][state[[1]] > 1] <- 1
  state[[1]][state[[1]] < 1] <- -1
  huga <- list(NULL)
  for(i in 1:100000){
    print(paste(i, 'th iteration'))
    #ランダムにノードを選択
    id <- sample(x = c(1:prod(dims.vec)), size = 1)
    state[[i+1]] <- state[[i]]
    #ノードの出力を更新
    hoge <- w[id,] %*% as.vector(state[[i]]) - theta
    hoge <- sign(hoge) * sign(ceiling(abs(hoge)))
    #hoge <- ceiling(sign(hoge))
    state[[i+1]][id] <- hoge
    for(j in 1:mnum){
      #記憶が連想できたら終了
      if( sum(memory[[j]] == state[[i+1]]) == prod(dims.vec)){
        #dev.new()
        print('image is remembered')
        #layout(matrix(c(1:mnum),ncol=1))
        #for(k in 1:mnum){
          #image_text(memory[[k]])
        #}
        #dev.new()
        #layout(matrix(c(1:4),ncol=1))
        #for(k in c(1,(i-1),(i),(i+1))){
          #image_text(state[[k]])
        #}
        ans <- list(memory,state)
        names(ans) <- c('memory','state')
        return(ans)
      }
    }
    if( (i %% 1000) == 1){
      huga[[((i %/% 1000) + 1)]] <- state[[i]]
    }
    state[1:i] <- 1
  }

  #返り値
  #ans <- list(memory,state)
  ans <- list(memory,huga)
  names(ans) <- c('memory','state')
  return(ans)
}

#描画関数
#ネット上で公開されていたはずだが元コードが見つからない
image_text <- function(x,list.I=0,list.J=0,TEXT=TRUE,...){
  at_v <- 1/(2*(ncol(x)-1))
  at_v <- seq(0,1+2*at_v,by=at_v)-at_v
  at_h <- 1/(2*(nrow(x)-1))
  at_h <- seq(0,1+2*at_h,by=at_h)-at_h
  xy <- do.call("rbind",lapply(at_v[seq(2,length(at_v),by=2)],function(x,y) cbind(x,y),y=rev(at_h[seq(2,length(at_h),by=2)])))
  image(1-t(x[nrow(x):1,ncol(x):1])[ncol(x):1,])
  if(TEXT==TRUE){
        text(round(xy,2),labels=x)
  }
  abline(v=at_v[seq(3,length(at_v)-1,by=2)],h=at_h[seq(3,length(at_h)-1,by=2)],col=8)
  if(length(list.I)!=1){
        tmp<-unlist(lapply(length(list.I):1,function(i){length(list.I[[i]])}))
        abline(h=at_h[c(1,2*cumsum(tmp)+1,2*sum(tmp)+1)],col=1,lwd=3,lty=2)
  }
  if(length(list.J)!=1){
        tmp<-unlist(lapply(1:length(list.J),function(i){length(list.J[[i]])}))
        abline(v=at_v[c(1,2*cumsum(tmp)+1,2*sum(tmp)+1)],col=1,lwd=3,lty=2)
  }
  #return(list(v=at_v,h=at_h))
  return(1)
}

疑問

ホップフィールドネットワークのエネルギー関数は、なぜあの形になったのか。

w_{ij}x_{i},x_{j}の相関を一致させる一番簡単な式だから?