たくさんタブを開く人にとってFirefox 5は福音となったか
3ヶ月ほど前に、たくさんタブを開く人にとってFirefox 5は福音となる…かも という記事を書いた。
6/21にFirefox 5がリリースされ、実際にFirefox 5が使えるようになった。確かに、Firefox 5になってから、CPU使用率は下がったようだ。タブを100個以上開いた場合でも、CPU使用率は5%程度にまで下がっている。そういう意味では恩恵は大きい。
ここで話が終わればいいのだが、今度は数秒に1度のCPU使用率のスパイクが気になるようになってきた。環境によってスパイクぶりは違ってくるのだが、会社のFirefoxだと、CPU使用率が80%程度にまで一瞬だけ上がる。しかも、そのたびにブラウザが固まる。最近は会社だと暑くて数秒に1回ファンがうるさく回るので、Firefoxを使えなくなってしまった。
数秒に一度のCPU使用率の上昇というと、まず疑うべきはGCだろう。「firefox garbage collector」でぐぐると、Firefox unresponsive when garbage collector is workingというバグ報告が見つかった。他にも同じような症状で困っている人はいるらしい。
結局、このバグ自体はunconfirmedで片付けられてしまっているようだが、いくつか面白い情報が手に入った。about:configで"javascript.options.mem.log"というオプションをtrueにすると、GCを起動するたびにログを吐いてくれるようになるらしい。試してみると、ブラウザが固まるタイミングとGCのタイミングは完全に一致した。
ログを見るとGCの他にCCというものが頻繁に発生しており、これはCycle Collectorというものらしい。Firefoxは、JSオブジェクトのGCにはmark & sweepを、DOMオブジェクトのGCにはreference countを採用しており、reference countでは循環参照を回収できないので、cycle collectorで循環参照しているgarbageを回収するようだ。なぜこのような形になっているのかはちょっとよくわからない。どうせstop the worldしてしまうなら、全部mark & sweepじゃダメなのだろうか。そんなに性能差が大きいんだろうか？
CCはcollected: 0、つまり何も回収できなかったというケースが非常に多くあるようだ。しかもGCよりもはるかに頻繁に起動されており、とてもうざったい。いろいろ操作して見ながら観察してみたところ、DOMツリーを変更しそうな操作をしない限り、CCではオブジェクトを回収できないようだ。まぁ、DOMを構成するオブジェクト（のうち、循環参照を起こしているgarbage）を回収するためのものなのだから、当たり前と言えば当たり前である。
ある一つのDOMが確保するメモリチャンクは通常はそれほど大きくならないと思うので、CCの処理はもっと細切れにできないものだろうか、と思う。さすがにコードを読んでるほどの暇は今は残念ながらないのでそこら辺はよくわからないけど。
パープルバッファを世代別にすることでポーズタイムを短くするという話があったりとかする。しかし、既にmark & sweepをincremental化するという計画があるのならば、そっちに乗っかるのが一番早いのではないかという気がしている。
xinputを使ってタッチパッドをオフにする
自宅では4年前に買ったmacbookにubuntuを入れて後生大事に使っているのだが、最近タッチパッドが暴走して、左ボタンがずっと押されっぱなしになるという事態が増えてきた。
gpointing-device-settingsでタッチパッドをオフにしてみたのだが、勝手にタッチパッドが復活して暴走するという問題が何度か起きた。さすがにハードウェアの暴走だけあって、何が起こるかわからない。
xorg.confの方でオフにすることで勝手に復活という最悪の事態をなくせるのではないかと思って試してみたのだが、設定がよくわからない。昔はHALでなんかXMLをいじればオフにできたような気がするのだが、もうHALはどこかへ行ってしまったしね…。
xinputコマンドを使うことでうまいことタッチパッドをオフにできたみたいなので、メモしておく。
まず、xinput listでデバイスを見つける。今回はmacbookだからか、appletouchという名前だった。これをオフにしたいのだが、オン/オフもプロパティの一部らしい。という訳で、xinput list-props appletouchしてみると、
Device Enabled (154): 0
という行があった。154番がオンオフの制御のようだ。最終的には以下のコマンドでタッチパッドをオフにできた。
xinput set-prop appletouch --type=int 154 0
evinceでuimが使えない問題を解決する
いつごろからか、evinceで日本語が入力できなくなっていておかしいなと思っていたのだが、最近になってAppArmorが原因であることに気づいた。
ubuntuで AppArmor を使ってセキュアな環境を構築する を参考にしてevinceでuimを使えるようにすることができた。その作業結果をメモしておく。
sudo apt-get install apparmor-profiles apparmor-utils
aa-genprofでまずプロファイルを作るものらしいが、evinceの場合は既にprofileが存在したのでそれは要らなさそう。aa-complainで学習モードへ変更する。
sudo aa-complain /usr/bin/evince
ここでevinceを起動して、日本語を入力してみたりしておく。aa-logprofでプロファイルを保存する。
sudo aa-logprof
Would you like to enable access to the profile repository?とか聞いてくるので(E)nable Repositoryを選択して、後はAllowで通して最後にSaveする。
最後にaa-enforceでenforce modeに戻しておしまい。
sudo aa-enforce /usr/bin/evince
SVMの正則化項がマージン最大化のために必要な理由
ラージマージンとマージン最大化について2回ほど書いてきた。
あの後もSVMとマージンパーセプトロンについてうだうだと考えていたのだが、もうちょっとシンプルな説明を思いついた。
SVMの特徴はヒンジロスを採用している点と、正則化項があるところである。
ヒンジロスはもう何度も出てきているが、max(0, 1-ywx)みたいな奴で、1-ywx<=0の時にだけ損失を0とするものである。
正則化は、wの各要素をできるだけ0に近づけようとする力で、要するに、この力に打ち勝つだけの価値を持つ素性だけが生き残れる。マージンパーセプトロンとSVMの大きな違いは、この正則化項のあるなしである。
前回は、ALMAの論文を持ち出してマージンパーセプトロンは近似的な最大マージンでしかない、と書いたが、そもそもSVMは最大マージンなのか。とりあえず、ヒンジロスだけで正則化項が存在しない場合（つまり、ほぼマージンパーセプトロンだ）を考えてみよう。
ヒンジロスはywxが1以上の値を取った場合に損失が0になるので、この場合、マージンを最大化せずに損失が0になる例を考える事ができそうである。例えば、以下の図を見ていただきたい。
この図の○と×はデータを表している。この図の緑は現在のパラメーターにおける識別超平面を表すことにしよう。だいたいy = 0.2x - 3 ぐらいかなぁ。で、ywxは1以上の値をとるだろうか？
答えは「wには自由度があるのでこの図からはわからない」ということになる。言い換えると、ywxがどちらのデータに対しても1以上の値をとるようなwを考えることができる。
そうすると、この緑の状態でもう損失は0になってしまっているので、学習はもう進まない。マージンパーセプトロンの場合、ここでおしまいである。
で、次に正則化項をつけてみよう。正則化項をつけてFOBOSで最適化した場合、各ステップでwのそれぞれの要素の値をちょっと減らして、0まで減らしたらそこでおしまい、ということになる。式で書くと、
w_{i+1} = sign(w_i) max(|w_i - lambda|, 0)
となる。（ただし、lambdaは適当な正の実数とする。）つまり、損失が0になった状態で学習を進めると、wの各要素の値はモリモリと小さくなっていく。
wの各要素の値がモリモリと小さくなっていくと、当たり前だがywxの値はどんどんと小さくなる。そうすると、また損失が正の値を取り、パラメーター更新が発生し、分離超平面が動くことになる。そして正例と負例のせめぎあいが発生し、マージンが最大化される。
という訳で、正則化はマージン最大化のために本質的に必要な要素である、という事ができる。（ないとマージンが最大化されないことがある。）
前回、マージン最大化にはマージンとして0より大きな実数を要求することが必要であると書いたが、今回得られたこの情報を合わせて、マージン最大化には
- マージンとして0より大きな実数を要求すること
- 正則化項があること
の2つが必須である、と言えよう。
おまけ。私の認識に従って分類表を書くと、以下のような感じになる。
| 正則化なし | 正則化あり | |
|---|---|---|
| ywx> 0 | パーセプトロン | 正則化つきパーセプトロン |
| ywx>= λ | マージンパーセプトロン | SVM |
私の認識では、この中でラージマージン、マックスマージンを名乗っていいのはSVMだけで、マージンパーセプトロンはラージマージンである。パーセプトロンと正則化つきパーセプトロンはマックスマージンとラージマージンのどちらでもない。SVMがマージン最大化であることは論を待たない。マージンパーセプトロンがラージマージンとしたのは、非常によく似たアルゴリズムであるALMAがラージマージン（論文中の表現では、マックスマージンの近似）であるからだ。
本稿ではラージマージンについては「マージンを最大化まではしないけど、なんか大きくする感じの奴」という意味合いで使いました。
sshを使いこなすための7つの設定
五月病が抜け切らないIT系新入社員に贈るシリーズ第1段。
~/.ssh/configにはいろいろな設定が書けるが、周囲を見渡した限り、あまり活用されているようには見受けられない。そこで、今回は便利な設定をいくつか集めてみた。
長いホスト名に短い名前をつける
Host exp1
HostName verrrryyy.looooong.hostname.example.jp ssh verrrryyy.looooong.hostname.example.jpの代わりにssh exp1でログインできるようになる。
ちなみに、zshの場合、configファイルに登録されたホスト名はsshコマンドを打つときに補完されるので更に便利。
特定のホストへログインするときのユーザ名や鍵をカスタマイズする
Host github.com
User tkng
IdentityFile ~/.ssh/id_rsa2 githubに登録してある鍵は普段使う奴と違うんだよね、みたいな場合に使う。
ここまでくると大体想像はつくだろうが、ポート番号などもカスタマイズできる。
放置してても切断されないようにする
10分ぐらい通信をしていないと、ルーターが勝手に接続を切ってしまったりするので、パケットを送って接続を維持する。
ServerAliveInterval 60
Debian系のOSだと独自のパッチが当たっていてProtocolKeepAlivesという設定ができたのだが、ServerAliveIntervalの方がどこでも使えて汎用性が高いようだ。何時頃からServerAliveIntervalなんて設定が増えたんだろう…。
コネクションを複数のターミナルで使いまわす
Host * ControlMaster auto ControlPath /tmp/%r@%h:%p
同一ホストに複数のターミナルから接続する場合、1本のコネクションを使い回してくれる。特にパスワードログインしかできない場合など、2回目以降はパスワードを打たなくて良いので便利。
時間のかかる認証方法を無効化する
Host example1
GSSAPIAuthentication no公開鍵認証の前にGSSAPI認証とかいうのを試すせいでログインにやたら時間がかかる…みたいな場合にこの設定を行うと、さっさと公開鍵認証をしてくれるようになってつながるまでの時間が短くなる。
多段ログインの設定
前に書いたのでそちらを参照。
ProxyCommandを使う。理論上は無限に多段ログインができる。
SOCKSプロキシ機能を提供する
Dynamic Port Fowardを使って、特定ホストへのアクセス（ポートで識別するんじゃなく、ホスト名で識別するところがポイント）だけをsshのトンネル経由でアクセスさせることができる。これも前に書いた。前に書いたときにはGoogle Chromeは対応してなかったけど、もう今では完璧に対応している。
Web APIを開発している時とか、ブラウザからちょいとテストできるとすごい便利。
emacsのマウスホイールでのスクロールを1行単位でかつホイールのあるところを動かす
emacs24は字句的スコープが導入されるらしい。4/1にlexcal scopeブランチがマージされたそうだ。デフォルトだとDynamic Bindingのままで、-*- lexical-binding: t -*-って書いたファイルだけがlexical bindingになるみたい。
emacsではmwheel-follow-mouseを設定しておくとマウスホイールのあるウィンドウのところでスクロールしてくれるのだが、一度にスクロールする行数の方をカスタマイズしようとすると世間に出回っているカスタマイズのコードと両立できなかったので、mwheel.elを参考にしつつ自分で書いた。
.emacsに以下の設定を書くとそのような動作になる。scroll-up 1のところをscroll-up 3とかにすれば、3行単位でのスクロールになる。
; scroll by wheel (mouse-wheel-mode t) (defun scroll (event direction) (let ((curwin (prog1 (selected-window) (select-window (mwheel-event-window event))))) (if (eq direction 'up) (scroll-up 1) (scroll-down 1)) (if curwin (select-window curwin)))) (defun scroll-down-with-lines (event) "" (interactive "e") (scroll event 'down)) (defun scroll-up-with-lines (event) "" (interactive "e") (scroll event 'up)) (global-set-key [mouse-4] 'scroll-down-with-lines) (global-set-key [mouse-5] 'scroll-up-with-lines)
明らかにもっと短くできそうなコードだけど、あんまり手間かけてもしょうがないしまぁこんなもんでしょう。
Lisp書くのは久しぶりだったが、やはり書くのは楽しい。読むのはあまり好きではないけど。
パーセプトロンはマージン最大化の夢を見るか？
前回の記事は長くなりすぎたので、長文を読みたくない人のために、まず三行であらすじをまとめる。
- ソフトマージンSVMがマージン最大化してるって言うけど、ちゃんと理解するの結構難しくない？
- なんか自分の中で議論を進めると、正則化項つきパーセプトロンもマージン最大化に分類されるんだけど大丈夫？
- こうなったらもう、正則化項つきパーセプトロンを実装して、実験してみるしかない…次回に続く
という話であった。
さて、前回の落ち穂ひろいから始めよう。前回「マージン最大化はSVMの特権ではなく、MIRAとかAveraged Perceptronとか、ラージマージン分類器と呼ばれる分類器はいくつもある」と書いたが、ここでは、「マージン最大化」という概念と、「ラージマージン」という、似たようだが違うかもしれない概念が混同して提示されている。どうも、この二つの用語は分けて考えた方が良さそうに思える。
その観点からググッた結果、echizen_tmさんのコメントが見つかった。どうやら、同じことを考えている人は他にもいるようである、という事でやや安心をして、議論を先に進めることにする。
「マージン最大化」と「ラージマージン」を分けて考えるとして、それぞれの単語の定義はどうなるのだろうか。まずは「マージン最大化」の方から。
ここでは、もう一度ソフトマージンSVMの目的関数を思い出してみることにする。ソフトマージンSVMでは、
- マージンをはみ出るものにはペナルティを与える
- マージンをはみ出なかったものに関しては、ハードマージンの場合と同じくマージンを最大化する
という二つの項の和を最適化するのであった。
「マージンをはみ出る」とは言うが、これは具体的にはどういう場合を指すのだろうか。分離超平面を超えなければはみ出てはいない…ように思えるが、数式をよく見ると、分離超平面からある程度の余裕を持って正しく分類されていない場合はペナルティが課せられる。いわゆるヒンジロスという奴である。
あれ、そもそもなんでこういう形になってんだっけ、という事を考えると、ハードマージンSVMの時の制約に思い当たる。ハードマージンSVMには以下のような不等式制約がある。
y w.cdot(x) >= 1
ハードマージンSVMでは|w|とか|w|^2を最小化するわけだが、これがマージンの最大化になるというのは、上記の不等式制約があっての話である。今手元に教科書がないので適当なことを書いてしまっているかもしれないが、マージンの値はy(w・x + b)として書けるが、wを定数倍することでこの値は自由に調整することができるので、サポートベクターのマージンを1と決めてしまうと、|w|の最小化がマージンの最大化になる、という話なのであった。>= 1の= 1の部分がサポートベクターの場合を表しているということになる。
wをスカラー倍することでマージンの値は操作できちゃうので、サポートベクターのマージンを「0.5」に決めてしまったり「3.14」に決めてしまったりしても、上記と同様の議論は成り立つ。ただ、0にしてしまうとマージンの値が0になってしまうのでそれはよくない。0より大きな実数にする必要がある。
パーセプトロンの場合はここが0になる訳で、それが意味するところはマージンを最大化していない、ということである。wを無限倍することを考えるとSVMと同様の議論が成り立つ可能性はあるが、そこを追求することにあまり意味もなかろう。
という訳で、当初の「正則化項つきパーセプトロンもマージン最大化に分類されるんだけど大丈夫？」という疑問に対する答えは「正則化項をつけたところでパーセプトロンはマージン最大化になりません」ということになる。違う、という結論が出てしまったので、実験は行わないことにする。
まとめると、
- マージン最大化には、マージンとして0より大きな実数を要求すること、|w|（か|w|^2）の最小化、の2つの条件が必要である。もしくは、これと等価な条件を要求しなければならない。
- 正則化項つきパーセプトロンの場合は前者が満たされていないのでマージン最大化にはなっていない
- 要するに前回の話には誤りが含まれている
という話になった。
世間ではよく「正則化=マージンの最大化」という扱いがされているような気がするのだが、「マージンとして0より大きな実数を要求すること」という条件も、（分かっている人には自明なのかもしれないけれど）もっと強調された方がいい、と思った。
ではマージンパーセプトロンの場合はどうなのか
と、ここまでで終わろうと思ったのだが、マージンパーセプトロン（Perceptron with Marginsの方が一般的な表記のようだが、カタカナで書くと長すぎるので以下マージンパーセプトロンと表記する）とかはどうなんだろう、という疑問が湧いてきたので、まとめを書いた後だがもうちょっと話を続けることにしたい。
マージンパーセプトロンというのはパーセプトロンで条件分岐の式をy w.cdot(x) >= λ みたいな形に書き換えたものである。ただし、正則化項はついていない。マージンパーセプトロンに正則化項をつければ、上記の議論からはマージン最大化の範疇に入ると言えそうだ。
ところで、これまでいくつか実験してきた際の実感としては、マージン最大化に重要なのは|w|の最小化よりもむしろマージンとして0より大きな実数を要求すること、の方であるように思われる。
そこで、調査班はさらなる文献の調査を続け、とある論文において以下の重大なフレーズを発見した。というか、Abstractの一行目に書いてあった。"A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ≥ 2 for a set of linearly separable data." つまり、この論文では最大マージンの近似を行うオンライン学習アルゴリズムが記述されている。この論文はALMAというアルゴリズムの元論文であり、そもそもALMAという名前自体が「Approximate Large Margin algorithm」の頭文字を取ったものであるようだ。
ALMAとマージンパーセプトロンは学習率の計算とかマージン(？)の計算とかでALMAの方がちょっと凝っているが、ほぼ同じものである。ここから、ALMAもマージンパーセプトロンも、「Max Marginの近似になっている」と言えそうだ。（本当に言いたかったらマージンパーセプトロンの方は証明が必要だが…）
ALMAの名前からすると、Max MarginもLarge Marginも用語として明確な区別はないけれど、学習ループを何回も回した際に最終的に収束先がマージン最大化であればMax Margin、マージン最大化の保証がなければLarge Margin、ぐらいの使い分けをしてもいいのかなぁ、という気がした。
ついでに、Passive Aggressiveのアルゴリズムもマージンパーセプトロンとほとんど一緒で、違うのは現在のサンプルを正しく分類できるように大きく動かすというところぐらいなので、Max Marginの近似（上記の使い分けをするならLarge Margin）と言ってよいだろう。（しつこいがこれも言いたければ本当は証明が必要だよ）
以下、後半をまとめる。
- マージン最大化には、マージンとして0より大きな実数を要求すること、|w|（か|w|^2）の最小化、の2つの条件が必要である。もしくは、これと等価な条件を要求しなければならない。
- マージンとして0より大きな実数を要求することで、マージンを最大化とまではいかなくても、マージンを大きくする効果があるので、Large Marginと呼んで良いのではなかろうか。ただし証明は今のところない。
なんか、当初の自分の実感とほぼ同じようなところに議論が着地したのでちょっとホッとしているのだが、連休明けぐらいに「間違ってるよ」とかコメントがつきそうで怖い。でも間違ったまま放置してしまうのはもっと怖いのでみなさんガンガン突っ込んでくださいね！
参考リンク
- TokyoNLP#5で「パーセプトロンで楽しい仲間がぽぽぽぽ〜ん」を発表しました
- Perceptron with Marginsについてはこの資料で参照されていたので辿ることができた
- A New Approximate Maximal Margin Classification Algorithm
