機械学習手習い: 暗号解読
「入門 機械学習」手習い、7日目。「7章 最適化:暗号解読」です。
最適化について学び、それを使ってシーザー暗号を解読するシステムを作ります。
# 前準備 > setwd("07-Optimization/")
最適化とは
最適化とは、設定で動作を変更できる機械と、その機械がうまく動作しているかを計測する指標があるときに、もっともうまく動作する設定を見つけることです。
実は、5章 回帰分析 で、身長から体重を推測する関数を作る際に、最適な切片と傾きを求めるため最適化が使われています。分析で使用した lm 関数が、内部で誤差関数と最適化アルゴリズムを使い、最適な切片と傾きを算出してくれていました。
> heights.weights <- read.csv(file.path('data', '01_heights_weights_genders.csv')) > coef(lm(Weight ~ Height, data = heights.weights)) (Intercept) Height -350.737192 7.717288
lmは二乗誤差を誤差関数として使用しています。Rのコードにすると以下のような処理になります。
> squared.error <- function(heights.weights, a, b) { predictions <- with(heights.weights, height.to.weight(Height, a, b)) errors <- with(heights.weights, Weight - predictions) return(sum(errors ^ 2)) }
切片と傾きそれぞれで、1,0,-1のパターンで、二乗誤差を出力してみます。
> height.to.weight <- function(height, a, b) { return(a + b * height) } > for (a in seq(-1, 1, by = 1)) { for (b in seq(-1, 1, by = 1)) { cat(a, b, squared.error(heights.weights, a, b), "\n") } } -1 -1 536271759 -1 0 274177183 -1 1 100471706 0 -1 531705601 0 0 270938376 0 1 98560250 1 -1 527159442 1 0 267719569 1 1 96668794
a,bの値を変えることで、二乗誤差が変動しています。 最適化問題は、誤差関数(目的関数)の結果がなるべく最小、または最大になるようなパラメータを探す問題です。
optimを使ってみる
Rでは、さまざまなアルゴリズムで最適化問題を解いてくれる便利な関数 optim が提供されているので、これを使ってみます。
# 身長から体重を推測する関数の最適値を探す例 > optim(c(0, 0), function (x) { squared.error(heights.weights, x[1], x[2]) }) $par [1] -350.786736 7.718158 $value [1] 1492936 $counts function gradient 111 NA $convergence [1] 0 $message NULL
引数で、最適化するパラメータの開始点と、パラメータを使って値を計算する関数を指定します。
実行すると、$par の値として、パラメータの最適値が出力されます。
optimでリッジ回帰問題を解いてみる
optim の使い方がわかったので、これを使ってリッジ回帰問題を解いてみます。
リッジ回帰とは、正則化を取り入れた特殊な種類の関数で、通常の最小二乗回帰と誤差関数が違うものらしい。
まずは、リッジ誤差関数を定義。
> ridge.error <- function(heights.weights, a, b, lambda) { predictions <- with(heights.weights, height.to.weight(Height, a, b)) errors <- with(heights.weights, Weight - predictions) return(sum(errors ^ 2) + lambda * (a ^ 2 + b ^ 2)) }
optim で解きます。
# 本来は交差検定で求めるもの。簡略化のため、今回は1が最適とわかっていると仮定して計算。 > lambda <- 1 > optim(c(0, 0), function (x) { ridge.error(heights.weights, x[1], x[2], lambda) }) $par [1] -340.434108 7.562524 $value [1] 1612443 $counts function gradient 115 NA $convergence [1] 0 $message NULL
解けました。
暗号解読
最適化問題のケーススタディとして、メトロポリス法というアルゴリズムを使って、シーザー暗号を解きます。(optim使わないのかよ・・・。)
まずは、文字列をシーザー暗号で暗号化する関数を定義。
> english.letters <- c('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z') > caesar.cipher <- list() > inverse.caesar.cipher <- list() > for (index in 1:length(english.letters)) { caesar.cipher[english.letters[index]]<- english.letters[index %% 26 + 1] inverse.caesar.cipher[english.letters[index %% 26 + 1]] <- english.letters[index] } > apply.cipher.to.string <- function(string, cipher) { output <- '' for (i in 1:nchar(string)) { output <- paste(output, cipher[substr(string, i, i)], sep = '') } return(output) } # 文字列をシーザー暗号で暗号化する > apply.cipher.to.text <- function(text, cipher) { output <- c() for (string in text) { output <- c(output, apply.cipher.to.string(string, cipher)) } return(output) }
動作確認。
> apply.cipher.to.text(c('sample', 'text'), caesar.cipher) [1] "tbnqmf" "ufyu"
暗号化する関数ができたので、解読に移ります。 問題を、以下の3つのステップに分割して、考えていきます。
1. 復号結果を評価する目的関数を定義する
今回は、暗号前のテキストは意味のある英文であることを前提としています。このため、「英文らしさ」を評価する関数を作り、目的関数とします。
具体的には、単語とその出現確率を保持する語彙データベースを作成し、復号化したテキストに含まれる単語の確率を計算、それらを掛け合わせて、テキストの「英文らしさ」とします。
まずは、語彙データベースを読み込み。/use/share/dic/wordsに含まれる単語のウィキペディアでの出現頻度を集計したデータベースです。
> load(file.path('data', 'lexical_database.Rdata'))
テキストの「英文らしさ」を判定する関数を定義。
# 単語の確率を取得する > one.gram.probability <- function(one.gram, lexical.database = list()) { lexical.probability <- lexical.database[[one.gram]] if (is.null(lexical.probability) || is.na(lexical.probability)) { return(.Machine$double.eps) # データベースに存在しない場合、非常に少ない確率を返す。 } else { return(lexical.probability) } } # テキストを復号して、その英文らしさを返す > log.probability.of.text <- function(text, cipher, lexical.database = list()) { log.probability <- 0.0 for (string in text) { decrypted.string <- apply.cipher.to.string(string, cipher) log.probability <- log.probability + log(one.gram.probability(decrypted.string, lexical.database)) # 浮動小数点の演算精度は有限なので、単純に掛け合わせると結果が不安定になってしまう。 # これを防ぐため、確率の対数を取り、それを足し合わせる。 } return(log.probability) }
2. 新しい復号表候補を生成するアルゴリズムを定義する
新しい復号表は、現在の復号表の一部を、ランダムに1箇所だけ変化させて作るようにします。
# ランダムな復号表(cipher)を生成する > generate.random.cipher <- function() { cipher <- list() inputs <- english.letters outputs <- english.letters[sample(1:length(english.letters), length(english.letters))] for (index in 1:length(english.letters)) { cipher[[inputs[index]]] <- outputs[index] } return(cipher) } # 復号表(cipher)中のinputに対応する文字を、outputに変更する > modify.cipher <- function(cipher, input, output) { new.cipher <- cipher new.cipher[[input]] <- output old.output <- cipher[[input]] collateral.input <- names(which(sapply( names(cipher), function (key) {cipher[[key]]}) == output)) new.cipher[[collateral.input]] <- old.output return(new.cipher) } # 復号表(cipher)の一部を変更した新しい復号表を生成する。 > propose.modified.cipher <- function(cipher) { input <- sample(names(cipher), 1) output <- sample(english.letters, 1) return(modify.cipher(cipher, input, output)) }
3. よりよい復号表に近づくためのアルゴリズムを定義する
単純に考えると、出力結果を1の関数で評価して、高い方を使えば良いように思えます。 しかし、今回のような状況では、この方法(貪欲法と呼ばれます)だと、あまりよくないルールで行き詰ってしまいやすいらしい。
このため、以下のようなルールを使います。
- 1) 復号表A,Bがあるとき、Aの確率 < Bの確率であれば、AをBで置き換える。
- 2) Aの確率 > Bの確率 であれば、時々、AをBで置き換える。
- 具体的には、「Bの確率/Aの確率」で、AをBで置き換えます。
# メトロポリタン法の1ステップを実行する > metropolis.step <- function(text, cipher, lexical.database = list()) { # 新しい復号表を生成 proposed.cipher <- propose.modified.cipher(cipher) # 復号表Aの確率 lp1 <- log.probability.of.text(text, cipher, lexical.database) # 復号表Bの確率 lp2 <- log.probability.of.text(text, proposed.cipher, lexical.database) if (lp2 > lp1) { # Aの確率 < Bの確率の場合、Bの復号表を使う return(proposed.cipher) } else { # Aの確率 > Bの確率の場合、「Bの確率/Aの確率」で、Bの復号表を使う a <- exp(lp2 - lp1) x <- runif(1) if (x < a) { return(proposed.cipher) } else { return(cipher) } } }
解読を行う
部品がそろったので、実際に解読を行ってみます。
まずは、暗号化文字列を作成。
> decrypted.text <- c('here', 'is', 'some', 'sample', 'text') > encrypted.text <- apply.cipher.to.text(decrypted.text, caesar.cipher) > print(encrypted.text) [1] "ifsf" "jt" "tpnf" "tbnqmf" "ufyu"
解読を実行。
> set.seed(1) # ランダムな復号表を作成 > cipher <- generate.random.cipher() > results <- data.frame() # 50000回改善ステップを実行する > number.of.iterations <- 50000 > for (iteration in 1:number.of.iterations) { # 復号表の評価値を計算 log.probability <- log.probability.of.text( encrypted.text, cipher, lexical.database) # 現在の表での復号結果 current.decrypted.text <- paste(apply.cipher.to.text(encrypted.text,cipher), collapse = ' ') correct.text <- as.numeric(current.decrypted.text == paste(decrypted.text,collapse = ' ')) # 結果をデータフレームに追加 results <- rbind(results, data.frame(Iteration = iteration, LogProbability = log.probability, CurrentDecryptedText = current.decrypted.text, CorrectText = correct.text)) # メトロポリタン法のステップを実行 cipher <- metropolis.step(encrypted.text, cipher, lexical.database) } # 時間がかかるので待つ...
結果を確認。
> subset(results, Iteration == 1 | Iteration %% 5000 == 0 ) Iteration LogProbability CurrentDecryptedText CorrectText 1 1 -180.21827 lsps bk kfvs kjvhys zsrz 0 5000 5000 -67.60777 gene is same sfmpwe text 0 10000 10000 -67.60777 gene is same spmzoe text 0 15000 15000 -66.77997 gene is some scmhbe text 0 20000 20000 -70.81143 dene as some scmire text 0 25000 25000 -39.85902 gene as some simple text 0 30000 30000 -39.85902 gene as some simple text 0 35000 35000 -39.85902 gene as some simple text 0 40000 40000 -35.78443 were as some simple text 0 45000 45000 -37.01289 were is some sample text 0 50000 50000 -35.78443 were as some simple text 0
ステップを重ねるごとに、正解に近づいています。が、よく見ると、40000ステップ目の結果の方が、45000ステップ目より評価結果が高い・・。今回使用した目的関数では「英文らしさ」を確率的に評価しているだけなので、正解にたどり着いても、次のステップに進んでしまい、このような結果になります。
最後に、メトロポリス法の問題点をまとめておきます。
