みどりねこ日記

よくわからないけど、頑張りますよ。

未踏事業に出した提案が不採択となったので資料を公開します

大学院時代の友人である森下くんと一緒に未踏事業に出した提案が不採択となりました。 私は今年25歳になり、来年以降は未踏事業の年齢制限に引っかかってしまうため、今回が未踏クリエータになる最後の機会でした。 そして残念ながらそれを活かすことができませんでした。

申請書、二次審査の発表資料及びPMからいただいた不採択理由を公開します。 不採択とはなりましたが、以下に公開する資料が今後未踏事業への提案を考えている方の参考になれば幸いです。 ちなみに形式は年によって結構異なるようです。あくまで参考にどうぞ。

一次審査

https://drive.google.com/file/d/0B9q5iVCNpwDlT2V2dHhJdGJHdEE/view?usp=sharing

二次審査

https://drive.google.com/open?id=0B9q5iVCNpwDla2pVUU9yZjk4MnM

不採択理由(PMのコメント)

技術的に特に新しいところや難しいところはなく、むしろ広くユーザを獲得して大きなトレンドにすることに一番の課題があるように思われました。つまり、この種のプロジェクトの最大の課題はユーザのインセンティブの確保の戦略です。これが現時点では、ブラウザプラグインという(ひょっとして気がつかないうちに実装されている)仕掛けのみだと思われました。それでも、ネットワーク帯域幅とディスク容量を食われるので、P2Pの好きな人でも、アーカイブというテーマでは導入を逡巡すると思われます。 むしろ、The Internet Archiveのようなものを非集中・分散で構築できるソフトウェアを開発して、有志なり大学なりがサーバ上で運営する、というシナリオならよかったかもしれません。 それよりもすべてのPMが感じた不安が、就職したばかりで必要な時間が本当に取れるのだろうかということでした。提案のときには、就職先と事前のネゴはしっかりしておいてほしかったですね。

スケジュール

申請書の締め切り(一次審査)は3/3でした。

一次審査の通過及び二次審査に関する連絡が来たのは4/3です。

二次審査は4/16に行われ、不採択通知が来たのは5/28でした。

ちなみに一次審査の倍率は3.3倍だったそうです。

所感

未踏事業には憧れがあったので、不採択となったことは本当に残念です。

提案したプロジェクトに関してPMから貴重な意見をいただきましたが、前半部分に関してはおっしゃる通りで、もっと良い方法もあっただろうと考えています。 しかし後半の「サーバで運用」という話に関しては、あまり同意できません。 もちろんサーバを補助的に使っていくというのは考えておりましたが、大学機関などのサーバに頼ることを前提にしたアーキテクチャでは我々の解決したい問題の根本的な部分は解決しません。 そういった面で我々のしたいこととは方向性が異なると感じています。

私はインターネットの利用者がPure Peer-to-Peerでアーカイブ及びCDNを行い、 互いのために少しずつ負担を負うことに意味があると思っているし、 面白いと思っているので、また別の機会にいつか実装するかもしれません。

私も森下くんも今年から社会人であり、 またどちらも4/16の二次審査の段階で所属する会社と兼業について交渉中であったことは大きな敗因だと考えています。 しかしやれることはやっていたので、これ以上どうしようもなかったと思っています。

森下くんは本当によく頑張ってくれました。ありがとう。

ただやはり悔しいですね。

謝辞

ご協力いただいた方々にお礼を申し上げます。

特にXcoo, Inc.の西村さん、青木さん、 及びUhuru Technical Rockstarsの部谷さんに感謝します。 過去に採択された際の申請書を送っていただいたり、貴重なアドバイスをいただきました。

応援していただいた、所属する会社の上司及び同僚に感謝します。

全然関係ないけど

Xcoo, Inc.は人材募集中です。

追記

未踏アドバンスド事業があるので「今回が未踏クリエータになる最後の機会でした」という書き方は不正確ではないかという旨のコメントをいくつか頂いたのでご回答させていただきます。

未踏アドバンスドは技術より事業化を目的とされているように見受けられました。 事業化は大事なステップであることは理解しているつもりですが、収益は見込めなくても人々の生活を変えられるようなプロジェクトもサポートしてくれる未踏事業に対して憧れがあったためにこのように書いています。

Pythonを呼べるLispを作った話

この記事はLisp Advent Calendar 2016 5日目の記事です。

Futhonとは

Futhonとは、Pythonが呼べるLispである。 先日作ってみた。 読み方は「ふとん」である。

本記事は、Futhonの内部実装がどうなっているかを簡単に説明する。 すごく小さな実装(ソースコードすべて含んで500行くらい)なので、この記事とコードを合わせて読めば誰でもちょっとしたおもちゃ言語が作れるようになるんじゃないかと思う。

作った動機

最近周りで機械学習がアツい。

Pythonディープラーニング機械学習ライブラリが充実していて、モデルを簡単に作ったり試したりすることができる素晴らしい環境になっている。

一方で、Lispニューラルネットを組もうと思ってもライブラリがなかったり、あってもドキュメントが少なかったりしたのでどうしたものかと悩んでいた。

そこで、ClojureJavaのリソースを利用できるように、Pythonのライブラリを自在に呼び出せるLispを実装して解決しようという考えに至った。 その結果完成した言語がこちらのFuthon言語。 Clojureにはcore.matrixとかあるから自分でそういうライブラリ実装すればいいじゃないかという意見は聞こえない。たぶん言語実装したほうがコスト小さい…。

実装の方針

Pythonのライブラリを自作言語から呼ぶ方法はいくつかある。 そのうちで検討したのは以下の3つである。

まず一つ目は実装がしんどそうな割にあまりメリットもなく思われたので候補から外した。そもそもC++について詳しくないので難航するのは目に見えていた。 二つ目が最有力候補だったけれどREPLの実装の仕方がわからなかったために断念。 というのは、REPLを実装するには順に入力された式を評価しながら何らかの方法でPython側の環境を管理する必要があるが、その仕方が思いつかなかった。 実はPythonにはcode.InteractiveConsoleというクラスが用意されていて、これの継承クラスを書いてやれば簡単にできることをあとあと知った。 結局、最後のメタプログラミングをする方法が実装に手間も時間もかからなさそうだったのでこれを採用した。

実装の大まかな流れ

大きく分けると、インタプリタはだいたい以下の要素で構成されている。

  • トークナイザ
  • パーザ
  • 評価器
  • プリンタ

トークナイザとパーザは、ライブラリによっては一緒に行われる場合もある。 これらを順に実装していくことになる。ここでもその順番に説明していく。

データ型と文法

最初にプログラミング言語のデータ型と構文を決める。 Futhonには以下のデータ型をプリミティブとして持たせることにした。

  • Vector
  • Set
  • HashMap
  • Symbol
  • Keyword
  • Lambda

以下がBNFで表記した文法。

program ::= sexpr

sexpr ::= atom | sequence | quoted

atom ::= string | regex_string | symbol
sequence ::= vector | list | hashmap | set

quoted ::= '\'' sexpr

symbol ::= '[_@\w.\-><\+\-\*\/\?!:=]+'
string ::= '".*?(?<!\\)(\\\\)*?"'
regex_string ::= '\#' string

vector ::= '\[' sexpr* '\]'
list ::= '\(' sexpr* '\)'
hashmap ::= '{' (sexpr sexpr)* '}'
set: '\#{' sexpr* '}'

Futhonプリミティブであるデータ型はFuthonObjectを継承するクラスとして実装する。 そうすると独自の型なのかPython側のオブジェクトなのかがisinstance(x, FuthonObject)するだけで判別できる。 ついでに__repr__のように、あったら便利かもみたいなメソッドをデータ型ごとに追加していく。 これらの詳しい定義はdatatypes.pyを参照のこと。

class Symbol(FuthonObject):
    def __init__(self, name):
        self.name = name
        
    def __repr__(self):
        return self.name

    def __hash__(self):
        return hash(self.name)

    def __eq__(self, other):
        return isinstance(other, Symbol) and self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(self, other)

文法

トークナイザ・パーザ

ソースコードからいきなり実行しようとすると、実装が難しい。 なので、ソースコードからトークンを切り出したり、木構造を生成して後に続く処理を楽にする。 これをするのがトークナイザとパーザ。 パーザの生成にはPlyPlusというパーザジェネレータを使う。 ドキュメントはあまりないがサンプルはあり、BNF表記でLRパーザが生成される点が素敵。 このライブラリを使えばトークナイザを作る必要もないので「とりあえずパーズしたい」という場合には便利だと思う。

start: sexpr;

@sexpr: atom | sequence | quoted;

@atom: string | regex_string | symbol;
@sequence: vector | list | hashmap | set;

quoted: '\'' sexpr;

symbol: '[_@\w.\-><\+\-\*\/\?!:=]+';
string: '".*?(?<!\\)(\\\\)*?"';
regex_string: '\#' string;

vector: '\[' sexpr* '\]';
list: '\(' sexpr* '\)';
hashmap: '{' (sexpr sexpr)* '}';
set: '\#{' sexpr* '}';

WS: '[ \t\n,]+' (%ignore) (%newline);

あとは生成されたLRパーザを呼び出してやって、それぞれ対応するデータ型に変換してやればパージングは終わり。 この辺の実装はfuthon_parser.pyに書かれている。

評価器

式の評価

大抵のプログラミング言語のパーズ結果は抽象構文木である。これはもちろんFuthonでも同様。 そういうわけで、得られた木構造をゴリゴリ評価していく。 Futhonは変数を持つ言語なので、評価する際には変数と値の対応を管理する環境という機構が必要になる。 さらにFuthonからPythonのメソッドなどを呼び出せるようにしたいのでPythonメタプログラミングが必要になる。

環境

環境は変数と値を対応づけるための構造。 Futhonの環境は階層的な構造を持っており、そうすることで変数の局所的な定義などができるようになる。 例えばFuthonでは定義された関数は新しい環境を持つことになるが、同時に生成された時点の環境を上位に持つことで、その時点での環境を関数内から参照できるようになる。

コード上の実装としては上の環境へのリンクを持つ、変数からFuthonObjectへのdict型という感じ。 environment.pyを読めばだいたいわかるはず。

Pythonメタプログラミング

FuthonではPythonのメソッド呼び出しやクラス生成を実行時に行いたいので、これらを実現する方法がホスト言語側に求められる。 幸いPythonにはいくつかそういったものが用意されていて、例えばgetattrを使えばPythonでクラスやメソッドをロードしたり呼び出したりできる。 getattrPythonの組み込み関数で、引数としてPythonのオブジェクトと属性名をあらわす文字列の二つを取り、そのオブジェクトの属性を返す。

class Hello():
    def __init__(self):
        self.hello = "nice to meet you!"

    def greeting(self):
        return self.hello

hi = Hello()
getattr(hi, "hello")
# => "nice to meet you!"
getattr(hi, "greeting")
# => <bound method Hello.greetings of <__main__.Hello object at 0x7febcaf46470>>

getattrで得られたオブジェクトがメソッドなのかはinspect.ismethod()で判別できる。 ただしこれだけではBuilt-in functionなのかどうかまでは分からないので、isinstance(o, types.BuiltinFunctionType)などでチェックする必要がある。 Futhonではメソッド呼び出しと一部のBuilt-in functionのみをサポートしている。

モジュールをインポートする場合はimportlib.import_moduleにモジュール名を渡してやればモジュールオブジェクトが返ってくる。

importlib.import_module("numpy")
# => <module 'numpy' from '/home/delihiros/.pyenv/versions/3.5-dev/lib/python3.5/site-packages/numpy/__init__.py'>

このへんのコードはdynamic.pyにまとめた。

こういうちょっとメタ的な仕様は他にも色々あって、例えばBuilt-in functionであるtypeに3つ引数を与えるとPythonのクラスを新しく生成できたりする。 興味ある人は公式ドキュメントを読んでほしい。 今回は後述する事情により途中で飽きた必要そうでもなかったので取り入れなかった。

以上で評価をするための部品はできた。

評価を行う

あとは実際に抽象構文木の評価を行う。 基本的には抽象構文木の根から葉に向かって深さ優先探索で評価をしていく。 このとき、与えられたノードの型によって評価の仕方を分ける。 例えばFuthonObjectではなくPython側のオブジェクトだったら、そのまま返す。Symbolだったら環境から対応する値を見つけてきて返す、など。 ただし、リストの場合はFuthonの式の可能性があるので特別な評価を行う。 これらの処理はevaluator.pyにある。

def eval(self, expr, env):
    if not datatypes.isFuthonObj(expr):
        if isinstance(expr, list):
            return self.eval_list(expr, env)
        return expr
    elif datatypes.isSymbol(expr):
        return env.get(expr)
    elif datatypes.isKeyword(expr):
        return expr
    elif datatypes.isVector(expr):
        return datatypes.Vector([self.eval(e, env) for e in expr])
    elif datatypes.isSet(expr):
        return datatypes.Set([self.eval(e, env) for e in expr])

リストの場合は、その先頭にあるオブジェクトの型と名前を見て、合致する条件に対応した処理を行う。 例えば、先頭がdefifのように特別な意味を持つSymbolの場合、環境に対して操作を行ったり条件分岐を行ったりする。 先頭が関数やメソッドの場合はそれらを適用する。

def eval_list(self, expr, env):
    if len(expr) == 0:
        return expr
    head = expr[0]
    if datatypes.isSymbol(head):
        if head.name == 'def':
            env.set(expr[1], self.eval(expr[2], env))
            return None
...
    elif datatypes.isLambda(head):
        args = [self.eval(v, env) for v in expr[1:]]
        return self.apply_function(head, args, env)
...

REPL

評価もできるようになったので、あとは外部からプログラムを読み込めるようにすれば終わり。 入力をパースして評価、という処理を繰り返すだけのREPLを実装した。 コードはrepl.pyにある。

(def np (import numpy))
(def chainer (import chainer))

(def l1 (chainer.links.Linear 4 3))
(def l2 (chainer.links.Linear 3 2))

(def my-forward
  (fn [x] (l2 (l1 x))))

(def x (.astype (np.array [[1 2 3 4]]) np.float32))

(.data (my-forward x))
; [[-1.02830815  0.6110245 ]]

これでひとまず大体の機能は備わったので、ChainerやTensorFlowのようなライブラリを使ってニューラルネットLispで書けるようになった。 やったね!!!!!!

オチ

Hyっていう言語があるんでそいつを使いましょう。 実装する前に知りたかった。事前のリサーチは大事。

どうでもいいこと

最初はPalisというオシャレな名前を付けて開発していたが、研究室のメンバーが「FudabaのPythonなんだからFuthonにしなよ」と言ったのでそのようになった。

参考

言語実装資料まとめ

YANSに参加してきました

大体上に書いてあるとおりなんですが、そういうわけにもいかないので絞り出しました。

YANSとはNLP若手の会の別名らしく、その名のとおり若い自然言語処理erが集まってワイワイ発表とかをする会です(たぶん)。

まずなんですけれど、これが初参加です。

実は昨年も参加登録して楽しみにしてたんですけど、そのときにインターンしていた研究所でのシンチョクが出ておらず、泣く泣くキャンセルしたという過去があります。

今回は他の学会と日程がかぶってしまったので、2日目から参加しました。

2日目のポスター発表でおもしろいなと思ったのは、機械翻訳向け前編集に有効な書き換えルールに関する調査でした。

機械翻訳の精度向上の手段の一つとして、原文が機械翻訳されやすい文を入力するというものがあります。 ただこの機械翻訳されやすい文というのが何なのか、またどうしたらそういった文を得られるかなどというのが分かっていなかったのですが、この研究はそれを調査しています。

手法自体はすごく地道で、英語、日本語どちらにも精通した被験者に文とそれに対応する機械翻訳結果を見せて、うまく機械翻訳されるまで意味が保たれる範囲で文を書き換えてもらう、というのを繰り返し行うものでした。

これによって得られた改変履歴から、どのような性質を持った文が機械翻訳されやすいかまで分析していてかっこいいなあと思いました。

この改変履歴を使って文の書き換えを自動で行えたりするとさらにおもしろそうだなあ…などと思って見てました。

夜になると旅館の一室が飲み会会場になり、お酒をグビグビ飲みました。結果、誰と飲んだのかすら、うっすらとしか覚えていません。

朝起きたらちゃんと自分の部屋で布団にくるまって寝ていたので本当によかったです。 なにか粗相をしてしまったのではないかとビクビクして一日過ごしましたので、お酒はほどほどにがいいですね…。

3日目にポスター発表を行いました。 僕の発表は自然言語からプログラミング言語ソースコードを生成する手法についての検討で、奨励賞をいただきました。 僕の発表と同じ時間に発表されていたいくつかのおもしろそうな発表が見れなかったのは残念です。

金沢駅でラーメンを食べて帰りました。

「迷子になったら動くな」を検証してみた

今日友達とホームセンターに行ったら迷子になってしまった。

いや、はぐれちゃっただけなんだけど、僕は携帯を持ってなかったし、この年で迷子センターに行くのもなーってことでしばらくウロウロして探した。

そこでふと幼い頃「迷子になったらそこから動くな、探される方がウロウロしてしまうと見つけにくくなるから」とママンに言われたのを思い出したんだけど、これって本当だろうかと思って検証してみた。

コードはgistにある。

動作させるとこんな感じ

迷子になったホームセンターを模したマップを作って、それに対して人を2人だけ用意してランダムに配置し、見つけられるまでに行動した回数をカウントする。

「双方動いた場合」っていうのと「ママンだけが動いた場合」っていう2つの状況を100,000回ずつ試して、その行動回数の分布を見てみる。

このシミュレーションでは、ひとはステップごとに移動と向きを変えることができて、向いている方向に対象の人がいたら見つけたことになる。

結果はこんな感じ。 横軸が試行回数、縦軸がその試行回数で発見できた回数。 試行回数の最高値は16,811なんだけど、双方動いた場合の最高値は1,995なのでこのグラフは全体の一部だけの表示。

f:id:paprikas:20150206034033p:plain

双方動いたときの平均試行回数が131.15286であるのに対し、動かなかったときの平均回数が536.75194。 ちなみに分散はそれぞれ27,592.7712938と692,246.087266。

双方動いたほうが圧倒的に早い!!!!!!!!!!

真面目に考察するなら、「ここにはいなかったからきっとあっちだ」っていう予想をAIがするようになれば、移動しないほうが探索回数の上限が決まるので早いと思う。

無限の大きさを持つホームセンターならどうなるんだろう。

簡単に人の顔に泥を塗る方法

僕は人の顔に泥を塗るのを得意とするのですが、泥を塗るのにも労力がかかるんですよ。 なので常日頃からこの作業を自動化できないかと思っていたので、論文の息抜きにやってみました。

import sys, cv2, random

imagefilename = sys.argv[1]

image = cv2.imread(imagefilename)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
gray = cv2.equalizeHist(gray)

faceCascade = cv2.CascadeClassifier("./lbpcascade_animeface.xml")
faces = faceCascade.detectMultiScale(gray)

for (x, y, w, h) in faces:
    points = []
    for i in range(1, 8):
        points.append((x+x/4+random.randint(-w/20,w/20), y+i*h/8+random.randint(-h/20,h/20)))
        points.append((x+w-x/4+random.randint(-w/20,w/20), y+i*h/8+random.randint(-h/20,h/20)))
    for i in range(1, len(points)):
        cv2.line(image, points[i-1], points[i], (64, 122, 170), 40)

cv2.imwrite("mud_"+imagefilename, image)

f:id:paprikas:20150204223231j:plain

これであなたも人の顔に泥をぬれる!!!!!!!!

lbpcascade_animeface.xmlはこちらからいただきました。

ヤドカリごっこ

結局NAIST自然言語の研究することに決めた。

関係者各位よろしくお願いします。

高校時代と大学入った当初はプログラミング言語に一番興味あって、当然大学院もそっち方面を研究しようと思っていた。

まさか自分が当時一番胡散臭いと思っていた自然言語に進むとは。人生わからんものだ。

東京での学生生活ちょっと憧れたけどな!!!!

進学先を決めたのはいいんだけれど、家が見つからない。

生駒駅周辺で探しているが、なんかもう結構埋まってる。

ひぃ。

追記: 駅から1分くらいのところに家決まりました。

大学のメールアドレスにスパムメールが届いた人へ

おはようございます。

昨日酔った勢いでスパムメールを書いてしまいました。

今は公開している。

そもそもなぜこんなことをしたかというと、大学からフィッシングメールに対する注意勧告のメールが来たので、ちょっとしたジョークということで試してみました。

送った先は冗談のわかってくれそうな教員方数名と生成した学籍番号全員です。

もし迷惑であると感じたなら 大変申し訳ございませんでした。 delihiros@gmail.com までご連絡ください。申し訳ねぇ!くらいは謝罪させていただきます。

本当は以前諸事情で手に入れた全学生のメールアドレスのリストを使おうと思っていたのですが、データがどこかに行ってしまっていて(多分大学の研究室に置きっぱなしのPCの中)、仕方がないのでリストを生成することにしました。

大学のメールアドレスは基本的には以下の構造をしています。

年度番号 学部アルファベット(工学部の場合T) 学科番号(情報工学科の場合5) 3桁の学籍番号 アルファベット

最後のアルファベットはチェックディジットのようなもので、ISBNのような計算式で求めることができます。以前式を求めたのですが、そのメモも見つからなかったし考えるのも面倒だったので、アルファベット総当りする実装になっています。

gmailの仕様として、一定時間内に多くのログインがされるとメールが出せなくなったり、1日に遅れるメールの数に制限があったりするので、Thread/sleepなんかを入れています。

実際に送ったのは教員の方々と11年度生のみです。

ちなみになぜこの記事を書いているのかというと、朝起きたら酔いが冷めていたからです。

大変申し訳ございませんでした。