歩いたら休め

If the implementation is easy to explain, it may be a good idea.

【情報検索】文章スコアのTF-IDFとBM25についてポインタを残しておく

OSS検索エンジンであるSolr/Luceneの勉強会に行っていました。

solr.doorkeeper.jp

この中の発表『Solrで多様なランキングモデルを活用するためのプラグイン開発』で、

  • SimilarityにはTF-IDFとBM25の二種類あり、Solr6からはBM25がデフォルトになっている
  • SolrのTF-IDFは、同じ単語が大量に出てきた際にスコアが極端に大きくならないように、TFが補正されている(√がかかっている)

という話があり、私は情報検索については不勉強なので、BM25は初めて聞く単語でした。

qiita.com

特徴

[改訂第3版]Apache Solr入門には次のように書かれています。271ページからの引用です。

  1. TFIDFSimilarityのような複雑な補正の仕方がなく,一般的なBM25である
  2. BM25は変数を2つ追加することで,TFIDFSimilarityが行おうとしていた補正の程度をコントロールできる
  3. tfに√よりもさらに上昇が抑えられる非線形変換がかかっている
  4. idfがシンプルになっている
  5. ヒットしやついドキュメントにかかるペナルティのかけ方も異なる

また、こちらのブログには次のように書かれています。また、『Information Retrieval: Imple- menting and Evaluating Search Engines』という教科書に詳しく解説されているという記述があります。

BM25って何? という質問には「文書長正規化したTF-IDF」と答えるようにしており,経験的に性能が良いことが知られている,という情報を加えれば使う分には十分だと思っている.

ただBM25を教科書で見かけると「背景には確率的情報検索てものがあってな」という記述を何度か見かけるし,一応検索をやってますというような人間がBM25が生まれた背景や,その背景とされる確率的情報検索について知りません,というわけにもいかない.

アプリケーションとして利用するには、とりあえずこのことを把握しておけば良さそうです。ただ、もしきちんと理解したいなら、鈍器のような本を読まなきゃいけなさそうです。

Python実装

文章の特徴量というと、検索エンジンだけでなく、データマイニング方面での実装も気になりますね。

ただし、機械学習や統計処理で使うライブラリでは、scikit-learnではTfIdfVectorizerのような形では実装されていませんでした。ただし、以下のライブラリを代わりに作成した方がいるようですね。

kujira16.hateblo.jp

トピックモデル用のライブラリgensimでは使われてるようですね。

radimrehurek.com

ただ、テキストマイニングでは統計モデルの特徴量としてTF-IDFを使うので、「同じ単語が大量に出てきた際にスコアが極端に大きくならないようにTFを補正したり、BM25を利用する」ようなモチベーションはあるのでしょうか?

参考文献

こちらの本を引用しています。

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

【本】最近読んでいる本(特に不動産関連)

最近はあまり本を読んでいませんが、一応何冊かは読んだので。

テキストマイニングを使う技術/作る技術(那須川哲哉)

最近、業務でテキストマイニングで業務支援を行う案件にアサインされており、ゴリゴリコードを書くことになりそうだったので読んでいます。

社内の研究部署の方から「IBM那須川さんの論文は読んでおくといいよ」と紹介いただいたのがきっかけです(日本語の論文でよかった!)。

エキスパートの素顔:第13回 那須川 哲哉 | IBM ソリューション ブログ

世界的にも有名な研究者である那須川さんのデータ分析を間近で見ているのですが、何といいますか、分析そのものが本当に「エレガント」なのです。決して難しいことをやっているようには見えないのですが、とにかく驚くような結果を出すのです。例えば、データ分析を通し、コールセンターのエージェントの方の質を見抜いてしまう、製品の不具合を世に出る前に発見してしまう。また、研究会の活動のひとつとして最近取り組んでいるのが、グルメサイトにランキングされない美味しい日本酒のお店探しです。ソーシャルメディアを分析した結果を、実際に皆で出かけては「確かめる」のですが、本当に有名ではないがすごいお店に行き着くのです。

いろいろ検索している中でこの紹介を見て、「これはエンジニアやデータ分析者として信頼できる」と思って本も買いました。さすがに紹介されている事例はそのまま適用できそうにありませんが、限られた精度のデータの中で、いかに実務に役立つ分析を行うのかというハックの仕方は勉強になります。

不動産格差(長嶋修)

@fds_infoで引っかかって気になって購入。

不動産コンサルタントの長嶋修さんの新刊で、今〜少し先の不動産の状況が概観できる本です。本の内容については以下のブログを参考にしてください。

1manken.hatenablog.com

特に印象に残った文章がこれです。ITエンジニアとしても、それぞれのドメインにおいて以下のような意見には耳を貸す必要があります。ビッグデータだのAIだの言われても、元になるデータが不十分では限界があるという話です。

日本で行われているこうした取り組み(←不動産テックのこと)には限界があります。というのは、日本で行う価格推定の根拠となるのは、国の成約価格情報を利用してはいるものの、全体の一部に過ぎず、主にインターネット上に出ている物件情報をロボットでクロールしてかき集めたものだからです。つまり、もともと不透明な価格情報を加工しているに過ぎません。(中略)

不動産総合データベースが本格稼働すれば、こうした課題も解消されます。データベースを利用できるのは、当初は宅建業者だけの予定ですが、国土交通省は民間への情報公開を見据えています。

不動産格差 (日経プレミアシリーズ)

不動産格差 (日経プレミアシリーズ)

お客さま、そのクレームにはお応えできません!(三浦展

これも同じく不動産ネタ。一応小説の体は取っているものの、不動産管理業者のあるあるネタをまとめた事例集みたいな感じのユニークで面白い本でした。

【書評】お客さま、そのクレームにはお応えできません!|不動産投資の健美家(けんびや)

テーマごとに一人の問題入居者が紹介されるのではない。それぞれに複数人、多い章(特にクレーマーたち)では数十人のトラブル事例がゾロゾロと出てくるのだから、驚く。現場のスタッフたちの苦労が偲ばれるというものだ。

また、本書には、不動産賃貸業の第一線で活躍するプロたちの頭の中や、トラブルを最小限で食い止めるためのノウハウを知ることができるという面白さもある。

ブロックチェーン入門(森川夢佑斗)

さすがにそろそろブロックチェーンを無視し続けることはできないなと思ってとりあえず本を読みました。

ブロックチェーン入門 (ベスト新書)

ブロックチェーン入門 (ベスト新書)

純粋関数型データ構造(Chris Okasaki)

関数型言語界隈やデータ構造界隈(どちらも怖いね!)で非常に評判が良い本です。

私は最近Haskellを読み書きできるようになり、「変数って全部イミュータブルでいいんだ」「Rubyの変数に全てfreezeして回る病」にかかってしまっていたのですが、少なくとも効率のいいデータ構造が必要だということは分かりました。

ところが、私は大学でもきちんといわゆる『アルゴリズムとデータ構造』の分野を学んだことが無いためか、逆にそちらの記述で詰まるところが多く、一旦この本を読むことを諦め、はてなの人が薦めてたCouseraのコースを勉強しています。

developer.hatenastaff.com

純粋関数型データ構造

純粋関数型データ構造

【Python】辞書のキーにデフォルト値をセットする

最近Python自然言語処理をしていて、複数のライブラリを利用していると、どうしてもリストや辞書のややこしい変換が増えてきます。

categories = ['サーバル', 'かばん', 'サーバル']
lines = [
    ['ここ', 'は', 'さばんな', 'ちほー'],
    ['食べ', 'ない', 'で', 'ください'],
    ['すっごーい!']
]

これを、キャラクターごとに利用している単語を集計したいと思います。具体的には、以下のような辞書に変換したいとします。

{
    'サーバル': ['ここ', 'は', 'さばんな', 'ちほー', 'すっごーい!'],
    'かばん': ['食べ', 'ない', 'で', 'ください']
}

Rubyであれば、nilガードを使って、サクッとハッシュの値を初期化すると思います。

# Ruby
categories.zip(lines).each_with_object({}) do |(c, l), hash|
  hash[c] ||= []
  hash[c].concat(l)
end

ところが、Pythonで同じことをやろうとすると、「キーが存在しないときに初期化する」という処理で、どうしても冗長になってしまいます。

result = {}
for c. l in zip(catagories, lines):
    if not c in result:
        result[c] = []
    result[c] += l

こんなときは、collections.defaultdictを使うと良さそうです。指定の型のデフォルト値(この場合は空のリスト)で初期化した値を辞書のキーに持たせることができます。

from collections import defaultdict

result = defaultdict(list)
for c, l in zip(catagories, lines):
    result[c] += l

厳密にはdict型ではないものの、defaultdictはdict型のサブクラスで、メソッドもほぼ共通しています。

参考:

8.3. collections — コンテナデータ型 — Python 3.6.1 ドキュメント

このような「オブジェクトの操作に向いているデータ型を使おう」といった感覚は、ケント・ベックSmalltalk本に詳しく書かれていました。

言語はSmalltalkですが、Pythonでもよく使われるSet型についての解説(値の重複チェックはオブジェクトにまかせてしまおう!)もあり、オブジェクトの操作の感覚をつかむのに勉強になりました。

ケント・ベックのSmalltalkベストプラクティス・パターン―シンプル・デザインへの宝石集

ケント・ベックのSmalltalkベストプラクティス・パターン―シンプル・デザインへの宝石集

  • 作者: ケントベック,Kent Beck,梅沢真史,皆川誠,小黒直樹,森島みどり
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2003/03
  • メディア: 単行本
  • 購入: 7人 クリック: 94回
  • この商品を含むブログ (55件) を見る

【Haskell】optparse-genericを使ってコマンドラインツールを作るまで

Haskellは優れた型システムによって見通しの良いプログラミングができるものの、アプリケーションを作る際にはどうしても敷居が高く感じてしまっていました。

というのも、PythonRubyなどのスクリプト言語では豊富なパッケージの組み合わせで小さなプログラムならサクッと作れてしまうことを考えると、自分にとって新しい言語をわざわざ使うメリットを考えてしまい、単なる教養やお勉強の領域だけにとどまっていました。

著名で使い勝手の良いライブラリを調べる

Haskellの"package archive"であるHackageには多数のパッケージが登録されているものの、この中のどれを使えばいいのか、なかなか候補が絞り込めずにいました。

翻ってPythonについて考えると、私はまずawesome-pythonリポジトリを参考にし、ここに自分の欲しい機能を見て(「コマンドライン引数をパースするライブラリが欲しいからcommand-line-toolsの項目を見よう!」)、紹介されている中から自分にとって使いやすそうなものを選びます(「clickがシンプルで良さそう」)。それで良い物がなければPyPIを直接検索します。

同様にawesom-haskellというリポジトリがあれば、そこから調べていけば助かります。実際にGithub上に2つ存在しました。

こちらのリポジトリでは1000件以上のスターが付いており、Pythonのものと同様、各項目に整理されています。

github.com

もう一つのほうは整理されていないものの、上記のリポジトリで紹介されていないパッケージもあります。例えばコマンドラインパーサーもいくつか紹介されています。

github.com

この中から、使い勝手の良さそうなoptparse-genericというパッケージを使ってみます。

github.com

stackを使って開発してみる

Haskellのビルドツールであるstackを利用して開発してみます。

stackが何かという話は、Rubyプログラマーは「Haskell Stack でライブラリを安定させる | Netsphere Laboratories」を読めば分かると思います。

基本的なコンセプトは Ruby のための Bundler と同じ。プロジェクトが直接必要とするライブラリと, さらに依存するライブラリについて、システムグローバルにインストールされたパッケージで不足する場合, プロジェクト内にインストールしてしまう。

新規プロジェクト作成

開発用のディレクトリで新規プロジェクトを作成します。

stack new haskell-cli

ディレクトリ構成はこんなのが出てきます。

$ cd haskell-cli; tree
.
├── LICENSE
├── README.md
├── Setup.hs
├── app
│   └── Main.hs
├── haskell-cli.cabal
├── src
│   └── Lib.hs
├── stack.yaml
└── test
    └── Spec.hs

3 directories, 8 files

依存ライブラリの追加

(プロジェクト名).cabalのファイルを編集します。本来は他の項目(ホームページのアドレス等)も変更する必要があるのですが、とりあえず動かすだけなのでこれだけで。

executable haskell-cli-exe
  hs-source-dirs:      app
  main-is:             Main.hs
  ghc-options:         -threaded -rtsopts -with-rtsopts=-N
  build-depends:       base
                     , haskell-cli
                     , optparse-generic -- この行を追加
  default-language:    Haskell2010

サンプルコードをapp/Main.hsに書き写します。

{-# LANGUAGE DeriveGeneric     #-}
{-# LANGUAGE OverloadedStrings #-}

import Options.Generic

data Example = Example { foo :: Int, bar :: Double } deriving (Generic, Show)

instance ParseRecord Example

main = do
    x <- getRecord "Test program"
    print (x :: Example)

ビルドして使ってみる

プロジェクトのディレクトリで実行すればビルドされます。

stack build

また、stack execコマンドでビルドしたものを使うことができます。

$ stack exec haskell-cli-exe -- --foo 1 --bar 2.5
Example {foo = 1, bar = 2.5}

ビルド先のディレクトリに移動すれば、直接実行することもできます。

$./haskell-cli-exe --foo 1 --bar 2.5
Example {foo = 1, bar = 2.5}

$ # 引数が足りないとエラーを出してくれる
$ ./haskell-cli-exe --foo 1 
Missing: --bar DOUBLE

Usage: haskell-cli-exe --foo INT --bar DOUBLE

さらに詳しく知りたい方は、以下の記事を読むと良いと思います。

qiita.com

最後に

おおまかな開発フローは確認できたので、サンプルコードではなく実際のコマンドラインツールを今後作りたいと思います。

こんなの作ろうと考えています。

【Haskell】vim上でHaskellの構文チェックを行う

今まで完全に教養としてHaskellを勉強していた(Pythonの型注釈に必要な感覚を養いたい、内部状態の少ないコードを書きたい)のですが、「この問題はHaskellなら上手く解けるんじゃないか」というものを思いついたので、初めて自分の頭で考えたコードをHaskellで書いています。

Haskellには強力な型システムがあるので間違ったコードを書きづらいのですが、少しコードを変えるたびにコンパイルを通すのはさすがに面倒です。そのため、普段利用しているエディター(vim)から静的解析ツールを呼び出せるように設定することにします。

こちらの記事で紹介されているhaskell-vim-nowでいろいろな開発ツールが導入できるようですが、私はエディターにいろいろ設定しても結局使いこなせないので、今後必要に応じて導入しようと思います。Pythonのプログラミングでもflake8と簡単な補完以外は使ってないので…。

qiita.com

というわけで今回は次の2項目を設定しようと思います。

特にhlintは命名規則やポイントフリースタイルの有無など、「Haskellらしくないコード」を検知してくれるようなので、勉強目的でも助かりそうです。

qiita.com

stackのインストー

Haskellの現在の事実的な標準のビルドツールであるstackをインストールします。stackについてざっくり知りたい方は以下の記事を読みましょう。

qiita.com

公式サイトにもある通り、UNIX系のOSであれば

curl -sSL https://get.haskellstack.org/ | sh

または

wget -qO- https://get.haskellstack.org/ | sh

でインストールできます。

Mac OS Xではbrewでもインストールできますが、公式サイト曰く「unofficial and lag slightly behind new Stack releases」とのことなので、私はcurlを使う方法でやりました。

brew install haskell-stack

念のため、現在インストールされるバージョンも記載しておきます。

$ stack --version
Version 1.4.0, Git revision e714f1dd3fade19496d91bd6a017e435a96a6bcd (4640 commits) x86_64 hpack-0.17.0

stackでghc-modをインストールする

こちらも公式サイトの手順に従います。会社のすごい先輩は事あるごとに「ネットの記事を参考にするのも良いが、基本的には公式サイトの手順に従え。場当たり的な対処はするな」と言っているので、皆さんも私の言うことは信用せず、以下のURLに目を通してください。

github.com

今回はプロジェクトごとではなく、グローバルな環境に入れてしまいたいので、Global installationの手順に従い、以下のコマンドをホームディレクトリで実行します。同時に、hlintもインストールしてしまいましょう。

stack install ghc-mod hlint

ghc-modの公式ページではcabalを使った手順が推奨されていますが、以下の記事で「stack ghcのバージョンとghc-modをビルドしたghcが食い違ってた」とき、うまく動作しないことがあるようです。

qiita.com

素直にパスを通します。stackを使ってインストールした場合は~/.local/binghc-modのバイナリが保存されているので、~/.bash_profileに以下を追記します。

export PATH=$PATH:~/.local/bin

vimの設定

ghc-modを利用したvimプラグインは、まずコード補完を目的とするneco-ghcが開発され、その他の機能(型の自動チェックとかLintとか)はghcmod-vimで提供されているようです。

eagletmt.hateblo.jp

私はPythonのflake8(文法チェック)のような機能を期待しているので、まずは基本的にhlintを利用し、より詳しい情報が欲しい場合にghcmod-vimも一応呼び出すようにしたいと思います。コード補完も欲しくなったらneco-ghcも検討します。

私はvimプラグイン管理ツールとして設定がシンプルだというvim-plugを利用しているので、こんな感じで記述していきます。

(ghcmod-vimvimprocに依存しているようです)

let g:syntastic_haskell_checkers = ["hlint"]

call plug#begin('~/.vim/plugged')
Plug 'scrooloose/syntastic'
Plug 'Shougo/vimproc', {'do' : 'make'}
Plug 'eagletmt/ghcmod-vim'
call plug#end()

詳しい利用方法は、vim-plugの公式サイトを読んでください。

使ってみる

Haskell で hlint を使用したコードチェック - C++でゲームプログラミング」のHaskellコードをvimで保存すると、hlintがコードの悪い部分と行を教えてくれます。

f:id:takeshi0406:20170514232251p:plain

また、:GhcModCheckコマンドを実行すると、ghcmod-vimコンパイラのエラーや警告を表示します。

f:id:takeshi0406:20170514232724p:plain

他にもいろいろできそうですが、とりあえずこれくらいで。

Haskellについて余談

ちょっとした余談ですが、もしインターネット上の資料でHaskellを学びたいという人はHaskell Day 2016チュートリアルから追うことをおすすめします。 他の情報源から追うと、古い情報があったり、Haskell経験者じゃないと難しい表現などが多く、情報の取捨選択が難しいと思います。

現在の事実的標準のビルドツールであるstackの説明なども詳しく、「ちょっと勉強したいだけなのに開発環境を整えるところで詰まってる」ような状況にはハマりにくくなると思います。

qiita.com

Haskellのコードを書く感覚をつかむには『すごいHaskellたのしく学ぼう!』がおすすめです。(その分、開発環境などの情報は古いです)

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

あと、こちらの本も「すごく分厚いけど、関数型言語を学ぶのに必要な感覚を丁寧に説明していて良かった」「すごいHaskellは、必要な概念の定義→利用例という説明が多くて『ちょっと待って!』と思うことが多かったけど、この本では無かった」ととある友だちから評判が良かったです(私はまだ読んでませんが…)。

Haskell 教養としての関数型プログラミング

Haskell 教養としての関数型プログラミング

表紙の「Haskellの美しさを知っている人は、人生に絶望することはない。Haskellで世界を変えたい。」という文言の威圧感がヤバいです。

また、日本HaskellユーザーグループのSlackも開放されています。私もROM専で登録してみましたが、Haskellの議論が日本語で読める貴重な場だと感じています。

haskell.jp

【アルゴリズム】検索エンジンで重要なトップnソートについてまとめておく

検索エンジンやレコメンドエンジンを昔実装していた先輩から、飲み会で

という話を聞きました。

ところが、私は低レイヤーの言語(CやC++)から逃げてPythonを始めたような人間なので、残念ながら「アルゴリズムとデータ構造」と呼ばれるような分野は全く詳しくありません。

しかし、社内には既に数学や機械学習・数理計画法の知識では敵わない人がいるため、私は生き延びるためには実装やアーキテクチャ(要するに数理モデルを「検索エンジン」として使えるようにする技術)を勉強しなければいけないと思っています。

という話はさておき、今後これらの分野を勉強するときのために、「トップnソート」関連の記事についてポインタを残しておこうと思います。

まずはこちらの記事。"top n sort"ではなく"top k-selection"と呼んでいますが、同じアルゴリズムだと思います。

qiita.com

プログラムを書くお仕事をしていると、いろんな場面で top-k selection をしなきゃいけない状況にちょくちょく出くわすことがあるかと思います。もちろん RDBMS を使っていれば、ORDER BY sort_column LIMIT k とすることでさくっと top-k selection が実現できるわけですが、RDBMS の外で top-k selection をしなきゃいけない状況だって (年に 2〜3 回もあるかは個人差がありますが)、人生の中で 1〜2 回は遭遇するんじゃないかと思います。

非常にわかります。私の場合、今のところ運良く「nが小さく、全部ソートしてしまっても遅くなかったケース」「一番大きなものだけ選ぶケース」にしか当たっていないので実装せずに済んでいるのですが。

こちらの記事のコメントで、言われている「mikioさんのページ」は、

本当は、mikioさんがかなり色々と実験をされていたので、そこにリンクが張れるとよかったんですが、ページが消えてるみたいで、見つかりませんでした……。

別の記事でも言及があったため、そのURLをインターネットアーカイブを探ると見つかりました。

開発メモ: トップNソートの検討

データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY timestamp DESC LIMIT 10" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。

こちらの記事では、実際にC++ヒープソートクイックソートを改造して実装しています。

なお、「レコメンドエンジンって、要するに検索エンジンの特殊なもの」ということは、以下の本の「Solrをレコメンドエンジンとして使う」という章でも書かれていました。検索エンジンの性能評価についても書かれていたのできちんとやればかなり勉強になりそうです。

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

本当は、業務でElastic Searchを使うような案件ができれば良いのですが、今のところそんな機会は無さそうです。仕方ないのでプライベートでAWS Lambdaを使ってクローラーを作り、まずは検索サービスを作るためのデータを集めようと画策しています。