LSHの論文

鬱です．

ゼミ前ってホントいやですね．



Imagineも大規模アップデートでいろいろと追加・変更があったので，

そろそろやりたい．

なんだかんだであまりにもブランクあけすぎた（あれｗもしかして，一ヶ月オーバー？）ので，

さっさと復帰したい．

でも，ゼミ終わるまでは無理．

というかゼミが無理ｗ

打ち合わせがもっと無理ｗ





さて，研究の話．

論文の内容の概略．

Approximate Nearest Neighbors: Towards Removing the Cures of Dimensionality

この論文で初めてLSHが提案された．たぶん．

でも，LSH主体な訳ではなく，

あくまでε-NNS(ε-approximate Nearest Neighbor Search)

を解く提案手法の一部として紹介されている．



この論文では，ε-NNSを解くために，

ring-cover treesという新しいデータ構造を用いることで高速化を可能としている．

詳細は・・・しょーじきよくわかりません（ぉぃ

まあ，でも実際これは概略さえ知ってればいいか思う．



しかしながら，ring-cover treesを構成する上でpoint location問題

を解く必要がある．

ここで，point location問題とは，queryの点が含まれている領域を探索すること．

http://www.cs.sunysb.edu/~algorith/files/point-location.shtml


で，論文では，point location問題の解法として，2つの手法を挙げており，

そのうちの片方がLSHというわけ．



あと，どうやらこの手法には次元の削減にramdom projection(ランダム射影)

を用いているらしい．

最初，ただランダムに次元を選ぶようなので，

まあ，そういうもんか

と思っていたら，きちんとした理論展開があるらしい・・・．

「Johnson-Lindenstrauss補題」というらしいけど，

どうやらこれも使ってるみたい．

一応，確認しておくか．

覚えておきたいショートカット

Macのショートカットは独特．

テキストのコピペ等の最も基本的なところは，

crtl => commandに置き換えられるだけなんだけど，

その他は結構違ってることも多い．

覚えるまでメモ代わりに書いておく．

Mac起動中の動作
Mac起動中にC	システムフォルダを含む CD から起動する

LDAP設定メモ

間違ってるかもしれないがメモ．



libpam-ldapをインストール．

インストール途中でダイアログが表示される．

サーバ，ベースDNを入力して進む．

ほかはデフォルト．

『ヱヴァンゲリヲン新劇場版：序』特装版DVD到着！

土日で十分堪能しますた．

あれ？だんだんブログの趣旨が・・・まあ，いいやｗ



パッケージはこんな感じ．

外側の赤いケースと中の黒いケースにはそれぞれ

「EVANGELION:1.01  YOU ARE (NOT) ALONE.」

の文字．







黒ケースは三つ折りになっていて，

左側のポケットには解説書等，右側にはディスクが2枚付いてました．

























そして，一番楽しみにしてたのはコレ！



 











��ｰｲヽ(ﾟ∀ﾟ)ﾒ(ﾟ∀ﾟ)ﾒ(ﾟ∀ﾟ)ﾉﾜｰｲ

映画の生フィルム！

すごいよね．生フィルム特典にするとか．

写真ではよくわからないけど，

光にかざすとちゃんとミサトさんがいましたｗ

たぶん，ヤシマ作戦のシーンの一コマだと思われ．

まあ，シーンの切れ間とか，激しい動きのあるシーンじゃなくて，

ちゃんとキャラクターが写ってるところでよかった　ε-(´∀｀*)ﾎｯ



結局，連続で2回も見てました．

いや～よかった．実によかった．

冒頭の伏線とか，次回予告とかをじっくり見て検証できたし大満足！



次は「破」ですか．

「壊れていく碇シンジの物語」（次回予告で言ってた）

うーん，楽しみ．

新キャラ，新エヴァ出るようだし．



でも，今年上映とはなってるけど，

ホントに今年上映できるかは未知数だよな．

今回の映画は，上映のつい数日前に完成したという話だったし，

なにより，過去の経緯からするに・・・．

まあ，期待せずに気長に待つ方が良いだろうな．



・・・



・・・



・・・



破(　ﾟдﾟ)ﾏﾀﾞｰ?

就職活動日記 0

すでに昨日（4/23）のことですが．



マイナビ主催の就職説明会に行ってきた．

きっかけはチラシ．

これどこでもらったんだっけ？

研究室で秘書さんが配ってくれたんだっけ？



今のM2の先輩の就職活動が少し遅いらしいということ．

自分に就職とかの自覚が全くないこと（いや，むしろニートのほうがry）

そもそも業界知識に乏しいこと（ゲーム業界以外）

そして，会場がKEERの発表会場だったことw

いろんな理由があって行く気満々でした．

でも，同期はどうも反応薄といった感じなので，

一人で偵察をかねて行くことにした．



結果．

まあ，説明会というだけにこんなもんかといった感じ．

就職までのガイダンス？みたいな．

人数も40~50人ぐらいだったし．

以下，説明会で思ったことを書いておく．

自己分析しとかないと・・・．

学内説明会は10月と12月．

でも，「自己分析」「業界研究」はそれより前に始めるべき．

説明には，自己分析は6月から，業界研究は7月からとある．

��あくまで，参考程度に）

エントリーシートは書くのが大変そう．

例で見せられたのは，右一面が「自由に自分をアピールしてください．」

��イラストも書いてよい）

10月に「エントリーシートの書き方」の講座があるらしい．

これは参加すべき．

「エントリー」は自由だ．とにかくとりまくれ！

北海道だと一人で30社とか普通らしい．

要は「会社案内の資料請求みたいなもん」らしい．

絶対受けたい企業，選考が早い企業，少しでも興味ある企業は

積極的にエントリーすべし．

道内の小さい企業でもいいから内定はとっておくべき．

らしいよ．

安心感が違うとか，本命前の練習になるとか，そういう理由で．

企業が思っている理系学生の良い印象．

「基礎学力が高い」

「情報収集能力が高い」

ふーん．

企業が思っている理系生の悪い印象．

「コミュニケーション能力が低い」

「プレゼンテーション能力が低い」

��(^o^)／

どうみても自分です．本当にありがとうございました．





帰りにミスドのドーナッツ2つと飲み物もらった．

おなかも空いてたし，マイナビの登録用紙を引き換えに釣られてみることにした．





で，なんでまた，こんなこと書き出すかというと，

実は，今日たまたま研究室の先輩から

「就職活動記録」（言葉とか少し直すらしいけどほぼ完成したもの）

なるものをもらったのだけど，

ちょうど，その中に「就職活動日記」があったので，



Blogに書いておけば，コピペでいいじゃん！



というわけ．

Option + キー

あ，ありのままに起こった事を話すぜ．

普通”Shift + キー”で大文字の英字を打つ要領で，

間違って”Option + キー”と打ってしまったんだ．

そしたら，"Option + a"で"å"，"Option + s"でßと表示されたんだ！

¡   ™   £   ¢   ∞   §   ¶   •    ª   º   –   ≠   \
œ   ∑   ´   ®   †   ¥   ¨   ˆ   ø   π   “   ‘
å   ß   ∂   ƒ   ©   ˙   ∆   ˚   ¬   …   æ   «
Ω   ≈   ç   √   ∫   ˜   µ   ≤   ≥   ÷   `

ま，まさか・・・

"Option + Shift + キー"
⁄   €   ‹   ›   fi   fl   ‡   °   ·   ‚   —   ±   |
Œ   „   ´      ˇ      ¨   ˆ   Ø   ∏   ”   ’
Å   Í   Î   Ï   ˝   Ó   Ô      Ò   Ú   Æ   »
¸   ˛   Ç   ◊   ı      Â   ¯   ˘   ¿   `

すげぇ・・・

sayコマンド

sayコマンドはその後に書いた英文を発音するコマンド．

書式：
say [-v voice] [-o out.aiff] [-f file | string ...]

voice  : /System/Library/Speech/Voices/にあるvoiceデータ名
out.aiff : 出力ファイル名
file : 発音させたい英文のテキストファイル
string : 発音させたい英文

stringに発音させたい英文を入力するとその通りしゃべります．

さらに，オプションでファイル読み込みと音声ファイル出力，

voice選択が可能と機能が豊富w

そんな，すばらしいsayコマンドくんはXcode

��Apple製開発ツール，gccとかJavaがパッケージされてる）

をインストールするともれなくついてきます．

ワーイ，ウレシイナ．



ところで，どうやらvoiceデータのみなさんはあなたに大切なものを盗まれたようです．

Victoriaさん




Bruceさん




Albertさん




・・・そして，Bellsさん




ちょw Bells名前そのまんまwww



*音声を聞くにはブラウザに対応したプラグインが必要です．

カテゴリー：Mac小ネタ

Macは独特だ．

まあ，最初からMacな人にはそうは感じないかもしれないけど．

OSの細かな違いに注目してみると，興味深いことがあってなかなか面白い．

けっこう小ネタが多くあるので，

気づいた小ネタをメモしていくカテゴリー「Mac小ネタ」を作ってみました．

SafariGestures

マウスジェスチャーがFireFoxにあってSafariにもない訳がない！

と思って探してみました．

すると，Safari Gesturesが該当！

ちなみに，Mac用のSIMBLプラグインです．

使ってみたけど，これはなかなか高機能．

・ジェスチャーのトリガー（ジェスチャーの開始を知らせるボタン）の設定
・便利な独自コマンドを装備
　"選択範囲のリンクを開く", "選択文字列を新規タブで開く", e.t.c.

このへんの機能がとても気に入っています．

とくに，"選択範囲のリンクを開く"は便利だよね．

新規タブ => URLコピペの手間がなくなるし．



しかし，驚いたのはこのプラグイン今年の3月に開発が始まってるってこと．

現バージョンver.0.0.7になるまでの短期間で，

バグとりがあっという間に行われ，かつ機能の向上が目覚ましい．

本当に制作者様には脱帽です．

おかげで安心して使えます．





つーか，俺Mac始めるタイミングよすぎw

k-d trees (k-dimensional tree)

k次元空間をいくつかの部分空間に分けて考えるデータ構造．

Nearest Neighbor Search(NNS)などで用いられることが多い．

k次元を2分し二分木として表現することで，探索を0(log n)，ワーストO(n)で探索可能．

参考：http://en.wikipedia.org/wiki/Kd-tree

サキュバスさんカウンタ

真・女神転生Imagineのサキュバスさんカウンタ設置しますた．

右下の方で悲しくなるような数のカウントをとってくれています・・・．



イマジンは課金制の無料オンラインRPGです．

興味ある方は是非やってみることおすすめします．

今は一周年記念のイベントが多くあり，
初心者優遇のイベントもあるので，
これから始めるとかなりお得です．







個人的には，サキュバスよりもガルムたんの方が (ry

個人的Macアプリケーションまとめ

Mac復活ｷﾀ━(ﾟ∀ﾟ)━!

まあ，今日の3時までやってましたがｗ

昨日構築した分までやって，

さらに以下のソフトのインストールと設定をしてみた．



パッケージ管理ツール - Fink, FinkCommander

　Finkはapt-getによるパッケージ管理ツール．

　Ubuntu的には同じなので使いやすく感じた．

　付属のFinkCommanderは，GUIによるFinkのパッケージ管理．



TeX環境の構築 - TeXShop

　詳しくは以下のURL参照．

　小川氏によって提供されているpTeX，GhostScript，

　さらにそれらを自動で実行しPDFまで自動生成するエディタTeXShop

　をインストール．

http://osksn2.hep.sci.osaka-u.ac.jp/~taku/osx/install_xtexgsgv.html



多機能エディタ - mi

　使ってないからよくわからんけど，Macならまずこれっぽいらしいので．



VNCクライアント - JollysFastVNC

　"Chicken of the VNC"というVNCクライアントもあるが，

　こちらの方がラグが少なかった．

　当然，サーバ側にはVNCサーバが必要．

　日本語入力を可能とするには，以下にあるサーバ側の設定ファイル

　　~/.vnc/xstartup

　を編集する．

　詳しくは，

　http://safe-linux.homeip.net/other/linux-vnc-03.html



仮想デスクトップマネージャ - VirtueDesktops

　Linuxで標準でついていた仮想デスクトップをMacで実現するソフト．

　切り替えもいくつか設定できてかっこいい．



圧縮解凍ソフト - The Unarchiver

　いろいろ解凍，圧縮可能．これ一つあればおk．



カスタマイズ，メンテナンスアプリケーション - OnyX

　Finderの裏設定など各アプリケーションのカスタマイズが可能．

　不可視に設定されたファイルもこれで閲覧できる．



アプリの安全なアンインストーラ - AppCleaner

　アプリケーションのアンインストーラ．

　インストールが自動化されていて簡単なくせに

　アンインストールがすべて手動のMacにとっては必須アプリ．





ついでに，前回の時点でインストールしてたものも列挙．



Safariの機能強化プラグイン - Stand

　「ザ・ワールド！」



　じゃなかったw

　プラグインです．

　これがなかったら，FireFoxに乗り換えてたかもしれない．

　事前にSIMBLをインストールする必要あり．

　詳しくは，以下のURL．

http://hetima.com/safari/stand.html



iTunesコントーラー - iMote

　ホットキーでiTunesをコントロール．

　曲が変わると楽曲情報を表示するフロート機能搭載．

　メニューバーに常駐するので非常に便利．



FTPソフト - Cyberduck

　かわいいあひるちゃん．

　多くのエンコードに対応し，接続設定をブックマークすることが可能．

　家のNASとのFTPにちょうどよかったのでインストール．



X11

　Xを使うために必要なアプリ．

　これはOSのインストールディスクからカスタマイズで一緒にインストールした

　方が安全．



XCode Tools

　gcc，Javaなどの開発環境系がそろっているソフト．

　これがないことにはなにも始まらない．

　これもOSのインストールディスクに入ってるものからインストール．



Thunderbird

　使い慣れているので．



Adobe Criative Suite Premium

Office:Mac

iLife'05

iWork'05

　このへんは，研究室にあったソフト．

　わーい．ひとりじめw

　でも，iWorkはOfficeにかぶってるからいらないかも．



Remote Desktop Connection

　Office:Macに付属．

　MacからWindowsにリモートログインするソフト．

　まあ，何かあるかもしれないし．一応ね．



Microsoft Messenger

　Officeについてるが，バージョンが古いのでネットから別入手．



とりあえず，こんなところ．


あとは，"ことえり"をどうにかしたいな．日本語変換微妙過ぎw


http://veadardiary.blog29.fc2.com/


はとくにお世話になったサイト．

悲しき再インストール

再いんすと〜る、再インスト〜ル♪



この間からセットアップしてたMacがお逝きになりました．

悲しい・・・．

なので、ダウンロードしたソフトや参考HPをさっき列挙したのですよ．

今日は，終わるまで帰れません．

MAC参考URL

アプリケーション系の解説

http://stwok.exblog.jp/



MACまとめ

http://www3.atwiki.jp/itunes/pages/23.html



UNIXの環境整備

http://www.astro.phys.s.chiba-u.ac.jp/~takahasi/macosx/macosx-top.html



MacWiki

http://macwiki.sourceforge.jp/wiki/index.php/



わかばマークのMacの黙示録

http://wakabamac.blog95.fc2.com/



Mac買ったからすぐいれるソフトまとめ

http://wiki.fdiary.net/mac2ch/



iTunesをメニューバーから操作するソフト - iMote

http://www.mkd.cc/imote/



Safariのプラグイン - Stand

http://hetima.com/safari/stand.html



FTPソフト - Cyberduck

http://cyberduck.ch/

NASの文字化け 続報

Macによる文字化けは、文字エンコードが多くサポートされているFTPソフトCyberduckでなんとかなった．



http://cyberduck.ch/



なんて優秀なあひるちゃんなんでしょうｗ





・・・しかし，それでも直らない文字化けがあった．

これは，どうやらFTPだけにOSに依存せず共通して起こる問題のようで，

どうすればいいかわからなかった．

具体的には，



ぷよぷよ?drwxrwxr-x   3 admin    users        4096 Mar 29 03:52 カービィのきらきらきっず

こんな感じ．



なにこれｗ

ファイルのパーティションとか所有者が表示するあたり，明らかにNASが悪さしてるっぽい．

しかもたちが悪いのは，アクセスしてもリンクがないといって仲のファイルを表示できないこと．

これは致命的なんですけど・・・．



よく観察すると，どうやら特殊文字系（～, ハート, e.t.c）がある場合，FTPをかえしてみると，こんなことになるらしい．

しょうがないので，これら文字がついたファイル名をローカルネットワーク側（こっちちからアクセスする分には文字化けはない）から変更することにした．

iTunesはすべてリンク張り直しですか・・・めんど

Macメモ

NASの文字化けについて

  http://homepage.mac.com/isaak1/iblog/B56609797/C1664775190/E20070104142413/index.html

Nice iTunes.

以前作っておいたゲーム音楽のバックアップディスクをMacに挿入。
これで、ゲームを移すことが簡単に終わった。
さらに、共有の設定で研究室内で音楽共有。
これもiTunesだとチェック入れるだけなので簡単。
あっという間にMacはゲーム音楽サーバとなりましたw

KH

決して空気が読めない訳じゃなくw
キングダムハーツ。
ディズニーシー行ってきたせいか、何故かやりたくなった。
未だに未クリアだったし、2の評価もよかったようなので。

でも、改めてやってみると、昔は挫折したところも今はスイスイ。
どんだけ自分がショボかったか思い知らせされてしまった…。

Macはいただき

マックはいだたいだぜ！

でも，Mac使い方わからん・・・．

勉強用ソース．



http://tokyo.secret.jp/macs/index.html



http://archive.mag2.com/0000242266/20080228080457000.html

LSHアルゴリズム

基本的な考え方

対象となる特徴ベクトルp=(x1, ..., xd) (d：次元数)
↓
二進数のベクトルv(p)に変換
v(p)=UnaryC(x1) ... UnaryC(xd)
C：ベクトルの要素の最大値
UnaryC(x)：1がx個の列に0がC-x個の列をつなげた0,1で構成される値．
↓
ハッシュ関数：gI(p)
{1, 2, ... , Cd}の部分集合Iによって選ばれたビットの値を並べた値がハッシュ値．

Step1:

{1, 2, ..., Cd}の部分集合Ii (i = 1, ..., L)について，
のハッシュテーブルを作成．

(つまり，ひとつの特徴ベクトルにつきL回ハッシュ値を計算してテーブルに格納．)

全部でL個のハッシュテーブルTiができる．

このとき，競合(collision)する場合は，同じエントリに格納する．

ここ重要！ｍ9っ｀Д´) ﾋﾞｼｯ!!

Step2:

最近接点探索．

クエリqに対してすべてのハッシュ関数でハッシュ値を求める．

得られたハッシュと同じキーを持つエントリに含まれる特長ベクトルをすべて取り出す．（同じキーを持つエントリの和集合）→　最近接点候補

候補の中から最近接点を距離計算により発見．

Locality-Sensitive Hashing

Locality-Sensitive Hashing [1] (以降、LSH)は，Indykらによって提案された最近接点探索の確率的な近似アルゴリズム．

LSHはハッシュテーブルを用いることで高次元のデータセットでも最近接点探索を高速に実行する．

・ハッシュテーブル(hash table)

キーと値の組（エントリと呼ぶ）を複数個格納し，キーに対応する値をすばやく参照するためのデータ構造．

・ハッシュ関数(hash function)

あるデータが与えられた場合にそのデータを代表する数値を得る操作．または，その様な数値を得るための関数のこと．

ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという．

LSHの重要なポイントは，類似しているデータ間のハッシュ値は一致し，類似していいないデータ間のハッシュ値は異なるようなハッシュ関数を用いることにある．

これにより，ハッシュテーブルを用いた探索が可能となり，ハッシュテーブルの特徴であるデータ参照の速さをいかした探索が可能となる．

参考文献

[1] A. Gionis, P. Indyk and R. Motwani, "Similarity Search in High Dimensions via Hashing," Proc. of the 25th VLDB Conference, pp. 518-528, 1999.