seri::diary

日常

自分が2016年に作ったrails拡張系gemとその解説

この記事はトレタ Advent Calendar 2016の4日目です。
3日目は弊社CTOのmasuidriveによる【定番】 新しいWebサービスを開発・運営するときに使いたいサービス 【2016年末版】でした。私の推しサービスはBugsnagです。詳細はこちらのスライドを参照ください。

さて、3日目のこの記事では、私が今年railsの実装についての調査と暇つぶしを兼ねて作ったrails拡張系gemについて紹介します。

flatten_routes

github.com

routes.rb を書くときにresouceresourcesを使った書き方をしているとroutes.rbだけでは実際のURLがパッと見でわかりにくくなることがある。

$ rake routes を使えばよいのだが、routes.rb が膨大になってくると表示まで3~4秒待たされることもあり、プロジェクトが佳境を迎え、1秒でも惜しい状況では結構なストレスになる。

そこで、routes.rbを書くときのもう一つの記法である verb {directory} => {controller}/{action} の書き方もコメントで併記できたらよさそうと考えてこのgemを作った。

実行例は以下の通りである。 仮にroutes.rbが以下の通りだったとすると

Rails.application.routes.draw do
  ActiveAdmin.routes(self)
  resources :todos, except: [:new, :edit] do
    member do
      post :start
      post :finish
      post :restart
      post :giveup
      put :awesome
    end
    collection do
      get :finished
      get :not_yet
    end
  end
end

Rails.rootで以下のコマンドを実行することで

$ rake flatten_routes:annotate

こうなる

Rails.application.routes.draw do
# == generated by flatten_routes from here 2016-02-27 17:56:31 +0900
#  get    '/admin'                    => 'admin/dashboard#index'
#  get    '/admin/dashboard'          => 'admin/dashboard#index'
#  post   '/admin/todos/batch_action' => 'admin/todos#batch_action'
#  get    '/admin/todos'              => 'admin/todos#index'
#  post   '/admin/todos'              => 'admin/todos#create'
#  get    '/admin/todos/new'          => 'admin/todos#new'
#  get    '/admin/todos/:id/edit'     => 'admin/todos#edit'
#  get    '/admin/todos/:id'          => 'admin/todos#show'
#  patch  '/admin/todos/:id'          => 'admin/todos#update'
#  put    '/admin/todos/:id'          => 'admin/todos#update'
#  delete '/admin/todos/:id'          => 'admin/todos#destroy'
#  get    '/admin/comments'           => 'admin/comments#index'
#  post   '/admin/comments'           => 'admin/comments#create'
#  get    '/admin/comments/:id'       => 'admin/comments#show'
#  delete '/admin/comments/:id'       => 'admin/comments#destroy'
#  post   '/todos/:id/start'          => 'todos#start'
#  post   '/todos/:id/finish'         => 'todos#finish'
#  post   '/todos/:id/restart'        => 'todos#restart'
#  post   '/todos/:id/giveup'         => 'todos#giveup'
#  put    '/todos/:id/awesome'        => 'todos#awesome'
#  get    '/todos/finished'           => 'todos#finished'
#  get    '/todos/not_yet'            => 'todos#not_yet'
#  get    '/todos'                    => 'todos#index'
#  post   '/todos'                    => 'todos#create'
#  get    '/todos/:id'                => 'todos#show'
#  patch  '/todos/:id'                => 'todos#update'
#  put    '/todos/:id'                => 'todos#update'
#  delete '/todos/:id'                => 'todos#destroy'
# == generated by flatten_routes to here
  ActiveAdmin.routes(self)
  resources :todos, except: [:new, :edit] do
    member do
      post :start
      post :finish
      post :restart
      post :giveup
      put :awesome
    end
    collection do
      get :finished
      get :not_yet
    end
  end
end

コメントするだけでなく、いっそのことresorucesresourceを使う記法をすべてconvertしたい、という時には

$ rake flatten_routes:convert

を実行することで、上記の例でコメントされていた部分が記述され、オリジナルのresourcesresouceを使っていた方がコメントアウトされる。

railsからrouting情報を取り出す方法について

$ rake routeがそれっぽい情報を表示してくれているのでその辺のソースを参考に調べた。(このgemを書いた当時はrails5が出る前だったので4-2-stableブランチを参照した)

rails4.2におけるrake routesタスクは以下の様に実装されている

desc 'Print out all defined routes in match order, with names. Target specific controller with CONTROLLER=x.'
task routes: :environment do
  all_routes = Rails.application.routes.routes
  require 'action_dispatch/routing/inspector'
  inspector = ActionDispatch::Routing::RoutesInspector.new(all_routes)
  puts inspector.format(ActionDispatch::Routing::ConsoleFormatter.new, ENV['CONTROLLER'])
end

Rails.application.routes.routesでrouting情報の構造を取得し、それを ActionDispatch::Routing::RoutesInspectorに渡して、 ActionDispatch::Routing::ConsoleFormatter で定義されたformat(定義箇所はここ)で整形されたものをputsしているということがわかる。ちなみに、ActionDispatch::Routing::RoutesInspectorActionController::RoutingErrorがraiseされたときに出るエラーページのルーティング一覧を表示する部分でも使われており、htmlのtableに整形するためのformatterも実装されている

なので、今回はオリジナルのformatterを作ってそれをinspectorに渡すように実装すればいいかなと思ったが、別にformatterを差し替えて使いまわすような使い方を提供するgemでもないので、ベタっとformatterを書いて実装した。中身はroutes.rbのフォーマットに合わせて置換したり見た目を揃えるためにスペース入れたりとかそういう当たり前のことしかしていないので割愛。

補足

単に実際のURLをコメントするだけなら他のgemとしてはannotateというgemがある。
自分はプライベートでも仕事でもよく使っており、ActiveRecordのModelにコメントでschema情報を付けるだけのgemかと思っていたのだが、READMEをよく読んだらrouting情報もコメントしてくれる機能があったらしい。じゃあこれ使えばいいか

error_arranger

github.com

Controller内部でエラーが起きて、rescue_fromに渡されたりそのままraiseされてrack layerで処理される前に何か前処理を入れたりできないかなぁと思って作ったgem。

例えば

class PostsController < ActionController
end

みたいなcontrollerがあったとして、PostsController内部で発生したエラーメッセージに何か注釈をつけたりしたい、みたいなケースがあったら(あるのか?)以下のようにarrange_exception!を実装することで実現できる。

class PostsController < ApplicationController

  private

  def arrange_exception!(exception)
    exception.message << 'This error raised in PostsController'
  end
end

エラーがrailsで処理される前にcallbackを差し込む仕組みについて

結論から言えばモンキーパッチを当てているので、あまり行儀が良い方法ではない。

で、モンキーパッチの内容は下記である。

module ActionController
  module Rescue
    extend ActiveSupport::Concern
    include ActiveSupport::Rescuable

    private
      def process_action(*args)
        super
      rescue Exception => exception
        request.env['action_dispatch.show_detailed_exceptions'] ||= show_detailed_exceptions?
        arrange_exception!(exception) if self.respond_to?(:arrange_exception!)
        rescue_with_handler(exception) || raise(exception)
      end
  end
end

単にcontrollerにarrange_exception!という名前のメソッドが生えていたらそれを呼んでからrescue_fromで定義されたhandlerに渡すかそのままraiseする、という感じである。

このgemを作った当時、Controllerのactionで発生したエラーがどこでhandlingされるか分からなくて散々railsのソースを読んでようやく見つけた記憶があるのだが、rails/actionpack/lib/action_controller/metal/rescue.rbに実装されている。

ソースをちゃんと読み切れていないのだが、どうもrails/actionpack/lib/action_controller/metal配下に実装されているモジュールがロードされて、そのモジュールの中でprocess_actionというメソッドをoverrideしていってstackされていき、実際にリクエストが来てactionが実行されるときにcallbackとしてcontrollerからprocess_actionが呼ばれる。。という感じのように見えるのだが、よくわかっていない。謎い。

practical_errors

github.com

先に説明したerror_arrangerを使って、railsでよく見るエラーにもう少し丁寧な解説をつけてみたらrails初心者に優しくなるんじゃなかろうか?と思って作ってみたgem。

例えば、Post.find(1000)を実行してActiveRecord::RecordNotFoundがraiseされたとする。

そのときには以下のようなメッセージをerrorオブジェクトに追加してくれる。

ActiveRecord::RecordNotFound (
========== Practical Errors appends message from here ==========

Rails says, "Couldn't find Post with 'id'=1000".

You might have called ActiveRecord::FinderMethods#find, but the record for provided id was not found.
If you DO NOT want to raise ActiveRecord::RecordNotFound even if the record was not found,
you should use ActiveRecord::FinderMethods#find_by instead.

Post.find(1000) # raise ActiveRecord::RecordNotFound
Post.find_by(id: 1000) # just returns nill


========== Practical Errors appends message to here ==========
See more detail about Practical Errors: https://github.com/serihiro/practical_errors

)

idで検索してnilになるケースが想定される場合はfind_by使ってね、的なrails初心者のコードをレビューする時につけるようなコメントをrailsに勝手にやってもらえる。もちろん、ちゃんとエラーメッセージを読む相手であるということが前提だ。読まない相手の場合は頑張って教育しよう。

ちなみに、ActiveRecord::RecordNotUniqueのときの追加メッセージはこうだ。

The column included in the record that you were about to insert or update, is not allowed duplicated value.
This error was detected by database, not Rails.
You might have configured uniqueness validation to this column, but uniqueness validation is not panacea.
In race condition, uniqueness validation was passed easily.
For more detail, see rails document
http://api.rubyonrails.org/classes/ActiveRecord/Validations/ClassMethods.html#method-i-validates_uniqueness_of

uniqueness: trueなvalidationを入れてもrace conditionではすり抜けるから気をつけような、的な。あまり役には立たないがActiveRecord::RecordNotUniqueがrescueされずに突き抜けてしまった時の慰めにはなるだろう。

ちなみにいまのところ対応しているエラーはActiveRecord::RecordNotFoudActiveRecord::RecordNotUniqueの2種類しかない。他にも色々作る予定だったが力尽きてしまったので、ぜひPRを送って熱いエラーメッセージを追加してもらえるとうれしい。

実装部分については特筆すべき事項はなく、前出のerror_arrangerを使ってraiseされたエラーのクラスを見てそのクラスに該当するAdviserクラスがあったらAdviserクラスにメッセージを付与してもらう、ぐらいの感じである。

      if PracticalErrors::ErrorAdvisers::const_defined?(exception.class.to_s)
        @customised_message << PracticalErrors::ErrorAdvisers::const_get(exception.class.to_s).advise(exception)
      else
        @customised_message << <<-"EOS".strip_heredoc
          hmm... I don't know this error :(
          Tell me => https://github.com/serihiro/practical_errors
        EOS
      end

Adviserがいない時は教えてくれ!っていうメセージを入れているが今の所一件も報告がないので誰も使ってないと思われる。PRお待ちしております。


トレタ Advent Calendar 2016の5日目は2回目の登場horimislimeによる「ここ最近作ってたMacアプリの話とか」の予定です。

高校数学やり直してみた時に使った教材や勉強法やあれこれ

このエントリーは 機械学習に必要な高校数学やり直しアドベントカレンダー Advent Calendar 2016の2日目です。
1日目は現役高校生の方のエントリーでした。自分もこういう話を現役の頃に先生や同級生としたかったですね。現役の頃は数学って大学に行くための手段程度にしか思ってなくて、今考えたら非常にもったいなかったなと思います。。

これは何か

  • Railsおじさんが機械学習の手法を使って仕事でデータ分析できるようになることを目標に12年ぶりに高校数学を復習した(ている)記録です

きっかけ

  • もともと機械学習に興味があったのだが、いい加減仕事でちゃんと使えるレベルになってRailsしか能がないおじさんから脱却しようと思い立ち、2016年5月ぐらいから「データサイエンティスト養成読本 機械学習入門編」を読み始めた

  • のだが、途中途中で出てくる数式の意味が理解できなくてモヤモヤした。

  • わからない所は飛ばしつつ、まずは大枠を理解しようと頑張って読んでいたのだがやっぱりモヤモヤする
  • なので数学をちゃんとやり直すことにした
  • 機械学習でよく出てくる線形代数、等比級数、確率、みたいにピンポイントで勉強し直せばいいかなと思ったけど、いい機会なので高校数学をまるっとやり直すことにした。

やったこと(時系列順)

高校数学をざっとやり直す

  • まずは高校数学一通りやり直そうと思ってことでこれを買って一通り練習問題を手で解いた。

もう一度高校数学

もう一度高校数学

  • 主に平日に出社前と帰宅後にちょっとずつ解いていき、大体2ヶ月ぐらいで一通り最後までやり終わった。
  • 仕事が忙しかった時期と被ってたりもしたので平日1日の勉強時間は平均して1時間にも満たない程度だったと思う。平日全然できなくて休みの日にガッツリやったりしたときもある。
  • この本にも書いてあるが、テキストを読むだけでは頭に入ってこない。実際にペンと紙で問題を解くことが重要だと感じた。(当たり前だけど)

その時の勉強ノート。字の汚さは昔と全く変わっていない…*1 f:id:serihiro:20161126130616j:plain

12年ぶりに高校数学を勉強してみた気づき

  • 高校数学なんて高校卒業以来12年近く使ってなかったのに、手を動かして問題解き始めたらすぐ思い出せたりして人間の記憶ってすごいなーと思った
  • 高校時代よりかはゆっくりしたペースで勉強できるので一個ずつ自分のペースで理解できてとても楽しい
  • 特に、高校時代はただ丸暗記していただけの公式を、導き方含めてその意味をじっくり考える良い機会になった

高校数学をやり直した成果を形に残したいと思って数学検定を受けてみた

  • 勉強中に、調べたら数学検定という検定試験があったので、まずは高校2年生レベルの2級を受けてみることにした。
  • 調べたら直近の試験日まで1ヶ月程度しかなかったが勢いで受けてみることにした。
  • 教材として上記の本に加えて過去問集を買って解きまくってみた。
  • 過去問の正答率はギリギリ受かるか受からないかといったライン。何度も繰り返し勉強した。

結果

  • センター試験レベルの一次試験は受かったが、二次試験は大問を合計5問説いて各1点満点という配点だったのだが、計算ミスって0.2点足りなくて不合格だった。
  • ので、来年リベンジしたい*2
    • 追記: 2017年11月に合格.なお准1級と1級はいまだに取れていない...

  • 二次試験の応用問題は青チャートの例題レベルをやっておかないと厳しいかと感じた。過去問で出てないパターンの問題が1パターンずつぐらいは毎回増えていっているように見える。
  • ので、これまた15年近くぶりに青チャート買った。昔は数学は基本的に青チャートシリーズだけで勉強してたが、まさかおっさんになってから改めて買い直すとは思ってなかった。

チャート式基礎からの数学2+B―新課程

チャート式基礎からの数学2+B―新課程

高校数学を改めて勉強してみて思ったこと

  • 現役高校生の頃はセンター試験対策の勉強しかしてなくて、公式丸暗記して問題を解く方法しか練習しておらず「数学が楽しい!」なんて全く思わなかったのに、「機械学習でデータ分析ができるようになる」ことを目標を持って勉強してみるとすごく楽しく感じた。
  • また、数学検定受ける際に時間がなかったので、必要な公式をすべて丸暗記することはできないと分かっていたので、最低限の公式から必要な公式を導けるように勉強してみた。その結果、12年越しに現役高校生の頃にやってたことの意味が理解できるようになったりして新たな発見が多かった。
  • あと特に三角関数複素数平面、ベクトルの辺りの横のつながりや、行列で計算することの意味を少しは理解できるようになった。
    • 昔はこれらの繋がりなんてまるで考えてなかったが、社会人になってプログラミングするようになってから「どういうデータ構造でデータを表現して問題を解決するか」という考え方が身に付いたことも関係しているのかもしれない。

まとめ

*1:なお、後述している数学検定の二次試験は計算過程含めて筆記なので、普段手書きで字を書かない自分にとっては採点者に読める字で時間内に回答を書くのは結構苦労した。。

*2:本当は今年もう一度試験日があったのだがTOEICと被ったので断念した

PageRankについて調べてみた

この記事はトレタ Advent Calendar 2016の2日目です。
1日目は弊社iOSエンジニアのhorimislimeによるリリース自動化だけじゃないfastlane活用方法でした。恥ずかしながらfastlane初めて知ったんですが便利ですね。あと関係ない話ですがなぜか弊社のiOSエンジニアは普通にruby書けるのでビビります…

概要

PageRankについて

PageRankが生まれた時代背景

  • Googleの前身であるBackRubが開発された1996年当時、他の商用検索エンジン転置インデックスを用いた全文検索を主な検索の手段としていたケースが多かった(AltaVistaなど)
  • しかし、それらの商用検索エンジンは、人間から見て実用的な検索結果を表示することが非常に困難な状態にあった。単純に検索クエリとページに含まれるキーワードの一致数などを使って表示順序を決定していたため、そのページに価値があるかどうかを評価することができなかった。
  • また、特定のタグに同じキーワードを沢山いれるなどするだけで簡単に任意のページの検索ランキングを操作することができ、スパマーの攻撃の的にされるという問題も抱えており、ますます実用性からはかけ離れていた。*1
  • その一方で、webサイト上のリンクのつながりから自律的にページの重要度を学習するBuckRubは、検索結果の表示順序を決定する際にPageRankによって算出された「ページの重要度」を用いていたため、他の商用エンジンと比べ「実用的な」検索結果を表示することができた。
  • 2016年8月現在においてもGoogle内部でページランクが「ページの重要度」を評価するために用いられていると公表されている

基本的なアイデア

PageRankの基本的なアイデアは下記がベースとなっている(後述するが実用的なスコアを算出するためには若干の調整が必要になるので単純に実際のリンク数だけで決定している訳ではない)

  • 沢山のページからリンクを貼られているサイトほど重要(以後本記事ではこのリンクを 入リンク と呼称)
  • 他のページにリンクを貼る時、重要なサイトから貼られたリンクの方が価値がある(以後本記事ではこのリンクを 出リンク と呼称)
  • 出リンク の価値は1つのサイトから貼られている 出リンク の数に反比例する

webサイトのPageRankスコアを計算してみる

以下のように6つのページが互いにリンクを貼っている状況を考える(それぞれのノードが1つのWebサイト) f:id:serihiro:20161118160538p:plain

Lawrence Page とSergey Brinは、当初下記の計算式によりPageRankスコアを求めた。*2

 \displaystyle
  \mathrm r(P_{i}) = \sum_{ P_{j} \in B_{P_{i}} } \frac { \mathrm r(P_{j}) } { \mathrm |P_{j}| }

ここで

  •  \displaystyle r(P_{j}) : ページPjのPageRank
  •  \displaystyle P : 全ページの集合
  •  \displaystyle B_{P} : 入リンクの集合*3
  •  \displaystyle \mathrm |P_{j}| : ページPjの出リンク数の総数

この数式を反復法で繰り返し計算することでPageRankのスコアを求めることができると考え、k+1回目の繰り返しで求められるスコアを

 \displaystyle
   r_{k+1}(P_{i})

とすると

 \displaystyle
  \mathrm r_{k+1}(P_{i}) = \sum_{ P_{j} \in B_{P_{i}} } \frac { \mathrm r_{k}(P_{j}) } { \mathrm |P_{j}| }

となる。

ここで、当然ながらk=0の時の値(つまり初期値)を何の値とするかという問題が発生するが、Lawrence Page とSergey Brinは初期値として集合Pに含まれるページ数の逆数を用いたとされる。今回の例で言えば、Pにはページが6個含まれるので、k=0の時は一律で 1/6 となる。

単純なアプローチによるスコア計算

上記の数式を用いて実際にスコアを計算してみる。*4
 \displaystyle r_{1}(P) から計算してみる。

 \displaystyle
  \mathrm r_{1}(P_{1}) = \frac { \mathrm r_{0}(P_{3}) } { \mathrm |P_{3}| } = \frac 1 6 / 3 = \frac 1 {18}
 \displaystyle
  \mathrm r_{1}(P_{2}) = \frac { \mathrm r_{0}(P_{1}) } { \mathrm |P_{1}| } + \frac { \mathrm r_{0}(P_{3}) } { \mathrm |P_{3}| }  = \frac 1 6 / 2 +  \frac 1 6 / 3 +  = \frac {5} {36}
 \displaystyle
  \mathrm r_{1}(P_{3}) = \frac { \mathrm r_{0}(P_{1}) } { \mathrm |P_{1}| } = \frac 1 6 / 2 = \frac {1} {12}
 \displaystyle
  \mathrm r_{1}(P_{4}) = \frac { \mathrm r_{0}(P_{5}) } { \mathrm |P_{5}| }  + \frac { \mathrm r_{0}(P_{5}) } { \mathrm |P_{6}| }  = \frac 1 6 / 2 + \frac 1 6 / 1 = \frac {1} {4}
 \displaystyle
  \mathrm r_{1}(P_{5}) = \frac { \mathrm r_{0}(P_{3}) } { \mathrm |P_{3}| } + \frac { \mathrm r_{0}(P_{4}) } { \mathrm |P_{4}| }  = \frac 1 6 / 3 +  \frac 1 6 / 2 +  = \frac {5} {36}
 \displaystyle
  \mathrm r_{1}(P_{6}) = \frac { \mathrm r_{0}(P_{4}) } { \mathrm |P_{4}| } + \frac { \mathrm r_{0}(P_{5}) } { \mathrm |P_{5}| }  = \frac 1 6 / 2 +  \frac 1 6 / 2 = \frac {1} {6}

つづいてk=1の時のスコアを使ってk=2のスコアを反復的に求めてみる。texで書くのがめんどくさくなってきたので細かい計算は省略する。

 \displaystyle
  \mathrm r_{2}(P_{1}) = \frac { \mathrm r_{1}(P_{3}) } { \mathrm |P_{3}| } = \frac 1 {36}
 \displaystyle
  \mathrm r_{2}(P_{2}) = \frac { \mathrm r_{1}(P_{1}) } { \mathrm |P_{1}| } + \frac { \mathrm r_{1}(P_{3}) } { \mathrm |P_{3}| }  = \frac 1 {18}
 \displaystyle
  \mathrm r_{2}(P_{3}) = \frac { \mathrm r_{1}(P_{1}) } { \mathrm |P_{1}| } = \frac 1 {36}
 \displaystyle
  \mathrm r_{2}(P_{4}) = \frac { \mathrm r_{1}(P_{5}) } { \mathrm |P_{5}| }  + \frac { \mathrm r_{1}(P_{5}) } { \mathrm |P_{6}| }  = \frac {17} {72}
 \displaystyle
  \mathrm r_{2}(P_{5}) = \frac { \mathrm r_{1}(P_{3}) } { \mathrm |P_{3}| } + \frac { \mathrm r_{1}(P_{4}) } { \mathrm |P_{4}| }  = \frac {11} {72}
 \displaystyle
  \mathrm r_{2}(P_{6}) = \frac { \mathrm r_{1}(P_{4}) } { \mathrm |P_{4}| } + \frac { \mathrm r_{1}(P_{5}) } { \mathrm |P_{5}| }  = \frac {14} {72}

k = 2の時点でスコアを降順ソートすると

 \displaystyle
\mathrm r_{2}(P_{4}) > \mathrm r_{2}(P_{6}) > \mathrm r_{2}(P_{5}) > \mathrm r_{2}(P_{2}) > \mathrm r_{2}(P_{1}) = \mathrm r_{2}(P_{3})

となり、6ページ間のランキングが作成できる。*5

総和計算から行列計算に置き換えて考える

ここで、最終的に得られるPageRankのスコアのリストを、n次元ベクトル(nは集合Pに含まれるページ数)と捉えると、上記の計算はn * n行列とn次元ベクトルの積として考えることができる。*6

具体的には、総和式の代わりに以下の行列を導入することで、先に行ったPageRankスコアの計算を単純な行列計算として考えることができる。

 \displaystyle
\begin{equation}
H=
\begin{vmatrix}
0 &\frac {1} {2} &\frac {1} {2} &0 &0 &0 \\
0 &0 &0 &0 &0 &0 \\
\frac {1} {3} &\frac {1} {3} &0 &0 &\frac {1} {3} &0 \\
0 &0 &0 &0 &\frac {1} {2} &\frac {1} {2} \\
0 &0 &0 &\frac {1} {2} &0 &\frac {1} {2} \\
0 &0 &0 &1 &0 &0
\end{vmatrix}
\end{equation}

Hi行の要素は、ページ Pi が持つの出リンクの有無を示す。

例えば H[1] 行においては H[1][2]H[1][3] のみが非0で、それ以外は0になっている。これは、 P1P2P3 に対する出リンクを保持しており、それ以外のページに対してはでリンクを保持していないことを示している。*7

要素の値がそれぞれ 1/2 となっているのは P1 の持つ出リンクの個数で除している為である。これは、先に示した総和式でPageRankスコアを計算した時、各ページのスコアを |Pj| で除した処理に対応した前処理である。

Hj 列の要素は、ページ Pj が持つ入リンクの有無を示す。 例えば H[1] 列においては H[3][1] のみが非0で、それ以外は0になっている。これは、 P1P3 からの入リンクを保持し、それ以外のページからの入リンクを保持していないことを示している。H[3][1] 要素が1/3 なのは、先に説明したとおりP3の出リンクの総数で除されている為である。

この行列Hを用いると、先に掲載した

 \displaystyle
  \mathrm r_{k+1}(P_{i}) = \sum_{ P_{j} \in B_{P_{i}} } \frac { \mathrm r_{k}(P_{j}) } { \mathrm |P_{j}| }

は以下のように書き換える事ができる。

 \displaystyle
  \mathrm r_{k+1}(P_{i}) = \sum_{ j = 1 }^n H_{ji} \times { \mathrm r_{k}(P_{j}) }

ここで、

 \displaystyle
\begin{equation}
\pi^{(k)T}=
\begin{vmatrix}
r_{k}(P_{1}) &\cdots &r_{k}(P_{n})
\end{vmatrix}
\end{equation}

と定義される行ベクトル  \displaystyle \pi^{(k)T} を導入すると、

 \displaystyle
\pi^{(k+1)T} = \pi^{(k)T}H

と置き換えられる。

なお、実際に行列計算をする時は

 \displaystyle
\pi^{(k+1)} = H^{T} \times \pi^{(k)}

として、Hの転置行列に右から列ベクトル  \displaystyle  \pi^{(k)} を乗じる必要がある(と思うのだが、なぜか参考にした書籍ではこの辺のことが記載されていなかった。。そんなもんは数学者の間では常識なんだろうか?)

単純なアプローチをそのまま用いて計算する場合の問題点

しかしこの式には以下のような問題があると参考にした書籍では指摘されている。

  • いつか  \displaystyle \pi^{(k)T} は収束するのか?
  • 計算を繰り返す回数は何回が最適なのか?10回か?20回か?それ以上か?

また、実際、先に掲載した式で  \displaystyle \pi^{(13)T} ぐらいまで求めると `(0 0 0 2/3 1/3 1/5) となり、一部のページにスコアが隔たってしまうという問題もある。

これらの問題を解決するためにLarry PageSergey Brinは以下の調整を行った。以下の調整を行うことで  \displaystyle \pi^{(k)T} がある定常ベクトルに収束することがべき乗法の考え方から収束することが保証される*8

ハイパーリンク行列を調整する

Larry PageSergey Brinが行った調整は下記の2つ。

出リンクを1つも持たないページには他のページに出リンクがあることにする

出リンクがないページに到達したらどっか適当なページに飛ぶじゃろ、という前提で他のページに対する出リンクが同確率で「あること」にする。

例えば P(2) は出リンクを持たないページなので、 H[2] の行において、全ページに対して出リンクを持つことにする。

つまり一定の確率で他のページにジャンプする、という概念を導入することになる。Larry PageSergey Brinの論文では ランダムサーファー と呼称されている。

この調整により先の数式で出てきた行列 H を用いて新たな確率行列 S が定義される。

 \displaystyle
S = H + a(1/ne^{T})

ここで a は出リンクを1つでも持つPは0、ないPを1とする2値ベクトルとする。

全てのページから関係のないページに一定の割合で他のページに出リンクがあることにする

出リンクがあるページを閲覧していたとしても突然関係ないページに飛ぶじゃろ、という前提で、全ページに対する出リンクが同確率で「あること」にする。

その結果、更に調整を行った新たな行列 G が登場する。

 \displaystyle
G = {\alpha}S + (1-\alpha)1/nee^{T} \\
\ \ \ = {\alpha}(H + a(1/ne^{T})) + (1-\alpha)1/nee^{T} \\ 
\ \ \ = {\alpha}H + ({\alpha}a + (1 - {\alpha}e)1/ne^{T} \\

 \displaystyle \alpha は0と1の間のスカラーである。googleでは長い間 0.85 が使われていたらしい。

実際に先に挙げた例で G を計算すると以下のようになる。

 \displaystyle
G = 0.9H + ({0.9}
\begin{vmatrix}
0 \\
1 \\
0 \\
0 \\
0 \\
0
\end{vmatrix}
+ {0.1}
+ \begin{vmatrix}
1 \\
1 \\
1 \\
1 \\
1 \\
1
\end{vmatrix}){1/6}
\begin{vmatrix}
1 &1 &1 &1 &1 &1
\end{vmatrix}

 \displaystyle \pi^{T}はGに対する定常ベクトルで、以下のようになる。参考書籍よりそのまま抜粋。参考書籍掲載のMATLABの参考実装で計算したものらしい。

 \displaystyle
\pi^{(k+1)T} = \begin{vmatrix}
0.03721 &0.05396 &0.04151 &0.3751 &0.206 &0.2862
\end{vmatrix}

参考書籍に掲載されていた参考実装では π(k)Tπ(k-1)Tノルムの差が一定数値以下になるまで計算を繰り返した最後の π(k)T を定常ベクトルとして扱っているらしい。要するに、1回前の計算値と最後の計算値の差が十分小さくなったら収束した、と見なすというアプローチらしい。

 \displaystyle \pi^{T} は以下の固有ベクトル問題を解くことでべき乗法で繰り返し計算しなくても近似的に求める方法があるらしいが、自分の数学力と時間が足りなくて固有値問題についてよく理解できないので誰か教えてほしい…(要勉強)

 \displaystyle
\pi^{T} = {\pi^{T}}G

自分でもrubyで実装してみた

最後に、自分がrubyで実装したpagerankのスコアをべき乗法で求めるコードを掲載しておく。

bitbucket.org

なるべく参考書籍の数式がそのまま動く感じになるように実装した。

実際にべき乗法で繰り返し計算するループは下記のような感じ。本文でも記載しているが、G 行列を転置して列ベクトルである pie を右から乗じて計算している。行列計算においてはrubyMatrixクラスが非常に便利だった。

収束したかを判定する @residual_erorr は参考書籍の参考実装から持ってきた 1e-8 を使っている。

    _transposed_google_matrix = google_matrix.transpose

    loop do
      previous_pie = pie
      pie = _transposed_google_matrix * pie
      if pie.norm - previous_pie.norm < @residual_erorr
        break
      end
    end

まとめ

  • ページランクの概要はざっくり知っていたが、いざ書籍を一冊読んでちゃんと調べると数学的な奥深さが半端なく、その辺のバックグラウンドがない自分には難解でほとんど理解できてないように感じる。実際、参考書籍は前半においてはオリジナルの論文の解説といった感じだが、後半は収束速度とパラメータの数値の調整に関する議論やPageRank以外でのランキングについて記されているのだが、その辺の内容が高度すぎてまだ理解できていない。
  • これをきっかけ確率過程やマルコフ連鎖について勉強していきたいと感じた。実際、確率過程についてはネットで拾った大学講義の資料とかで調べてみたらかなり面白く、自然言語処理機械学習の分野でもこれが理解できないといつか詰みそうな内容だったので、いつか単独でブログネタにしたい。*9
  • トレタ Advent Calendar 20163日目はmasuidriveによる「Railsで新規サービスを作る時に使うべきサービス」です。

参考資料

*1:CCCメディアハウス「グーグル ネット覇者の真実 追われる立場から追う立場へ」より

*2:この数式は書籍 「Google PageRankの数理」に記載されていた通りのものだが、書籍中では出典が明らかになっておらず、また、オリジナルの論文である 「The Anatomy of a Large-Scale Hypertextual Web Search Engine」 にはこの数式は書かれていない。Lawrence Page と Sergey Brin によるもう一つの論文 「PageRank, an Eigenvector based Ranking Approach for Hypertext」 の方に記載があったのかも知れないが、この論文はweb上で本文が見つからなかったため確認できなかった。無念。

*3:Lawrence Page とSergey Brinらが入リンクのことをBacklinkと論文の中で記述していたのでBを使っているのだろう

*4:このあたりから段々tex記法で数式書くのが辛くなってきた…ので段々サボり出しているがはてなブログにおけるmarkdowntex記法の組み合わせが最悪なのでご了承いただきたい

*5:ページ1とページ3のスコアが同値なので、2つのページが同じ検索結果に含まれる場合にどう並べるかという問題に対しては、別の評価パラメータを用いて総合的に優劣を決定しているものと考えられる。

*6:実際は行列と行ベクトルの積は直接計算できないので(懐かしの数Cでやったことを思い出そう)それぞれの転置行列同士の積を取ることになるのだが、アカデミックの世界ではその辺をよしなにやってくれる計算ライブラリを使うのが常識なのかどうかは分からないが「PageRankの数理」においてはその辺の説明を端折っている

*7:ここでtex使わないで書いているのは、同じ行にtex記法で書くとはてなブログが展開してくれないからである。。

*8:なぜ保証されるかは参考書籍を読んでも良く分からんかったが、調整したH行列の固有値を用いることで収束することが証明できるらしい…要勉強

*9:公開されている大学の講義資料にいつも助けられている。機械学習自然言語処理の方で調べ物するときも信頼のおける情報ソースとしていつも使わせていただいている。工学系の学位取ってない自分にとってはホントありがたい。

エンジニアの立ち居振舞い:過度に仕組みを作らない

お題「エンジニア立ち居振舞い」

特に仕事でコードを書く場合で意識してることだけど、過度に仕組みを作らないというのを大事にしている。

ここで、過度な仕組みとは例えば最初から以下のような実装をすることを指すことにする

  1. 1つのクラスでしか使われないコンテキストの上に成り立つ実装をグローバルなクラスに切り出してそのクラスを他のクラスからも使えるように実装する
  2. テンプレートメソッドパターンを適用して部分的に実装を差し替えられる用に実装する
  3. 例えばjavaとかで実装クラスは現時点で一つしかないのに最初からインターフェースを用意する

要するに、万人が使うようなフレームワークやライブラリを実装するかのように拡張性の高いコードを実装してしまうことを指す。

過度な仕組みを作れば作るほど、仕組みの動作を保証するのに必要なUTの量は増加し、実装量も増えてレビューは大変になり、またその部分を修正する人はロジックそのものに加えて仕組みそのものの仕様理解にも時間を取らされたりと、色んな人の工数を大量に消費する。

それでもまだ本当にそんな仕組みが必要だろうか?自分たちが今必要としているのは動く実装でありフレームワークではない。

自分が過度な仕組みを持つ実装をする場合は、今から作ろうとしている実装において、明らかにコピペできるレベルの実装がいくつもあるなーと感じた時だけにしている。これもしかしたら他でも使うかもなーと思うこともあるのだが、それでも一箇所でしか使われないコードならグッと我慢してベタッと実装する。

もちろん機能的な分解点やUTの書きやすさを意識してメソッド自体はあれこれ分割したりスコープを考えたりクラスを分けたりといったことはするが、しょっぱなからサブクラスを作ってそのクラスをオーバーライドするところから実装を始めたりはしない。

なぜか?今作ろうとしている目の前の機能こそが一番大事だからだ。

今作ろうとしている機能を過不足なく、他のメンバーが理解しやすい形の落とし所に納めて、リリースすることこそが一番大事だからだ。だから無駄なことはしない。早く作って早くリリースする。

そして時が経って、必要になったらその時初めて抽象化でもなんでもする。

大事なことは常に「今」必要最低限のものだけで始めて、「必要なとき」に素早く拡張できることだと思う。

今読んでる本とか

完全に自分用のメモ。

平行してその時の気分で読む本を選んで読む癖があるのでたまに何読んでたか忘れて最初から読み直すハメになったりする。

今読んでる

Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―

Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―

Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

コンピュータの構成と設計 第5版 上

コンピュータの構成と設計 第5版 上

インテル 世界で最も重要な会社の産業史

インテル 世界で最も重要な会社の産業史

積んでる

ペンギンが教えてくれた 物理のはなし (河出ブックス)

ペンギンが教えてくれた 物理のはなし (河出ブックス)

ハイパフォーマンス ブラウザネットワーキング ―ネットワークアプリケーションのためのパフォーマンス最適化

ハイパフォーマンス ブラウザネットワーキング ―ネットワークアプリケーションのためのパフォーマンス最適化

HTTP: The Definitive Guide (Definitive Guides)

HTTP: The Definitive Guide (Definitive Guides)

  • 作者: David Gourley,Brian Totty,Marjorie Sayer,Anshu Aggarwal,Sailu Reddy
  • 出版社/メーカー: O'Reilly Media
  • 発売日: 2002/09
  • メディア: ペーパーバック
  • 購入: 1人 クリック: 34回
  • この商品を含むブログ (1件) を見る

はじめてのパターン認識

はじめてのパターン認識

今年読んだ本で面白かったやつ(ソート順は適当)

グーグル ネット覇者の真実

グーグル ネット覇者の真実

  • adwordsのアイデアは最初からあったと思ったんだけど、当初はマネタイズ手段としては検索エンジンのライセンスビジネスを考えていたというのと、adwordsと似たようなアイデアが他社検索エンジンにすでにあったのは初めて知った。
  • googleのproductの強みはオリジナリティよりも泥臭い努力に裏打ちされた愚直な性能の高さにあるんやなってはっきりわかるんだね。
  • googleの中国撤退の話は多分ほかのメディアよりずっと詳しかったのではと思った。

サーチ・インサイド・ユアセルフ――仕事と人生を飛躍させるグーグルのマインドフルネス実践法

サーチ・インサイド・ユアセルフ――仕事と人生を飛躍させるグーグルのマインドフルネス実践法

  • 作者: チャディー・メン・タン,ダニエル・ゴールマン(序文),一般社団法人マインドフルリーダーシップインスティテュート,柴田裕之
  • 出版社/メーカー: 英治出版
  • 発売日: 2016/05/17
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログ (6件) を見る

  • googleの宣伝的な文章が結構多くて最初の方はもどかしく感じたが、その後に続くマインドフルネスの具体的な内容については割と詳細に書かれている。
  • 個人的な感想としては瞑想に対する敷居がかなり下がった感じ。今でも忘れない限りは寝る前に瞑想をしている。
  • 運動と瞑想の習慣がない者の末路は(ry

SOFT SKILLS ソフトウェア開発者の人生マニュアル

SOFT SKILLS ソフトウェア開発者の人生マニュアル

コンピューターで「脳」がつくれるか

コンピューターで「脳」がつくれるか

ザ・チーム 日本の一番大きな問題を解く

ザ・チーム 日本の一番大きな問題を解く

突撃! オトナの大学院

突撃! オトナの大学院

チームが機能するとはどういうことか――「学習力」と「実行力」を高める実践アプローチ

チームが機能するとはどういうことか――「学習力」と「実行力」を高める実践アプローチ

アメリカ大学院留学 - コンピュータ・サイエンス

アメリカ大学院留学 - コンピュータ・サイエンス

作家の収支 (幻冬舎新書)

作家の収支 (幻冬舎新書)

ITエンジニアが覚えておきたい英語動詞30

ITエンジニアが覚えておきたい英語動詞30

Java 謎+落とし穴 徹底解明 (標準プログラマーズライブラリ)

Java 謎+落とし穴 徹底解明 (標準プログラマーズライブラリ)

やさしいコンピュータ科学 (Ascii books)

やさしいコンピュータ科学 (Ascii books)

cでwebサーバを書き始めた

趣味でcでwebサーバを書き始めた。 8月末ぐらいからちょっとずつ作業を進めていたのだが、とりあえずhtmlファイルをレスポンスするところまでは実装できたのでgithubに公開した。

github.com

名前の由来は旧日本海軍が第二次大戦時に開発したオートジャイロの名前を拝借した。何となく、サーバー系プログラムには空を飛んでる何かの名前を付ける習慣があると思っているのでその習慣に倣ってみた。

書き始めた理由は今年開催のいくつかのカンファレンスでOku Kazuhoさんのhttp2のセッションを聞いてhttp2の実装に興味が湧いたからなのだが、それ以前にhttpもよく分かってない。ということでhttpの勉強も兼ねてまずはhttp1.1サーバを書いてみようと思った。また、せっかく新しいものを書くなら使ったことがない言語にしよう、ということでcで書くことにした。あとパタヘネ読んでたら低レイヤーを触れる言語を1つはちゃんと書けないと理解できないことが沢山あるという危機感を感じたという理由もある。

今はまだhtmlファイルしか返せない(.htmlか.htm以外の拡張子を指定すると415を返す)し、 ../../tmp/hoge.html みたいなパスにアクセスされると一発でアウトみたいなセキュリティホールだらけなのだが 、一般的な静的ファイルを置いて使う程度には困らない程度のものに仕上げたいと思っている。実装予定のfeatureはREADME.mdに記載した。

あとcのノウハウが全然ないので手探りで書いてる感が半端ない実装状態である。char配列のバッファサイズとかかなり適当だし、どういう時にmalloc使うべきでどういう時に配列使えばいいかもよく分かってない。どう最適化すればよいのかも併せて勉強していく必要がある。あとMakefileも適当に書いているしgccのオプションも言われるがままにホイホイコピペしてきたものである。とりあえずgdbデバッグするために-g o0 は付けているが、これもホントはmake debug みたいなdebug用taskに分離して置いた方がいいのだろうか。周りにcでプロダクト書いてる人がいないのでこの辺の知見が得られなくて中々に辛い。

余談だが、趣味プロダクトが一つでもあると心が落ち着くというか、仕事で辛いことがあったり退屈していても、家に帰ってからあのバグを直そうとかあれを実装しようというポジティブな予定が持てて、精神衛生上良いのでオススメである。

自分にはもう一つの趣味プロダクトslidesearch.jpというwebサービスもあるので、こちらについてもたまにrailsとかgemのバージョンを上げたり細かいバグを直したりという作業を日課としている。大したUIはないのだが、自分の勉強のためだけにフロントをangular2で書き直してSPAにするかとか色々考えている。

周囲からの期待値を自分で決めて自分で動くということ

今の会社に入ってから新たに増えたタスクとして、「周囲からの自分に対する期待値を自分で決めて動く」というタスクがある

今までの会社でいえば、「お前に期待することはこういうことだから」というのを教えてくれる人がいた。その上で自分がやりたいことを踏まえてどういうことをやっていくかを決定してきた。 だから周囲の期待値は何となく見えていたし、自分でもそれについて納得しながら仕事をしてきた。言い方を変えれば「走るべきレールが決まっていてその上でいかにパフォーマンスを出すか」ということに集中していた。

それが今の会社では、誰もレールを引いてくれない状態になった。これは会社の方針として開発チームに意図的にマネージャーを置いていないからなのだが、この状況に当初は戸惑った。 自分の期待値は当然伝えられず、何をすべきか分からず、何を期待されているかすら分からず、さらに言えば、何故自分が今の会社に採用されたのかすらわからなかった。(一応聞いてはみたが、まぁそこまで自分である理由はなかった。)

ということで、「どうすれば自分がこの会社で価値を発揮できるか?」を自分で考える必要が出てきた。

入社して最初の3か月でやったことは、サーバーサイドチームの開発体制の見直し。 デプロイ頻度の固定化、相互レビューの導入、エラー監視のためのBugsnag導入、CircleCIの導入、定例ミーティングの導入、Hubot導入などなど、これまでいた会社でやってきて上手くいったことを導入して足場を整える仕事を中心に行った。「誰かにやれ」と言われたからやったのではなく、「今これをやれる知識があるのは自分しかいない」という自己判断の元行った行動である。誰も文句は言わなかったし、多少抵抗があった項目もあるが説得して導入していった。今でも適宜チーム内で話し合ってやり方は都度見直している。

serihiro.hatenablog.com

また、もう一つの自分の役割として「コードの品質を担保する」というのがあると思っている。スタートアップならよくあることなのだろうが、今までスピード重視で書かれてきたコードベースは必ずしも綺麗ではなかった。Rails純正の機能を使えば解決できることを自前で処理していたり、そもそも問題を抱えたまま運用していたり、課題を結構抱えていた。

しかし、それは「課題」として認識されていないものが多かった。要するに、それを「課題」だと気づける人間がいなかった。自分は気づける人間だったので、その課題を直していくことが自分の役割だと今も考えている。

普段やりたくてもできないタスクを1日かけて消化する「改善部」イベントを企画してrubocopを導入したり(もちろん.rubocop.ymlは意味のある指摘だけに絞るようにいじり倒した上で)、普段からコードベースをいじるときに既存のコードでリファクタできるところはリファクタし、新規に書くコードは後から入ってくる人が真似したとしても負債が残らない、変なコードにならないようにすることを第一に考えてコードを書くようにしている。

レビューは自分一人だけでやってる訳じゃないのですべてのコードを見られる訳ではないが、自分がレビューするコードはなるべくそういう観点で見ている。もうスピードだけでコードを適当に書き殴ってプロダクトを作っていいフェーズの会社ではないからだ。ユーザーが増えるにつれて安定稼働への責任に重きをおく必要が高まっている。もちろん、この認識は自分がセールスやサポートの人と話をしていて思っているだけであるが。

今のところ、普段のタスクをやりつつ上記のようなことを念頭において仕事しているが、今のところ誰からも「それよりこういうのやってよ。」「お前最近価値のある仕事してないよ。」と言われることはないので周囲からの「実際の期待値」も「自分が考える周囲からの期待値」とそこまでズレてないようだし、自分の仕事はそこそこ会社に貢献できているのではないかと思っている。 この辺も誰からもフィードバックをもらったことがないので分からないが、とりあえず誰かから何か言われるまで、あるいは自分の仕事が意味がないと自分が感じるようになるまでは、今やっている草の根活動を続けようとは思うし、今後も必要そうなタスクが見つかったら開発チームに提案して自分でやってみようとは思う。

VP of Engineeringみたいなポジションの人がいる規模の開発組織だと、この一連の作業はそういうポジションの人がやるんだろうけど、ウチみたいなスタートアップにおいてはまだ自律的に各メンバーが考えて行動する必要がある。自分は少なくともそう考えているし、他のメンバーもそれぞれ必要だと思うことを自律的に考えてやっている節がある。どこまで今の体制で開発チームがスケールできるか分からないが、少なくとも自分で何が必要かを考えて動くというのは、自分の経歴としても良い経験だと考えているので、とことん必要なことを考えて自律的に動いてやろうと思っている。