ゼロから始める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 論文 - 統計的モデルとしてのボルツマンマシン

ニューラルネットワーク情報処理―コネクショニズム入門、あるいは柔らかな記号に向けて

作者: 麻生英樹
出版社/メーカー: 産業図書
発売日: 1988/06
メディア: 単行本
この商品を含むブログを見る

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

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

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

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

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

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

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

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

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

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

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

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

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

記憶させたイメージその１（LENAの一部111*111画素）

記憶させたイメージその２（Cameramanの一部111*111画素）

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

脳に入ったデータ（いわば視覚）

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

5,000回想起後

10,000回想起後　　　　　　　

100,000回想起後

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f:id:rishida:20140301030330p:plain

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

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

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

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

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$

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

図的に説明する。

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

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

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

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

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

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

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

エネルギー関数

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

　　 $E = - \frac{1}{2} \sum_{ij} w_{ij} x_{i} x_{j} + \sum_{i} \theta_{i} x_{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$

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

　　実は、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} < 0$ で $x_{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} < 0$ で $x_{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$ の場合も同様である。

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

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

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

実装

ホップフィールドネットワークを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}$ の相関を一致させる一番簡単な式だから？