Preferred Research サマーインターン2011問題を解いてみた

http://research.preferred.jp/2011/07/intern2011_problem/

基本方針: 異なる種類の文字同士を見つけて消去して、最後に残った文字の種類を出力する。

出現回数が最大の文字をaと呼ぶことにする. aの出現回数はn/2より大きい、別の言い方をすれば、a以外の文字の出現回数の合計はaの出現回数よりも小さい。そのため、異なる種類の文字同士を見つけて消去していくと、仮に消去の組み合わせの一方が全てaだったとしても、文字種が1種類になるときには必ずaが残る。

文字列をstrとすると、回答は以下:

i = 0
j = 1
while j != n
  if str[i] == str[j]
     j += 1
  else
     str[i] = ILLEGAL_VALUE
     str[j] = ILLEGAL_VALUE 
     while str[i] == ILLEGAL_VALUE 
    //while str[i] != ILLEGAL_VALUE 6/29 10:08追記 逆でした
       i += 1
     end
     j = MAX(i +1, j+1)
  end
end
return str[i]

使用しているバッファ量: 2 * log_2(n)
計算量 O(n) (iもjも手戻りが無いため)

輪番停電について

地区毎に順番に停電を計画的に起こす、輪番停電が実施されます。
収集した限りの情報を公開します。この情報は23時30分時点の情報です。古くなっている可能性があります。

地区グループに関して


東京電力は会見で「東京23区は荒川区の一部以外対象になっていない」としていましたが、公表しているHPには別の区も含まれています。記者の方が指摘されましたが、どちらが正しいかは判明しませんでした。どちらであっても大丈夫なように行動してください

重複する地域に関して

停電は送電線単位でやるので、 どの区域にどの線から電気が行ってるか分からない地域は複数の場所に名前を載せるしかないそうです。 これは東電さんも分からないので電話しても仕方ありません。 2日目からは自分がどの区域なのかわかると思うので、それまで待っててあげてください。

3月14日の輪番に関して

第1グループ 6:20〜10:00のうち3時間程度
第2グループ 9:20〜13:00のうち3時間程度
第3グループ 12:20〜16:00のうち3時間程度
第4グループ 13:50〜17:30のうち3時間程度
第5グループ 15:20〜19:00のうち3時間程度
第1グループ 16:50〜20:30のうち3時間程度
第2グループ 18:20〜22:00のうち3時間程度

第一グループ及び第二グループの2回目は、実施するかどうかは当日の電力の需給量で決まります。

計画停電交通系への影響

道路交通信号は止まります。 電車は都心部は鉄道会社が独立した電源系を確保していますが、 地方部(たとえば千葉の奥の方)とかは運行自体に影響が及ぶ可能性があります。

その他

  • 言うまでもないかもしれないけど、輪番停電になりそうな時間になったら、みんなくれぐれもエレベーターに乗らないで!閉じ込められるのが一番怖い。
  • 冷蔵庫は3時間くらいなら閉じておけば大丈夫だ問題ない


http://gigazine.net/news/20110313_rolling_blackouts/

Confidence Weightedの挙動を見てた

理論は理解したつもりになって、実装してみたは良いものの、なかなか正体が見えないので、パラメータの更新量を調査してみることにする。

ブログで上手く紹介できないかとと計算機サービスを探してみたところ、instacalcというWebサービスを発見。早速入力してみた。

http://tinyurl.com/mgo69o

M_iはmean margin。パラメータと重みの線形和。|M_i|はi番目の事例がどれだけはっきり分類されているかを解釈することができる。負であれば正解ラベルと分類されたラベルが逆。
V_iはvariance margin。事例に出てきた素性の出現回数が少ないと素性に対応する分散は大きい値になる(出現するごとに分散は小さくなっていく)ので、V_iが大きい値になるということは、事例の素性が余り出てきていないと解釈することができる。ということはV_iはi番目の事例が目新しいほど高い値を示していると考えることが出来そう。こちらは正値のみ。

Cはconficdence parameter

alphaがM_i, V_i, Cを元に算出された更新量


V_iが大きくなるとalphaも大きくなる。これは、目新しい事例だと大きく更新してやろうとする、CWの計算通り。
M_iが正値で大きくなると、alphaは0になり、M_iが負値で小さくなるほどalphaは大きい値になる。事例とラベルが同じだとほとんど更新せず、逆だと大きく更新してくれる。
また、Cが大きいとalphaも大きくなる。Cが大きくなれば更新量も大きい

以上をまとめると、分類が誤っていた時、また分類が正しかったとしても目新しい事例を受け取った時はパラメータを大きく更新し、正しくて目新しくもないときはパラメータの更新量を小さく、もしくは全く更新しないようにする、ということになる。そして、その更新量はCにより制御できる、と。解析すればするほどよくできてる分類器だということが分かる。

んーでも、正例と負例の割合が偏ってる場合はどうなるんだろう。例えば負例がすごい多くて、久しぶりに正例が出てきた場合、既に目新しくない事例だとCWに理解されて全然更新されなくなってしまうという事態がおこる可能性が十分ありうる。インスタンスの値を上手く調整してやる必要が有りそうだ。

Confidence Weighted Linear ClassificationをRubyで書いてた

つい最近、機械学習勉強会でConfidence Weightedを読みました。理論はラグランジュで引っかかってしまいましたが、そこ以外はつまること無く読めました。

せっかく読んだのでRubyで実装してみました。といっても、ぜんぜん難しくない。ホント実装簡単すぎる。せっかくなのでオープンソースとかで公開してみたいけれどもどうやったらいいかさっぱり。。。


勉強会では、なぜ1回で学習が収束するのかを議論にしてみました。僕は、分散の値が学習される毎に小さくなっていくため2回目以降の学習によるパラメータの更新量が小さくなるのではないかというのと、Perceptronとは異なり、分類が誤ったからといってその事例が必ず分類できるようにをするわけではないため、他の事例によって元の事例が分類できないパラメータになる可能性が低くなるのではないかと主張してみたけど、すっきり筋の通る説明になっていないのでうーんという感じ。

CWはカーネル化が難しい(moritaさん曰く)ので、そこなんとかならないかなぁと思ったり思わなかったり。

あらゆる仕事はインフラになる

研究のプログラムが上手く動作しなくてむしゃくしゃしているので、適当に今思っていることを書きなぐる。

営業だろうと企画だろうと開発だろうと研究だろうとなんだろうと、仕事とは人が嫌がることを代わりにやってお金を頂くことです。それが自分にとって楽しいことかどうかは関係ない。そして、仕事とは常にパイが減るものです。それはコンサルティング業界やらIT業界、研究職という業種/職業が存在する以上、避けられないこと。

ただ、パイが減らないように見える業種もあります。例えば、ゲーム業界、テレビ業界、風俗なんかもそうですね。彼らは需要を生みだすことによりパイを増やし続けています。

しかし、需要を生み出すということは何かしら目新しさが必要。それは、人間全体にとってではなく、本人にとってであれば良いけれども、でもそういうものが必要。だからテレビもゲームも既にインフラになりつつある。

この間のInprotの夏野さんとひろゆきの講演を公聴させていただいたのだが、ひろゆきが「TBSは軒並み視聴率を落としたが、その中で一番視聴率が高かったのは再放送の水戸黄門だった」というお話がありました。

夏野
 過去に、TBS が番組改編して、60%を生放送にしたんですね。

 そうしたら視聴率が激減。

 ちなみに、再放送の水戸黄門が一番だったそうで。

 (会場爆笑)

6/12「インターネットの未来像:ポストインターネット」(夏野×ひろゆき)2

あれ、これひろゆきの発言じゃなかったっけ。まあいいや

これはTBS現在あまりよろしくないことを意図して出た発言ではありますが、もう一つ見逃せない事実があります。面白い作品は何度も見られるということです。
だからゲームもリメイクが売れるのも当然。


ということを考えると、最終的に残るのは新しい企画を打ち出してくことではなく、いかにして良いものを継続的に売っていくかになります。ゲーム業界も今は右肩上がりですが、必ずパイは下がっていきます。

このことは、畑村洋太郎先生も「技術の創造と設計」という本の中でおっしゃっております。

すべて産業の成長と衰退は、この図に示すような飽和曲線を描くのである。
(中略)
すべての産業は、生産量が少ない「萌芽期」、増えていく「発展期」、だんだんと増えなくなっていく「成熟期」。そして減っていく「衰退期」という4つの時期を通る。そして、非常に不思議なことだが、萌芽期の終わりから成熟期の終わりまでの期間は、どんなに産業かに関係なく、約30年になっているのである。

技術の創造と設計

このことを事実として捉えるのならば、例えばゲーム業界であれば、ファミリーコンピュータが登場した1983年を萌芽期の終わりとするならば、衰退期に入るのは2013年ごろとなります。今、ゲーム業界は空前の人気業界ですが、その人たちが働きざかりになるころには、ゲームを作り出す人たちのパイの減り方が半端なくなっていると思います。事実、テレビは既に衰退してきてますよね。少なくとも新しいことを生み出すことに関しては、かなり弱くなってきていると思います。

であれば、ゲームを作り出す人たちになるより、ゲームを継続的に提示する側になるほうが賢い。ただし、継続的な顧客が見込めるような方法で。だからリメイクは強い。某N社には内定を頂いた友人がいるので、ちょっと心配。ま、めっちゃ面白くて、頭の良い彼なら大丈夫だとは思うが。

近代?は研究はお金持ちが有り余った時間を使って趣味でやるものだったわけだが、現代もそう遠くない未来、同じようになるだろう。昔は手法が確立してなくて、現代は研究する領域がなくてと理由はことなるものの、結局のところ同じ状況になるだろう。

だから、会社としてもう残っている領域は、どのようにインフラを提供していくかになってしまう。ゲームも新しく作り出すことより、例えば過去のゲームを一緒にやっている感覚の共有に価値を見いださせることにより、継続的な収入を得る方向性に変えていかなきゃならない。プラットフォームビジネスとかまさにそんな感じだし。作る側は殆ど趣味であることが正しくて、時々ヒット作品が出て、そこから新しい発展がおこるかも程度で良いんじゃないかしら。製品をオープンソースにして、講習会でお金を取っているとかも同じですよね。

向いてることを仕事にし、好きなことは趣味でやろうということになるんでしょう。だから、需要を生み出し続ける業種につとめることは良い選択では決して無い。売り抜くことで一生過ごせるだけの収入が得られるのであれば良いが、そうでなければやめて、安定している企業に入るべき、と思う。

そして僕は博士後期課程を志しているという矛盾。はぁ。