読者です 読者をやめる 読者になる 読者になる

sasau’s diary

作ったもので2年に一回くらいの更新を目指す

fastTextのベクトルの類似検索でYAHOOのNGTを使う。

fasttextにWikipedia全文を食べさせて遊んでいた(だいたい以下の記事の内容)。

qiita.com

「パリ - フランス + 日本」とかそういうやつ(だいたい以下の記事の内容)。

antibayesian.hateblo.jp

1 0.044094 -0.020766 -0.043709 -0.28123 0.13417 0.1673 0.05862 0.22077 -0.12497 0.077398 -0.022736  ...
2 0.1059 -0.050905 -0.10932 -0.22583 0.15278 0.15993 0.034985 0.12569 -0.10522 0.09798 -0.026379  ...
3 0.010506 -0.23203 -0.083458 -0.26819 0.14723 0.2554 -0.032926 0.029112 -0.24196 0.063793 ...
...

↑ fasttextで学習させるとこういうファイルが吐かれる。
最初の整数が単語に割り振ったトークンでそれからfloatが次元数分、ここでは300個並んでいる。
それが約92万行。学習はCPUで2時間くらいで終わる。
92万もあるとファイルサイズが2GBくらいになるのでパソコンでは全力で並列化とかしても読み込みに1分くらいかかってしまう。
さらに、対象のベクトルと全件の類似度を計算するみたいなことをやるのでパソコンでは全力で並列化しても1分くらいかかってしまう。

これだと気軽に使えないし、例によってslack botにするなどしたいのでさくらのVPSの安いやつでも数秒で計算が終わって欲しい。
たぶんアプローチとしては、読み込みも類似計算もこのベクトル空間内で近しいものだけ行うようにインデックス化すればいいんだと思うけど
それは大変だなーとか思ってググっているとすごいツールがあった。

NGT(Neighborhood Graph and Tree)

NGT

簡単にいうとfastextが吐いたような1行に1ベクトルみたいなファイルをインデックス化して、それを使って高速に空間内の距離の検索をしてくれるコマンドラインツール。

インストールは書いてある通りにやれば簡単に出来ると思う。 注意点としては

  • ubuntu, centosなどのLinuxでは動いたけどMacではインストールはできてもコマンド引数が認識されないみたいなエラーが出て動かなかった。
  • githubから最新版をクローンしてくると動かなかったのでおとなしくタグが打ってあるやつを使うといい。

前処理

最初にNGTにベクトル放り込んでインデックス化してもらう。
そのためにfasttextが吐いたやつの下処理をする。

import numpy as np


def sorted_vectors(vec_path):
    vec_file = open(vec_path)
    # 最初の行はヘッダなので捨てる
    vec_file.readline()

    rows = []
    for token, vec in (row.strip().split(maxsplit=1) for row in vec_file):
        # なぜかトークンではないものが混じることがある。
        try:
            rows.append((int(token), vec))
        except ValueError:
            continue

    # 行数とトークンが揃っててほしいので、トークンでソートする。
    rows.sort(key=lambda x: x[0])
    # 1からの連番になることを確認
    for idx, row in enumerate(rows, 1):
        assert idx == row[0]
    yield from (row[1] for row in rows)


def prepare_for_ngt(vec_path, dist_vec):
    dist = open(dist_vec, 'w')
    for row in sorted_vectors(vec_path):
        vec = np.array(row.split(), dtype='float32')
        # ノルムで割ってベクトルを正規化。
        vec /= np.linalg.norm(vec)
        row = list(vec)
        row = ' '.join(map(str, row))
        dist.write('{}\n'.format(row))

正規化をしているのは結果をコサイン類似度と揃えたかったから。 techblog.yahoo.co.jp

NGTは距離しか扱えないため、コサイン類似度と同じ検索結果を得るために事前にベクトルのノルムが1となるように正規化してユークリッド距離を使う方法か、

距離関数はcreateの引数で選択できる。
デフォルトだとユークリッド距離。

これにfasttextが吐いたファイルを与えると1行に1つのベクトルで、トークンでソートされているファイルが出来上がる。

prepare_for_ngt('model.vec', 'ngt_model.vec')

そして以下のコマンドを叩く。
-dは次元数,indexは出力されるディレクトリ名。
$ ngt create -d 300 index ngt_model.vec
詳しいオプションは→https://research-lab.yahoo.co.jp/software/ngt/command.html#create
この所用時間はコア数に応じて数十分~1時間くらい。
もちろん出力されたものは使いまわせる。

検索

$ ngt search index target.vec
taget.vecは検索したいベクトルのファイルで、形式はcreateに使ったファイルと同じ。

Query No.1
Rank    ID  Distance
  1    野球    0
  2    ソフトボール    0.682129
  3    プロ野球    0.708267
  4    サッカー    0.739252
  5    軟式野球    0.754248
  6    少年野球    0.755179
  7    バスケットボール    0.765375
  8    高校野球    0.788223
  9    リトルリーグ    0.788254
  10   アマチュア野球    0.794894
  11   アメリカンフットボール    0.799319
  12   ホッケー    0.805228
  13   ベースボール    0.822246
  14   ラグビー    0.822764
  15   アメフト    0.823869
  16   硬式野球    0.832693
  17   バスケ    0.834052
  18   大学野球    0.835599
  19   卓球    0.835896
  20   投手    0.836089

結果がこういう形で表示される(本当に正しいかわかりづらかったのでトークンを単語に変換している)。
indexに放り込んだベクトルから近い順に返ってくる。
さくらのVPSの下から2番目のやつでも3秒くらいで返ってくる。

まとめ

このツールは、界隈では自分が紹介するまでもなく有名で、かつ使われているのかもしれないけれどリリースが結構前な割には(商用利用出来るようになったのは去年だけど)そんなに情報が多くなかったので、ただ使ってみただけだけれども書いてみた。
多次元ベクトルのインデックス化は明らかに僕のできる範囲を超えているので感動してしまった。ごちそうさまです。

あと一応試せるように使用したモデルデータを置いておきます。
これは冒頭のqiitaの記事の過程で得られるものだけど。
model.vec.gz - Google ドライブ
wiki__all.vocab.gz - Google ドライブ

おわり

指定した聖書の箇所を読み上げるslack bot

この記事はSlack Advent Calendar 2016 - Qiita の 20 日目です。

文字どおり私事なのですが、privateなslack teamを利用しています。その中でタイトルのようなbotを稼働させていまして、いわゆるアドベントカレンダーに合っているな、と思ったので、紹介をしたいと思います。

はじめに

聖書は旧約聖書新約聖書があり、それらはいくつかの書物から成り立っています。
さらに本文中には章番号と節番号が振られており、聖書の箇所を指定するときは
[新|旧]約聖書, 書物の名前, 章の数字, 節の数字
という形式で行います。(慣れている人は書物の名前で新旧はわかるので省略することも多いです)
例:
旧約聖書 創世記1章1節


聖書の参照を簡単にしたいというのはモチベーションとしてあったのですが
日本聖書協会のWebサイトにて聖書の本文を検索出来るフォームが公開されていて、これに前述の内容を入れることで目当ての聖書の箇所の本文を閲覧することができます。
こういうフォームへの入力をSlackを使って対話形式にできたらいいな、と考えて作りました。

実装

Python3で書いています。*1

本文検索を行うコードはgistにあります。
bible_search.py · GitHub

これを、

from random import choice
from bible_search import SearchQuery, BibleSearch


def bible_search_sequence(text):
    query = SearchQuery(text)
    if not query.ready:
        yield '聖書の箇所がよくわからないな。ごめんね。'
        return

    sections_text = ''
    if query.section_from:
        if query.to_end_of_section:
            sections_text = ' {}節から終わりまで'.format(query.section_from)
        elif query.section_to:
            sections_text = ' {}節から{}節'.format(query.section_from, query.section_to)
        else:
            sections_text = ' {}節'.format(query.section_from)

    yield '`{}、{}の{}章{}`だね。{}'.format(
        query.bible_name,
        query.book_name,
        query.chapter,
        sections_text,
        choice([
            'うん、頑張るね。',
            '{}、どんな箇所だろう。'.format(query.book_name),
            'ふふ。聖書読むの大好き。',
            '聖書を持ってくるからちょっと待ってね。',
            'ええと、その箇所は...。',
            'わかった。任せてよ。'])
    )

    bible_text = BibleSearch.search(query).text()
    if bible_text:
        yield '```{}```'.format(bible_text)
    else:
        yield 'あれ?その箇所はないみたい。'

こんな感じに使って返答を作っています。

bot: bibledog

そして稼働しているbotbibledogです。こんな感じに喋ってくれます。

f:id:ssuwam:20161213151153p:plain

f:id:ssuwam:20161213152345p:plain

  • botがjoinしているchannelに投稿された「読んで|よんで」に反応して、その聖書の箇所をpostしてくれる。
  • 書物の名前は省略にもだいたい対応、読み上げる箇所は1節から最大1章まで。

終わりに

メッセージという一つのUIでやりとり出来るのは便利で楽しいですね。
また普段、聖書を開いている時に複数の箇所を見たい時は、聖書についている紐を使ったり、しおりや指を挟んでおいたりしますが、タイムラインに並べて表示できるのは捗ります。
他には源氏物語など、章節が振られている書物などは同じようにやってみると面白いかもしれません。
最後に、アドベントカレンダーということなので、少し長いですがクリスマスの箇所、特にページェントでよく参照される箇所を読んでもらいたいと思います。

ルカによる福音書 2章1節から20節を読んで。

f:id:ssuwam:20161213153719p:plain

それではよいクリスマスを。

謝辞

引用している聖書の日本語訳は新共同訳です。
(c)共同訳聖書実行委員会 Executive Committee of The Common Bible Translation (c)日本聖書協会 Japan Bible Society , Tokyo 1987,1988

*1:言及していませんがPythonによるSlack APIのインターフェース実装には github.com を使用しています。

因縁サーチ

久々にプロ野球因縁サーチの中身を更新した。

今永昇太 | プロ野球因縁サーチ
↑今季新入団の投手。

中身はhttp://ja.dbpedia.org/sparqlからダンプしたデータを弄ってJSONにしてそれをオンメモリで展開しているだけなのだけど。
こんな感じで1日300人?くらいは見ている人がいるようなので、野球が好きな人の間で少しは楽しんでもらったりしているんだろう。
f:id:ssuwam:20161011192423p:plain

あんまりエゴサする習慣はないんだけど何年も前なので思い出として置いとく。

野球選手の経歴とか世代とか簡単に調べられるツール
↑自分が立てたスレ

野球選手の経歴とか世代とか簡単に調べられるツール:非常識@なんJ
↑をまとめたまとめブログ

【やじうまWatch】ファン垂涎、プロ野球選手同士の経歴のつながりを検索できる異色サイトが登場 - INTERNET Watch Watch
↑をまとめたやじうまWatch
ブクマはこっち→ http://b.hatena.ne.jp/entry/internet.watch.impress.co.jp/docs/yajiuma/20131025_620919.html


そうそうhttp://ja.dbpedia.org/sparqlから
日本の野球選手の出身高校を列挙するクエリの例 - Qiita こういう感じのSPARQLでデータを取ってきてるんだけど
更新しようとしたら

?person dcterms:subject <http://ja.dbpedia.org/page/日本のプロ野球選手一覧> .

このクエリの結果が空になっていてちょっと困った。
これを作った時はいわゆるカテゴリページは述語dcterms:subjectを使ってその一員のリソースを記述していたんだけど今は違うらしい。
これは、dbp-owl:wikiPageWikiLinkを使うとうまくいく。
dbp-owl:wikiPageWikiLinkを使ったクエリの結果は、そのままだと要はwikipediaのページ内リンクされているもの全てなのでとても雑多になるけど
例えば右側(カテゴリ)が変数になる場合、DBPediaではカテゴリページはskos:Conceptというものに分類されているので

?category rdf:type skos:Concept .

とすれば、?categoryバインドされていて、その中でカテゴリページでないものをフィルタすることができる。
...RDFの世界は、リソースにrdf:typeで「それが何であるか」がはっきりわかるのはすごい魅力だなあと思う。

最適化系の問題を解いてみる。

自分はPython第一言語なので https://checkio.org/ でよく遊ぶ。
自分のプログラム力はお世辞にも高いとは言えないようなレベルだと思うけど
そもそも普段の仕事はUIKitとかReactとかのフレームワークやライブラリと仲良くすることであってあまり自分でアルゴリズムとかを考えたりしないし
それに胡座を書き続けてきた結果CodeIQ(の簡単なやつ)は解けるがPaizaは全くワカランみたいな状況になって死にたくなったりするのでまあ似たような思いをしている人がいることを信じて出来なかった問題を解くまでを書いてみたいと思う。

自分がこういうプログラミングクイズみたいな問題に取り組むと

  • FizzBuzzに毛が生えたようなやつ→解ける
  • FizzBuzzに手足が生えたようなやつ→頑張れば
  • 経路探索くらいのやつ→ググりながらやればなんとか
  • 最適化→ググってもわからん

みたいな感じになる。

この先も似たようなことはあるとは思うけどその都度こんな感じでクリアしていきたい、と思う。 前置き終わり。

問題: Break Rings

https://checkio.org/mission/break-rings/

問題は

  • 繋がりあった複数のリングがある。
  • リングには番号が振られている。
  • 何回かリングを破壊してバラバラに(全てのリングがどれとも繋がっていない状態)にしたい。
  • 破壊する回数で一番少なく済むものを求める。

f:id:ssuwam:20160606204816p:plain

入力として 整数のsetのtupleが与えられる。これは対応するリングとリングの繋がりを示す。

input_value = ({1,2},{2,3},{3,4},{4,5},{4,6},{6,5})

出力はリングを破壊する回数。
↑の画像は3つ壊せばバラバラになる。

break_rings(input_value) == 3

考えたこと

つながっているリングが多いもの優先して壊せばそれが一番回数が少なくなるのでは?

やってみた。結論から言うとダメだった。

from collections import Counter

def break_rings(rings):
    break_count = 0
    while True:
        counter = Counter()
        for ring in rings:
            # 二個揃っていないものは除外
            if len(ring) != 2:
                continue
            l, r = ring
            counter[l] += 1
            counter[r] += 1
        # 二個揃うものがない(=バラバラ)
        if len(counter) == 0:
            break
        common, _ = counter.most_common(1)[0]
        break_count += 1
        for ring in rings:
            if common in ring:
                ring.remove(common)
    return break_count

f:id:ssuwam:20160606204951p:plainf:id:ssuwam:20160606204956p:plainf:id:ssuwam:20160606204959p:plain おおう...このくらい絡まり合ってるとどの手順で破壊すれば回答に辿り着けるのか手作業じゃ分からん。
これは8個目のテストなので途中までは、まあ...。
そもそも最適化問題ってFizzBuzzみたいな明瞭な答えがあるのか分からないな…。

続・考えたこと

更に眺めていると、この問題は入力を単なる「ペアの集合」と考えれば良くて
ペアのどちらかに該当する数字で、全てのペアを網羅するリングの数字を列挙すれば良いのでは?というように見えてきた。
うまく説明できないけど... 例えば入力が

input_value = ({1, 2}, {2, 3}, {3, 4})

だったら(2, 4) or (2, 3) or (1, 3)で網羅できる。
明瞭なアルゴリズムはあるのかも知れないが自分には思いつかないので、全パターンを試してみることにする。

from itertools import permutations


def break_rings(rings):
    ring_numbers = set()
    # 登場するリングを集める
    for l, r in rings:
        ring_numbers.add(l)
        ring_numbers.add(r)

    break_count = len(ring_numbers) - 1
    # 壊すリングの順番を生成
    for break_rings in permutations(ring_numbers):
        filtered_rings = rings
        for count, ring in enumerate(break_rings, 1):
            # ペアのどちらかに含まれるものを除外していく
            filtered_rings = [r for r in filtered_rings if ring not in r]
            # break_countを超えてしまったら以降の検証は打ち切る。
            if count > break_count:
                continue

            # 全てのリングを網羅した。
            if not filtered_rings:
                break_count = count
                continue
    return break_count

オーダー数は、リングの数の順列の数…か? 時間は掛かるが失敗のケースは通ってくれる。

最適化

checkio.orgの検証がまるで終わらないので最適化を考えてみる。
そもそも個数しか求められていないので、全パターン網羅する必要はない。
そして、壊す順番も実は関係ない。
なので、 繰り返しを許さない組合せでいいし、検証は、短いものから始めて成功したら終了で良い。

from itertools import combinations

def break_rings(rings):
    ring_numbers = set()
    # 登場するリングを集める
    for l, r in rings:
        ring_numbers.add(l)
        ring_numbers.add(r)

    for break_count in range(1, len(ring_numbers)):
        # 壊すリングを生成
        for break_rings in combinations(ring_numbers, break_count):
            filtered_rings = rings
            for count, ring in enumerate(break_rings, 1):
                # ペアのどちらかに含まれるものを除外していく
                filtered_rings = [r for r in filtered_rings if ring not in r]
                # 全てのリングを網羅できた
                if not filtered_rings:
                    return break_count

手元のケースでは一瞬で終わるがどうか。 f:id:ssuwam:20160606205400p:plain もっと良い答えはいくらでもあるのかもしれないが、ひとまず。

他の人の解答を見る前の感想

やる前は、知ってるか知らないかで終わるような解答があるのではみたいな甘えた考えがあったが、まあ、ないよな...。
あと(まるで自分が本当に壊すかのように)ストーリーに引っ張られると良くなくて壊す順番とかが大事なんじゃないかみたいな本質的じゃない部分に目が行きがちだった。
入力見て欲しい出力を考えて、それをどうやれば導けるかを考えてどういう性質があるか考える。
書いてみると当たり前なんだけど…。

他の人の解答を見た後の感想

一位の得票(イケてるコードの人に投票する仕組みがある)の人は同じcombinationsで組んでいて、product(積集合)の人も多そうだった。コード自体がイケてるかは別にして、とりあえずこんなもんか…。
次も頑張ろう。

try! Swiftに参加していた。

短いインターバルで内容を咀嚼していくのはなかなかハードだったけど、内容がそれぞれ極まっていた。

同時通訳のレシーバーが足らないという話が気掛かりだったけど戻っていたようで、よかった。

とりあえず、個々のテクニックは別にして今回感じたことは大きく2つ

Swiftのプログラミングスタイル

Objective-Cは、誰が書いても同じようなコードになる。
Objective-Cnilへのメソッド呼び出しが無視されたり
評価するとデフォルト値を返すなどして、簡単にヌルポを吐かない代わりに独特の意訳をする言語だ。
標準のNSArrayや、NSDictionaryに値を詰めると型が消えるという仕様、ダイナミックなメソッド呼び出しは完全に動的言語のそれで、主な使命がFoundationやUIKitのAPIの利用ということを差し引いても`There's Only One Way To Do It`だ。

Swiftはどうか、というとSwift2からProtocol Oriented Programingが提唱されており、メタプログラミングが追加されRxをはじめとしたFunctionalなプログラミングスタイルが既に人気を集めている。
そして、恐ろしいことにそれらは日々増え続ける状態の管理を幾分か、簡明にする優れた答えの一つでもある。
まあだいたい、言いたいことはakisuteさんが仰っておられた通り。 

try! Swift SwiftらしいTable View Controllerの使い方

try! Swift Protocol-Oriented Programming in Networking

try! Swift パーサーコンビネーター in Swift

自分も見習ってキラッキラしたSwiftコードを書きてえと思う一方で、エクストリームな世界に対しては、身構えるところもある...。

Swift Package Managerとswiftenv

今回は基本的にiOSに向けたセッションだったが

try! Swift Swiftでサーバを書いてみよう #tryswiftconf Day3-2 - niwatakoのはてなブログ

try! Swift ライブラリの開発 #tryswiftconf Day2-8 - niwatakoのはてなブログ

 はLinux環境での利用について言及していた。

これらは今後一年で主流になっていくと思われるので、試す。(cocoapodsはコマンド一発で使える、cartageもビルドの速さなど、過去の資産も含め一日の長があるのでそれなりに使われていくと思う)
来年は上から下まで全部swiftで書いたとかraspi動かしたみたいなセッションが出るんだろうか。

Party

英語使えないのにお酒を飲んで外国の参加者の方に意味不明な絡みをしてしまった。

とても申し訳ない、勉強させていただきます。

棚上げテキスト 1.0.0

自分用のメモアプリをリリースした

棚上げテキスト

棚上げテキスト

  • Fumiya Kubota
  • Productivity
  • Free

どんなアプリか

棚上げ機能が付いている機能に乏しいメモアプリ。

棚上げ機能

編集中のテキストにリンクの定型文を登録して埋め込むことができる。
棚上げした文は、リンクをタップした先で後から変えることと
それについてのdescriptionを書くことができる。

f:id:ssuwam:20160109105820p:plain  f:id:ssuwam:20160109110033p:plain

何を目指したのか

考えをまとめようとしている時「まだ決まっていない概念」が思考の邪魔をすることが自分はよくある。
ただ、それをまとめるためだけに別のメモを作るなどするとたぶん一番重要な全体の流れからは遠ざかってしまう。
全体の流れを考える上で障害となるものを全て棚上げして、今考えていることの最後まで辿り着くことの助けとなるようなメモアプリを目指して作った。

なんで作ったのか

理由1

灯台下暗しというか

「そらそうよ」のフリック入力は気持ちいい [転載禁止]©2ch.net

http://orpheus.2ch.net/test/read.cgi/livejupiter/1431911650/l50

最近こういうスレが立つことが多くてハッとしたんだけど
片手の入力方式としてのフリック入力は暫定最強(日本語限定だし他は英語環境くらいしか知らないが)だと気付かされたので
もう少し片手間のアウトプットとして使っていきたいと思った。
何か作れば、自分くらいは使うだろうと。

理由2

RPGツクールMV発売に向けてそれに役に立つようなやつが欲しかった。
試しにライトノベルのあらすじだけ書いてみたらそこそこ便利だった。

作ってみてどうだったか

  • 仕事で使うには割と慎重派なんだけど、まあ単純すぎるアプリだしrealm便利だった。アプリの知能指数があがった。
  • 「棚上げ」は棚上げした名前というか気分的には「棚上げ(仮)」みたいな感じなんだけど最後まで思い浮かばないまま出てしまった。

TODO:

  • 棚上げ画面のUI改善
  • エクスポート
  • フォルダ分け(棚上げした定型文の名前空間的なものが欲しい)