Engineering the LOUDS Succinct Tree Representation - 射撃しつつ前転 改
Engineering the LOUDS Succinct Tree Representation(O. Delpratt et al., 2006)を読んだ。モチベーションとしてはTxの実装ってどういう風になってるのかが知りたかったというのがある。 LOUDSというのは順序木を効率的に実装するためのアルゴリズムで、この論文ではさらにそれを改良したLOUDS++というのを実装・提案している。 基本的なアイデアは、木の上の方から、ノードに存在する子ノードの数だけ1を並べる。デリミタは0。（まぁ、1と0が逆でもいいんだけど。）そうすると、それぞれの1とノードの対応が取れるようになる。このビット列をLBSと呼ぶ。LBSに対してis_leaf, parent, next_siblingなどの関数が実装できれば順序木が実現できる訳だけど、これらの関数はそれぞれ数個のrank, select操作で実
Confidence Weighted Linear Classificationを読んだ - 射撃しつつ前転 改
ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。 Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。 こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
