ブログ執筆中 このページをアンテナに追加

2011-07-28

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も手戻りが無いため)

2011-03-13

輪番停電について

地区毎に順番に停電を計画的に起こす、輪番停電が実施されます。

収集した限りの情報を公開します。この情報は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/

2010-07-13

テストテスト

あーあーあーマイクテスト

2009-07-26

インターン全ダメだった

もう少し早く動くべきだったね。夏休みどうしようかな

来年にむけて英語でも勉強しますか。未踏でも準備しますか。

2009-07-25

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に理解されて全然更新されなくなってしまうという事態がおこる可能性が十分ありうる。インスタンスの値を上手く調整してやる必要が有りそうだ。