2014-07-28

CodeIQ 出題者デビューしました。

CodeIQ Ruby Python

このたび、CodeIQ の出題者としてデビューしました。
問題は取り敢えず2問：

「取り敢えず」というのは。
問題タイトルを見ていただければお分かりの通り、今回の出題は「レベル1」の問題。
まだこのあとに Lv.2 とかそれ以降のレベルの問題が控えている、というわけです(^-^)

問題は、知識問題と言うよりは、実用問題。
最近多い選択肢を選択するだけの問題ではなく、ちゃんと自分でプログラムを書く問題です。
Lv.1 は入門編。「yield」というキーワードを使ったことがなくても問題を見れば使い方が分かるし、自分で書いてみることで練習にもなる、非常に取っつきやすい問題になっています（と思います(^-^)）。
そして Lv.2 で応用問題、さらにそれ以降…とすすんでいくに従って、どんどん使い方が身についていくo(^▽^)o
（ような構成にしたつもりです）

たくさんのご解答、お待ちしておりますm(_ _)m

2014-03-21

Ruby でメモ化カッコカリ（ #rubytokai 発表メモ）

Ruby メモ化

昨日の Ruby東海第32回勉強会で、メモ化の発表をしてきました。

資料を作る暇（と体力）がなかったのですが、とりあえず発表内容をまとめておきます。

2014-01-08

enumerable_lz 0.1.5 公開しました。

Ruby

なんか今更感ハンパないですけれど。
約 3 年ぶりに、自作の gem の新バージョンを公開しました。
もう誰も使ってないかもしれないにもかかわらずｗ

enumelable_lz 0.1.5

enumerable_lz (0.1.5): http://t.co/3a62B1Bt8c Add Enumerable#filter, Enumerable#transform and some equivalent methods on En…
— RubyGems (@rubygems) January 8, 2014

簡単に言うと、Enumerable に遅延リストを返すフィルタリングメソッド Enumerable#filter と変換メソッド Enumerable#transform を追加する gem です。
Ruby 2.0.0 で導入された Enumerable#lazy と同じような機能を提供します。
でも Enumerable#lazy の挙動がどうしてもなじめなくて、メンテナンスリリースの意味も込めてアップデートしちゃいました。

【2014/04/23 23:33 追記あり】

2013-09-22

続・文字と数値リテラルを使わない Hello World 考 (in Ruby)

Ruby

先日の続き。

解答集サイトを見ていて、他にもこういう解き方があるな、と色々発見があったので、引き続き Ruby で、先日のとは全く違う方向性の別解をまたいくつか。

2013-09-19

文字と数値リテラルを使わない Hello World 考 (in Ruby)

Ruby

CodeIQ の大人気問題「Restricted Words」が、ついに解答締切となりました。

この問題は「数値・文字・文字列リテラルを使用せずに、"Hello World" と出力する」というもの。
解答締切と共に、出題者から解答集が公開されました。

解答集を公開します https://t.co/fd418ZJrAp：挑戦者求む！Restricted Words by @cielavenir http://t.co/6uourFB4uJ @codeiqさんから
— しえる (@cielavenir) 2013, 9月 19

色々な言語の解答が載っていて、見ているだけで楽しいですね(^-^)

さて、でもここにのっている解答は、基本、以下のパターンです。

キーワードや配列リテラルを利用して、そのサイズ（や length 等）から数値を生成する。
数値から文字を生成する。

でも最低条件は、「数値・文字・文字列リテラルを使用しないこと」。
この基本パターン以外の解答も探せばいくらでも見つかります*1。
ということで、私の提出した解答例と共に、それ以外のものも含めた Ruby での「別解」を探ってみたいと思います。

*1:実際、解答集サイトには、Perl の barewaord を利用した例、Ruby の class オブジェクトからクラス名を取得できることを利用した例、C の関数名を文字列で取得できることを利用した例、などが挙げられています。

2012-08-13

ナイーブベイズフィルターの実装と考察

機械学習 Ruby MeCab 勉強

やっぱ実家はいろいろ捗る。洗濯とか料理とか自分では何もやらなくていいから。
というわけで、前回の勉強の続き、予告通りナイーブベイズフィルターを実装してみました。

実装

と言っても、実装に関しては手抜きです。
gihyo.jpの連載機械学習はじめようの、第3回「ベイジアンフィルタを実装してみよう」のサンプルコードをほぼそのまま流用しました。
ただし。以下のような手を加えています。

せっかくなので別言語(=Ruby)に翻訳することで、一応自分でコードを写経して覚えるという行動を取る。
せっかくなので先日インストールした MeCab を利用するようにコードを修正する。

どちらもすんなりうまくいったのですが、後者でちょっと躓きました。それは追々触れていきます。

まずは翻訳（写経）*1。

あ、もちろん morphological.rb の動作には MeCab と MeCab Ruby のインストールが前提です。

さて、これをそのまま動かしてみたのですが…。

$ ruby naivebayes.rb
ヴァンロッサム氏によって開発されました. => 推定カテゴリ: Ruby
豊富なドキュメントや豊富なライブラリがあります. => 推定カテゴリ: Python
純粋なオブジェクト指向言語です. => 推定カテゴリ: Ruby
Rubyはまつもとゆきひろ氏(通称Matz)により開発されました. => 推定カテゴリ: Ruby
「機械学習 はじめよう」が始まりました. => 推定カテゴリ: 機械学習
検索エンジンや画像認識に利用されています. => 推定カテゴリ: 機械学習

最初の文章が、期待通り「Python」に分類されず「Ruby」と分類されてしまっています。
他の「『機械学習はじめよう』のサンプルを試してみた」サイトをいくつか見てみても、きちんと Python と分類されているところしか見付からないのに、なぜだろう。ロジックは間違っていないし。
ということで、色々見てみました。

MeCab の形態素解析の精度、あるいは、クセ？

色々調べた結果、以下のことが分かりました。

まず、Python→Ruby に翻訳したコードには問題なし（ロジック的に）。
主な原因は全て、MeCab 側にある、と。
その問題点は、いくつか出てきたのですが大きなのは以下の2つ。

人名「グイド・ヴァンロッサム」が、この塊で一般名詞として認識されている。
- 特に「ヴァンロッサム」が単語として認識されていないのでカウントに引っかからない。
日本語的には助動詞の「れ(る)」「られ(る)」が、動詞（接尾）として認識されている。
- 動詞は検索対象なので、これが含まれる量がカテゴリ推定に大きく左右されてしまっている。

つまり簡単に言うと、

「ヴァンロッサム」という単語が出てきたがこれは学習データに存在しない → 推定材料にならない。
「開発された」の「れ（動詞）」が、Ruby カテゴリの学習データに一番多く存在している → 推定材料。

ということで結果として Ruby に推定分類されてしまった、というわけ。

MeCab 側の解決方法模索

まず、MeCab の解析精度にも問題があることは確かです。
考えてみれば先日インストールしてから全然触ってないですし、辞書も mecab-ipadic をデフォルトのままいじってないですから。
あと morphological.rb での品詞分類も MeCab デフォルトの品詞分類に基づいたモノになっています。

このあたりの、設定を弄るなり、学習データを用意して学習させるなり、mecab-dic-overdrive等のツールを使って辞書へのパッチ適用・ノーマライズ、ユーザ辞書の拡充、などを行っていくべきでしょう。行く行くは。

ま、それはそれとして、課題として残しておいて、今回は別のアプローチを考えます。

学習

MeCab にも「学習課題」が出てきたわけですが、そっちのせいにしないで、自分自身にもっと何かできることを探す、というのがやっぱ筋でしょうね。
じゃ、今回実装したフィルターに、「学習」させれば良い。
そもそも現在の学習データが各カテゴリ1件ずつというのは少なすぎますからね。
連載記事の最後の方にもきちんと書いてあります。

訓練データが増えることによって，より正確な分類ができるようになるので興味のある方はご自身で試してみてください

ということで、訓練データを追加してみましょう。
というか、naivebayes.rb には追加訓練データがコメントアウトしてあります。

  #nb.train("ヴァンロッサム氏によって開発されました。", "Python")

そう、正しく分類されなかったら、その正しい分類先を教えてやる。これが機械学習の「学習」の基本。

ということでこのコメントアウトを外して実行してみました。

$ ruby naivebayes.rb
ヴァンロッサム氏によって開発されました. => 推定カテゴリ: Python
豊富なドキュメントや豊富なライブラリがあります. => 推定カテゴリ: Python
純粋なオブジェクト指向言語です. => 推定カテゴリ: Ruby
Rubyはまつもとゆきひろ氏(通称Matz)により開発されました. => 推定カテゴリ: Ruby
「機械学習 はじめよう」が始まりました. => 推定カテゴリ: 機械学習
検索エンジンや画像認識に利用されています. => 推定カテゴリ: 機械学習

無事、同文章が Python に分類されました(^-^)

でも、これで「めでたしめでたし」じゃないんですけどね。「れ(る)」「られ(る)」問題はまだ残ってます。
例えば「必要に迫られて開発された発明品。」という文章*2を分類してみると、この時点での結果は「Python」となります。
同じ文章を、先ほどコメントアウトを外した追加訓練データをもう一度コメントアウトして実行すると、今度は「Ruby」になります。

ここまで来ると、やっぱり MeCab 側の調整か、プログラム側の調整が必要になってくるでしょうね。
元々連載記事の方にも、推定フェーズの出現頻度のところで「ゼロ頻度問題」の解決策とその精度問題のことが取り上げられています。今回は同連載のコードをそのまま翻訳したので、決して精度の高くない「加算スムージング」という補正方法を用いています。これをもっと精度の良いモノに置き換えることで解決する問題とかもきっと出てくるでしょう。

まとめ

勉強と言っても今回はほぼ写経で終わりましたが、これで大体「どういうことをすれば単純分類器が作れるか」ということは掴めたと思います。
もっと実用的な or 個人的ニーズのある文例の分類を試しながら、色々調整していこうと思います。

次回

次…どうしよう。
連載機械学習はじめようの流れに沿って、次の記事、理論編の分布の話を掘り下げてみるか。
それとも、ここでもうちょっと統計よりに方向転換を図るか…。

*1:gist に上げてありますので、ご自由に Fork してご使用ください。もっとこうしたら良いよとかあればそれも大歓迎。

*2:この例文には意味はありません。主に「れ(る)」「られ(る)」によって分類先の推定が左右されることを見るためだけの例文です。

2012-08-11

フィボナッチ数(2) ver.末尾再帰

フィボナッチ数 Ruby 整数

暑中残暑お見舞い申し上げます。
この記事書き始めた頃は暑中だったのに色々あって立秋過ぎちゃった。

さておき、前回予告した、「フィボナッチ数を求めるための末尾再帰」について。

おさらい …フィボナッチ数

詳細は、前回の記事とか、適当にググってみたりとかしてください。

簡単に言うと、

$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}(n\geq2)$

で定義される数列で、例えば

def fib n
  return n.even? ? -fib(-n) : fib(-n) if n < 0  # for negative n
  a, b = 0, 1
  n.times { a = b + b = a }
  a
end

こんな関数（メソッド）を書くと一般の n 番目のフィボナッチ数を求められます。
ちなみに最初の方を列挙すると以下の通り。

(0, )1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

末尾再帰について少しだけ

一般に関数の「再帰呼び出し」というのは、関数の実装の中で自分自身を呼び出す手法のこと。
「末尾再帰」というのは、その再帰呼び出しを関数の最後のステップで（のみ）行う手法のこと。

例えば、再帰呼び出しを利用した階乗の定義を考えると分かりやすいですね。
↓

def factorial n
  return 1 if n < 2
  n * factorial(n-1)
end

最後に自分自身を呼び出しています。逆にそれ以外の部分では余分な再帰呼び出しは行っていません。
これも末尾再帰と考えることも出来ますが、さらに推し進めて「最後の行は本当に再帰呼び出ししか行わない」ようにしてみましょう。この場合↓こうなります。

def factorial n, r=1
  return r if n < 2
  r *= n
  n -= 1
  factorial n, r
end

本当に最後の行が、元の関数の定義式とほぼ同じになるように、少し冗長に書きました。とにかく最後の行は、パラメータを少し変えて自分自身を再帰呼び出ししている、ただそれだけのことをしているのが分かると思います。
これが厳密な「末尾再帰」のカタチ。

この形になっていると、再帰呼び出しをジャンプに変換することで実行効率を上げる、所謂「末尾最適化」が可能になる*1、という特徴もあるのですが、今回はその話はパス。本題はそっちじゃないので。

フィボナッチ数を末尾再帰で(1) O(n) バージョン

まず前回考えた「関数指向の例」を考えてみましょう。
コードを再掲します。

def fib n
  return n.even? ? -fib(-n) : fib(-n) if n < 0  # for negative n
  return n if n < 2
  fib(n - 2) + fib(n - 1)
end

この例も、再帰呼び出しになっています。しかし最後のステップは、自分自身を2回呼び出しています。
これは末尾再帰のカタチではありません。

これをなんとか末尾再帰のカタチに持って行きたいと思います。どうすれば良いでしょう？

ここで、前節の階乗の例で、2つの実装がどう違っていたのかを思い出してみましょう。

最初の例の最後のステップは、詳しく見るとこうなっています。

再帰呼出しで、nが一つ少ない場合の階乗を実際に計算している。
それを計算した上で、階乗の定義に合わせて今回のnの場合の答えを算出している。

この仕組み、先ほどのフィボナッチ数の関数と同じ構造になっていますよね。

再帰呼出しで、nが1少ない場合と2少ない場合のフィボナッチ数を実際に計算している。
それを計算した上で、フィボナッチ数の定義に合わせて今回のnの場合の答えを算出している。

それに対して、階乗の2つめの例は、最後のステップがこんな構造になっています。

最後のステップに行く前に、カウンタとなる変数と、実際の値を計算するパラメータを変更している。
新しいパラメータで再帰呼出している。

この「実際の値を計算するパラメータ」が重要で、階乗の例の場合、実際に階乗をステップごとに計算しています。
ただし、先の例は「1に、1〜nをこの順に掛けている」形になっているのに対して、後の例は「1に、n〜1をこの順に掛けている」形になっています。
でもこれは大きな問題ではありません。この場合、結果はどちらも同じになりますから。

それを踏まえて。
フィボナッチ数の場合は、どうすれば良いのかというと。
まず、カウンタ以外のパラメータは少なくとも2つ必要です。なぜなら、フィボナッチ数の定義に則った計算を行う以上、少なくとも2つのフィボナッチ数からしか算出できない構造になっているのですから。
そして、その2つの値を使って計算して、その結果をまたパラメータとして次の再帰呼出に与える、ということを繰り返していくことを考えればOK、というわけです。

その2つをこのようにすれば、実はうまくいきます。

def fib n, a=0, b=1
  return n.even? ? -fib(-n) : fib(-n) if n < 0  # for negative n
  return a if n < 1
  #return b if n < 2
  fib n-1, b, a+b
end

つまり。
最初はa=0(=F₀),b=1(=F₁)とし、再帰呼出のたびに、aにb、bにa+bを代入することでF_n-2とF_n-1をF_n-1とF_nに変換している、というわけ。
これを所定の回数繰り返せば、aにF_nの計算結果が入っているはずだから、それを返して終わり。

もちろんすぐに分かるように、この関数の場合の計算量は O(n) です。単純にn回繰り返しているだけですからね。

改良(?)バージョン

少し考えると、この方がもっと効率よいんじゃないか？という以下の実装も思いつきます。

def fib n, a=0, b=1
  return n.even? ? -fib(-n) : fib(-n) if n < 0  # for negative n
  return a if n < 1
  return b if n < 2
  fib n-2, a+b, a+b+b
end

つまり1回の再帰呼出で、カウンタを1ずつ減らす代わりに2ずつ減らして、与えるパラメータも「F_n-2とF_n-1をF_nとF_n+1に変換」する、というわけ。
計算量はやはり O(n) ですが、実際は、というと。

実は実行速度の面ではむしろ遅くなります。1回繰り返すときに、先の例では足し算1回だけだったのに対して、今回は1回繰り返すとき（先の2回分に相当）に足し算3回。つまり1.5倍になってしまうからです。
ただし再帰呼出の回数は減るので、関数呼び出しのオーバーヘッドとか、スタックオーバーフローの問題は軽減できます。ただこの話も今回の本題ではないので言葉だけ。

フィボナッチ数を末尾再帰で(2) O(logn) バージョン

次は、倍数公式をうまく活用して計算量が O(logn) になるようにできないか考えてみましょう。
「倍数公式」とは、以下のようなモノでした。

$F_{2n}=(2F_{n-1}+F_n)F_n\\F_{2n+1}=F_n^2+F_{n+1}^2$

実はこれをもっと一般化した、以下のような「和の公式」が存在します。

$F_{n+m}=F_nF_m+F_{n-1}F_m+F_nF_{m-1}\\F_{n+m-1}=F_nF_m+F_{n-1}F_{m-1}$

これを利用するとさらにこんな風に書けます：

$F_{2^k+m}=F_{2^k}F_m+F_{2^k-1}F_m+F_{2^k}F_{m-1}$

ここで0≦m＜2^kと考えれば、nを2進数表記して、それを利用してまずF_nをF_2^kとF_m（およびその周辺のフィボナッチ数）で表して、F_mをまた同様に分解して…という繰り返しで計算していくことが出来そうです。

実際にやってみたのが、こんな例になります：

def fib n
  return n.even? ? -fib(-n) : fib(-n) if n < 0
  fibFastIter = lambda do |a, b, p, q, c|
    return a if c < 1
    if c.even?
      a1, b1, p1, q1, c1 = a, b, p**2 + q**2, (2*p+q)*q, c.div(2)
    else
      a1, b1, p1, q1, c1 = a*p + b*q, a*q + b*q + b*p, p, q, c-1
    end
    fibFastIter[a1, b1, p1, q1, c1]
  end
  fibFastIter[0, 1, 0, 1, n]
end

ちょっと先ほどまでと書き方が変わってますが、自分自身を再帰関数としていたか、別の再帰関数を（ラムダ式で）用意したかの違いだけなのであまり気にしないでください。
p, q の方が、倍数公式を利用した、F_2^kを表すフィボナッチ数となっており、
a, b の方が、和の公式を利用した、F_2^k+mを表すフィボナッチ数となっています。
で、繰り返していって最後に、aに求めるフィボナッチ数が入っている、という仕組み。

これ、結構速いです。前回の記事の『メモ化＋倍数公式』に肉薄するくらい。どちらも O(logn) ですしね。
ベンチマークを取ってみました。

                      user     system      total        real
fib(50)x1000      0.010000   0.000000   0.010000 (  0.008081)
fib(100)x1000     0.010000   0.000000   0.010000 (  0.010353)
fib(500)x1000     0.020000   0.000000   0.020000 (  0.025588)
fib(1000)x1000    0.040000   0.000000   0.040000 (  0.033170)
fib(5000)x1000    0.080000   0.000000   0.080000 (  0.082407)
fib(10000)x1000   0.190000   0.000000   0.190000 (  0.192046)

与える n が十分に小さいときは、メモ化＋倍数公式の時よりも速くなっているのが分かります。
でも n=5000 の時に同じ数値となり、n=10000 のときは、逆に少し時間かかってますね。
それは、この方式にまだ少し無駄があるから。

改良(!)バージョン

実は先のコードは、ググって見付けたHaskelか何かの関数型言語の実装例をRubyに翻訳したモノです。
でも、明らかな無駄があるの、分かりますよね？
カウンタ変数 c を、どんどん2で割れば良いのに、奇数の時は1引いて再帰呼び出しして、偶数の時に2で割っています。これをまとめちゃえば、効率よくなるはず。
ということでまとめちゃいました。

def fib n
  return n.even? ? -fib(-n) : fib(-n) if n < 0
  return 0 if n < 1
  fibFastIter = lambda do |a, b, p, q, c|
    return a*p + b*q if c < 2
    a, b = a*p + b*q, a*q + b*q + b*p if c.odd?
    fibFastIter[a, b, p**2 + q**2, (2*p+q)*q, c.div(2)]
  end
  fibFastIter[0, 1, 0, 1, n]
end

ベンチマーク。

                      user     system      total        real
fib(50)x1000      0.000000   0.000000   0.000000 (  0.005049)
fib(100)x1000     0.010000   0.000000   0.010000 (  0.006286)
fib(500)x1000     0.020000   0.000000   0.020000 (  0.016950)
fib(1000)x1000    0.030000   0.000000   0.030000 (  0.029278)
fib(5000)x1000    0.060000   0.000000   0.060000 (  0.062313)
fib(10000)x1000   0.130000   0.000000   0.130000 (  0.132980)

うん。やっぱり先のモノより速くなりました(^_^) n=10000 の時も『メモ化＋倍数公式』の時と同じ数値を出しています。
ていうか、これ以上大きな n のことを考えると、やっぱりメモ化を利用した場合の方が速くなる傾向にあるってことですよね、これ。
メモ化利用の方が再帰呼出の回数は多いけれど、演算（足し算や掛け算）の総回数は下回っていくから、なんでしょうね。

*1:実際には厳密バージョンではなくても末尾最適化は適用可能です。

名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

CodeIQ 出題者デビューしました。

Ruby でメモ化カッコカリ（ #rubytokai 発表メモ）

enumerable_lz 0.1.5 公開しました。

enumelable_lz 0.1.5

続・文字と数値リテラルを使わない Hello World 考 (in Ruby)

文字と数値リテラルを使わない Hello World 考 (in Ruby)

ナイーブベイズフィルターの実装と考察

実装

MeCab の形態素解析の精度、あるいは、クセ？

MeCab 側の解決方法模索

学習

まとめ

次回

フィボナッチ数(2) ver.末尾再帰

おさらい …フィボナッチ数

末尾再帰について少しだけ

フィボナッチ数を末尾再帰で(1) O(n) バージョン

改良(?)バージョン

フィボナッチ数を末尾再帰で(2) O(logn) バージョン

改良(!)バージョン