2016-07-13

ncatで遊んでみる

手慰み計算機

ncatという超便利コマンドを恥ずかしながらいままで知らなかった。HTTPプロトコルを学ぶには最適なおもちゃだ。

www.example.com の 80番ポートに、 / を GET するという HTTP リクエストを投げてみる。

fjk@x240:~$ ncat www.example.com 80 << END
GET / HTTP/1.1
Host: www.example.com

END

すると、以下のような HTTP レスポンスが返ってくる。200番のステータスコードが帰ってきているので、リクエストはうまいこといったようだ。いろいろヘッダーフィールドについているが、こう見ると HTTP プロトコルはテキストを送って返すだけという非常に単純なプロトコルなことが分かる。

HTTP/1.1 200 OK
Accept-Ranges: bytes
Cache-Control: max-age=604800
Content-Type: text/html
Date: Tue, 12 Jul 2016 14:47:58 GMT
Etag: "359670651"
Expires: Tue, 19 Jul 2016 14:47:58 GMT
Last-Modified: Fri, 09 Aug 2013 23:54:35 GMT
Server: ECS (rhv/818F)
Vary: Accept-Encoding
X-Cache: HIT
x-ec-custom-error: 1
Content-Length: 1270

<!doctype html>
<html>
<head>
    <title>Example Domain</title>
以下略

www.google.com に GET を投げると 302 が帰ってきた。

fjk@x240:~$ ncat www.google.com 80 << END
GET / HTTP/1.1
Host: www.google.com

END

HTTP/1.1 302 Found
Cache-Control: private
Content-Type: text/html; charset=UTF-8
Location: http://www.google.co.jp/?gfe_rd=cr&ei=-AKFV4uqMq7U8AeQ67-IBA
Content-Length: 261
Date: Tue, 12 Jul 2016 14:47:20 GMT

<HTML><HEAD><meta http-equiv="content-type" content="text/html;charset=utf-8">
<TITLE>302 Moved</TITLE></HEAD><BODY>
<H1>302 Moved</H1>
The document has moved
<A HREF="http://www.google.co.jp/?gfe_rd=cr&amp;ei=-AKFV4uqMq7U8AeQ67-IBA">here</A>.
</BODY></HTML>

http://www.google.co.jp/?gfe_rd=cr&ei=-AKFV4uqMq7U8AeQ67-IBA に移動しているらしい。この文字列の意味は ncat では分からない。

ncatはソケットにリクエストを投げるだけでなくて、リクエストを待つことができる。

fjk@x240:~$ sudo ncat -l -p 8000 << END
HTTP/1.1 200 OK

<HTML><HEAD></HEAD><BODY><H1>HELLO WORLD</H1></BODY></HTML>
END

としたら、8000番ポートに接続されたときに、 HTTPレスポンスを返す。ブラウザで http://localhost:8000/ にアクセスしたら

f:id:fjkz:20160713000501p:plain

ちゃんとWebサーバーっぽい動きをしている。

リクエスト内容は標準出力に吐かれる。

GET / HTTP/1.1
Host: localhost:8000
Connection: keep-alive
Upgrade-Insecure-Requests: 1
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8
Accept-Encoding: gzip, deflate, sdch
Accept-Language: ja,en-US;q=0.8,en;q=0.6

Google Chrome は HTTP 1.1 でリクエストを投げて、Chrome のバージョンもリクエストに乗せていることが分かる。

試してみると、HTTP はテキストベースで、すごい単純なプロトコルであることが見える。もっと良いプロトコルがあるに違いないが、現実的にはこういう単純で原始的なプロトコルを組み合わせると、今の巨大なインターネットになると思うと、なんとも感慨深いものがある。

2016-07-08

テスト駆動開発で品質が上がる証拠

計算機ノート

テスト駆動開発（TDD)で品質が上がる証拠を得た。

Realizing quality improvement through test driven development: result and experiences of four industrial teams*1

性質が異なる４つの製品の開発プロジェクトで TDD を行って、TDD でない類似の開発プロジェクトとの比較をした。４つのプロジェクトはデバイスドライバ・OS・Webアプリケーション・PCアプリケーションと全く異なる種類のものである。

f:id:fjkz:20160708213157p:plain

欠陥密度は40%から90%減少し、一方で実装時間は15%から35%増加するという結果が得られた。データだけ見ると、TDDの導入は投資としてはお得だと言える。

*1:http://link.springer.com/article/10.1007%2Fs10664-008-9062-z

https://github.com/tpn/pdfs/blob/master/Realizing%20Quality%20Improvement%20Through%20Test%20Driven%20Development%20-%20Results%20and%20Experiences%20of%20Four%20Industrial%20Teams%20(nagappan_tdd).pdf

2016-07-02

インターネットの物理学

本所感 a.k.a. poem

服部の『Amazonランキングの謎を解く: 確率的な順位付けが教える売上の構造 (DOJIN選書)』を読んで、なかなか興味深かった。（興味深かったけれども、本書は分かる人にしか分からなくて、分かる人は原著論文が読めるレベルという一体誰向けに書いているのか不明な非常に読みづらい本である。私も5割ぐらいしか分からなかった。余談や脱線も多くて、構成も稚拙だ。編集者はもっと頑張って欲しい。）

この一年以内に読んだ本で最も面白かったのは、バラバシの『新ネットワーク思考―世界のしくみを読み解く』という本であった。

どちらも、インターネット時代に現れた現象を古典力学の側面から切り取とろう試みをしている。服部はAmazonのランキングを、バラバシはWebベージごとのリンクを対象とした。

物理学は名前の通り、光だとか水だとか物質的な現象を対象とした学問であるが、ネタが尽きてきたということもあるのかそれ以外の現象にも手が広がっている。例えば、経済現象を物理学的な方法論で分析しようという試みは経済物理学と呼ばれたりする。

インターネットの普及とともに、インターネットがなければ見られない現象を調べようという試みが行われるようになった。インターネットはデータが取れるから、物理学の手法を試すにはうってつけなのだ。データがないことやもう調べつくされたことが、物理学のボトルネックなので、データも簡易に集められてかつ未開拓な領域に物理学者が押し寄せるのだ。インターネットはCERNで物理学ための道具として発明されたが、インターネットが逆に物理学の対象になっている事実が面白い。

個人的に、ソフトウェアも物理学の対象にできると予想を立てている。ソースコードとその成長の過程を公開するのが当然となっている現在、ソフトウェアも科学の対象にできそうだと思っている。ネットワーク理論だとか統計力学理論が使えそうで、ソフトウェアの成長は熱力学過程とのアナロジーで議論できそうだ。調べたいが、メトリクス収集ツールを作るところからはじめなければならないことと、そこまでやるには趣味ではきついことから、できていない。そして、それが私以外の人にとって何の意味があるのかも分からないので、スポンサーも募りようがない。

2016-07-01

リコメンデーションのための相関係数２

計算機ノート

ユーザーに対して類似のアイテムを推薦するアルゴリズムのアプローチには、

ユーザーの相関をとるアプローチ、
アイテムの相関をとるアプローチ

がある。今回は２のアイテムの相関をとるアプローチについて。

	item A	item B	item C	item D
user 1	2	0	2	1
user 2	3	0	1	3
user 3	2	1	3	1
user 4	2	2	4	X

前回と同様に、４人のユーザーと４個のアイテムがあったとして、それぞれのユーザーが各アイテムに上の表のような評価を与えているとする。user4のitem Dに対する評価は不明で、今これを推定したいとする。

アイテムごとにユーザーの評価のベクトルが与えられる。ここでは、user 1, 2, 3の評価のベクトルを取る。item A では (2, 3, 2), item B では (0, 0, 1), item C では (2, 1, 3), item D では (1, 3, 1) となる。

これらのベクトルの類似度をもって、アイテムの類似度とすることができる。２つのベクトルの類似度は、間の角度によって求められる。便利なので間の角度のコサイン値を類似の尺度とする。これは、コサイン類似度と呼ばれる。[0, 1]の値を取り、1 に近いほど類似度が多きい。

f:id:fjkz:20160701192653p:plain

item a, b のベクトル →p_a, →p_b のコサイン類似度は以下で計算できる。

f:id:fjkz:20160701211219p:plain

ドットは内積、||はベクトルの長さの意味です。

計算してみると、

C(A, D) = 0.95
C(B, D) = 0.30
C(C, D) = 0.64

のとなるので、item D は item A と似ていると言える。

user u の item a に対する評価の予測値は以下で計算する。

f:id:fjkz:20160701212359p:plain

ここで、N は類似度が高いアイテムの集合である。

N = {A} とすると、user D の item 4 に対する評価の予測値は、２となる。

2016-06-30

リコメンデーションのための相関係数１

計算機ノート

ユーザーに対して類似のアイテムを推薦すること、いわゆるリコメンデーションを機械にさせるのが、浸透している。リコメンデーションのアルゴリズムというのは興味深い。

	item A	item B	item C	item D
user 1	2	0	2	1
user 2	3	0	1	3
user 3	2	1	3	1
user 4	2	2	4	X

４人のユーザーと４個のアイテムがあったとして、それぞれのユーザーが各アイテムに上の表のような評価を与えているとする。user4のitem Dに対する評価は不明で、今これを推定したいとする。

アプローチとしては２つあって、

ユーザーの相関をとるアプローチ、
アイテムの相関をとるアプローチ

がある。

今回は１について。

ユーザーごとの相関を計算には、ビアソンの相関係数がもっとも基本的な形だ。

user a, item b との相関係数は以下で計算できる。

f:id:fjkz:20160630210116j:plain

ここで、 P はアイテムの集合であり、 r_i, j は user i のitem j に対する評価であり、 \bar{r_i} は user i のアイテムの評価の平均値である。

相関係数なので[-1, 1]の範囲を取り、1に近いほど類似度が高いことを示している。

今回は user 4 に似たユーザーを知りたいので、 user 4 と user 1, 2, 3 の相関係数を求める。 user 4 には item D の値がないので、 P = {A, B, C} です。

計算してみると、

C(A, D) = 0.50
C(B, D) = - 0.19
C(C, D) = 0.87

となり、user A は user D と高い相関があることが分かる。

user a の item p に対する評価の予測値は、以下の式から求められる。

f:id:fjkz:20160630223945j:plain

ここで、Nは最近傍ユーザーの集合である。

user C を user D の再近傍ユーザーとすると、 user D の item 4 に対する評価の予測値は、

r_pred(D, 4) = 2.67 + 0.87 * (1 - 2.0) / 0.87 = 1.67

となる。

2016-06-26

寄付と投資

考え事

歳をとったのか世のため人のために多少は貢献できないかなと思うようになった。手っ取り早い手段は寄付をすることだ。世の中にはお金で解決できる問題は多い。ただお金を出すだけで世の中のためになるなら楽なものだ。金は命よりも重いが、負担にならない程度のお金はほとんど痛みもない。時間だとか労力だとか精神力を負担する方のはやはり大変だ。

駅前を歩いていると、しばしば学生団体と思しき若者が寄付を募っている。立派だと思う。ただ、街頭募金を募っている学生は、必要な人に金を届けるルートを持っているのかと疑問がわく。演説を聞いていると、日本赤十字社などのNPOを経由して送金するようだ。

それなら直接そのNPOに送金したほうが確実だと思う。街頭募金の演説がきっかけで、NPOへの直接の寄付が行われるなら、街頭募金を募る活動にも意義はある。ただ、それだと街頭募金の活動の成果が彼らには見えないので、街頭募金を募る人を応援する意味で彼らを信用して彼らを通して寄付を行うのもありうるだろう。

いずれにしても寄付をするならどこかの団体を経由するしかない。集めた寄付金をどのように使うかの判断は任せたい。誰がどれだけ困っているかなんて、なかなか知りようがない。少額の寄付に対して、それを調べるエネルギーは割けない。NPOが適切に寄付金を使ってくれることは、信用するしかない。

そのため、寄付が集まる団体は権威があるところになる。赤十字社だとかユニセフだとか。無名な慈善団体には寄付をしようとはなかなか思わないものだ。慈善事業は志さえあれば誰でもできそうだが、現実には商業と変わらず権威があるところが有利だ。

これは別に決して悪いことではない；お金が本当に困った人の助けのために効果的に使われるのであれば。しかし、実際のところどうなのだろうと疑問に思っている。ただ、私は赤十字社やユニセフよりも有意義な金の使い方を知っているわけでないので、答えはない。

権威のある団体よりも、寄付すべき団体があるのかもしれないが、それも知りようがない。

困っている人が、クラウドファウンディングみたいな形で直接寄付を募れるようにしたらどうだろうと思ったが、これは良くない。クラウド乞食にしかならないし、困っている人が収支報告なんて出せるわけもなく、余計な混乱を招くだけだ。また、そのマッチングを行う場所の運営費用は誰が負担するのだという話になる。ショバ代なんて当然取れない。

なんかうまい方法があるのではと考えて見たが、寄付は一種の投資なので、それが解決できたら投資の問題なんてすべて解決できてしまう。どうも解決する方法はなさそうだ。

2016-06-12

『Who Gets What』

本考え事

アルビン・E・ロス著『Who Gets What――マッチメイキングとマーケットデザインの新しい経済学』を読んだ。本の内容とは別に考えたことを記す。

Who Gets What (フー・ゲッツ・ホワット) ―マッチメイキングとマーケットデザインの新しい経済学

作者: アルビン・E・ロス,櫻井祐子
出版社/メーカー: 日本経済新聞出版社
発売日: 2016/03/19
メディア: 単行本
この商品を含むブログ (2件) を見る

マーケットデザインというのは経済学・ゲーム理論の応用して効果的なマーケットの制度を設計しようというものである。経済学という学問は、数学の一分野に過ぎなくて、ほとんど数字遊びで現実に存在する問題の解決には全く貢献しない時代が長かったが、近年では経済学の知見を工学的に利用して現実の問題の解決することに成功している。現実に困っている人がいて、その問題の解決ができるということに私は面白さを感じる。

マーケットというのは、２つの集合――例えば、売り手と買い手、男と女、企業と求職者、大学と受験者――のそれぞれの要素を結びつけるシステムのことだ。２つの異なるクラスに属するものを結びつけることをマッチングという。マーケットというのははっきり誰かが定義していると限らない。誰かが何かを探し始めたら、マーケットというのは自然発生する。

しかし、皆が別々の場所・時間でマッチング相手を探していたら効率が悪いので、出会いの場所というのが設置される。*1このマーケットは人工的なもので、そこでのルールとかは設計の余地がある。設計が悪くてマッチングされる組み合わせが適当でなかったり、そのためにマーケットの外で取引が行われたりする。そうすると、みんなが幸せにならない。どのようにマーケットの制度を設計すると、参加者の全員が幸せになるのかを考えるのがマーケットデザインである。経済学というのは皆が幸せになる方法を探求する学問である。

世の中には証券市場に代表とされるような人工的なシステム化されたマーケットも多いのだけれど、そのようになってないマーケットの方が多い。何かと何かを結びつけることは、システムを介さずに行われているものがほとんだ。しかしながら、場所がないところでのマッチングというのは非常にコストがかかるものだ。仲介業というマッチングを行うための専門の業種が存在するほどである。

社会に存在する職業のうち相当部分は、仲介業である。例えば、営業職をしている人って労働人口のうちのかなりの割合を占めている。彼らは何も生み出しているわけではないにも関わらず、こんなにいるのはおかしい；マッチングを効率化する仕組みを作れば生産的な仕事に人口を割くことができる――という見方もできる。あるいは、マッチングというのはそれ自体がそれほどに価値を生み出すものだから、こんなに多くの人を養うことができる――という見方もできる。いずれにせよ、社会で行われている活動のほとんどはマッチングだというのは事実であろう。

今よりももっと高速に安価にマッチングを行うでも、今よりも適したマッチングを行うのでも、どちらのアプローチをとってもマッチングを効率化するようなマーケットを作るというのは、社会的に意味があることだろう。

さて、今私の前にあるコンピュータはインターネットにつながっているわけだが、インターネットというのはこれ以上ないほどにマッチメイキングを行うのに適した装置である。ほとんど全世界の個人が常に接続しているのだ。インターネットのいろいろな使い方が日々考案されているわけだが、何かと何か引き合わせるというのはインターネットの使い方として最も効果的な使用法なのではないかと思う。

インターネットを介したマッチングを行うサービスというのは既に多くあって、ヤフオク、メルカリ、楽天市場、Amazonマーケットプレイス、リクナビ、等々いくらでも挙げることができる。これらを使うことで、インターネット以前には仲介業者が必要だったり、あるいはインターネットがなければ成立しなかったマッチングというのが達成できるのだ。場所を提供するビジネスモデルをプラットフォームビジネスというそうだが、あたればでかい商売である。

インターネット上のマーケットというのはまだまだ可能性があると思う。本にあるようなゲーム理論をマーケットの設計に活用するアプローチというのは、有効な手法な気がしているのだ。昔、Gale-Shapleyアルゴリズム（受け入れ保留アルゴリズム）に基づいて最適なマッチングを作るという合コン用のAndroidアプリを作った。むき出しの理論のままでは全然使えないけれども、どうにかこのコンセプトを現実に適用できる形に落とし込めないかと未だに思っている。最大多数の最大幸福を実現するような仕組みが世の中に受け入れられると私は信じているし、それが実現した社会がどういうものなのかを見てみたいのだ。

*1:ナンパスポットのように自然に場所ができることもある。