~matubara/ChangeLog / 2006-06 →移動しました

■ shibata(hi) shokudou -- coLinuxでデュアルブートマシンをいじる [linux][win][net]

<http://hoop.euqset.org/archives/001086.html>
Linux が入ってる実パーティションをルートにして、
coLinux で起動する。

色々めんどくさそうなことが書いてあったけれど、
実は最新の coLinux だと、すごく簡単。

<?xml version="1.0" encoding="UTF-8"?>
<colinux>
    <block_device index="0" path="\DosDevices\e:\programs\coLinux\root_fs"  enabled="true" alias="hda6"/>
    <block_device index="3" path="\DosDevices\e:\programs\coLinux\root_fs3" enabled="true" alias="hda7"/>
    <block_device index="5" path="\Device\Harddisk0\Partition4"             enabled="true" alias="hda5" />
    <block_device index="1" path="\DosDevices\e:\programs\coLinux\swap_device" enabled="true" />
    <cofs_device index="0" path="\DosDevices\e:\" type="flat" enabled="true" alias="hda3"/>

<bootparams>root=/dev/hda5  fastboot=yes</bootparams>
    <initrd path="initrd.gz" />
    
    <image path="vmlinux" />

    <memory size="256" />

    <network index="0" type="tap" name="TAP" />
</colinux>

<block_device ... /> は、
ディスクイメージも、物理パーティションも、
（Windows で使用中の）Windows ドライブもマウント可能にする。
PartitionXという番号は、Linux側とは一致していない。
拡張パーティションとかスワップを数えてないらしい。
diskpartというWindows XP 付属のCUIツールを使って見られる番号を入れる。

あと、カーネルの起動パラメタをいじる。

カーネルが違うので、モジュールを置いておかないといけない気がするが、
coLinux カーネルは自分でモジュールを展開するらしい。

ネットーワークの手順再掲。

通常使用している ネットワークの接続 -> プロパティ -> 詳細設定 -> インターネット接続の共有

でTAPを選ぶ。
ここで TAP のIPアドレス設定が上書きされてしまうので、
設定しなおす。

書き忘れていたが、
/etc/resolv.conf
を書く必要があったと思う。
Windows からみえるDNSサーバーと同じでいい。

■ Fibonacci number - Wikipedia, the free encyclopedia [math][net]

<http://en.wikipedia.org/wiki/Fibonacci_number>
フィボ進数も。
エジプト式掛け算との対応とか

エジプト式掛け算：19x65

  halve double odd?
    19 65 +
     9 130 +
     4 260
     2 520
     1 1040 +

+の付いてる double の値の和が答え。

halve と double を2進数にすると、
当たり前だった。

2進数だと二倍を計算できないと、掛け算ができない。
フィボ進数なら、（trivial な方法よりは少ない回数の）足し算だけでできる。

■ Computational Infrastructure for Operations Research Home Page [opt][net]

<http://www.coin-or.org/index.html>

COmputational INfrastructure for Operations Research

Ipopt - Trac（内点法による微分可能NLP）など。
[2006-06-22-3]

■ Simple Repeater `stone' [linux][net]

<http://www.gcd.org/sengoku/stone/Welcome.ja.html>
software repeater

■ zshのある暮らし - FrontPage [linux][howto][net]

<http://www.ex-machina.jp/zsh/index.cgi>
screen番号をプロンプトに表示するのは便利。
bashでもできたのかな？

■ Subversion のリポジトリの引越し [svn]

基本的には、svn move URL URL をして、 新しく svn checkout で完了、のはず。
でも、全部コミットしないまま move した場合、
.svn/entries に書かれているリポジトリパスを書き換えればよい。

find . -name entries | xargs perl -pe's/.../.../'

で問題なさそうなら、perl -i に変えて実行。（フィルタ動作ではなくファイル上に書き込む）

■ Introduction to Mathematical Programming from the Viewpoint of Interior-Point Methods [opt][net]

<http://www.is.titech.ac.jp/~kojima/articles/b-349.pdf>
数理計画法の内点法のイントロ。
中身は日本語。

■ CFSQP? [opt]

制約条件が線形で、目的関数が対数線形。
どんなソルバーが使えますか？

CFSQP?
http://www.math.pitt.edu/~thales/dodec/code/cfsqp/
http://www.aemdesign.com/download-cfsqp/cfsqp-manual.pdf

線形計画には含まれないが、
非線形計画とか線形制約非線形計画は条件が広すぎる。

■ Pronunciation of mathematical expressions [math][lx][net]

<http://www.math.helsinki.fi/engl.html>

■ INSERTION SORT is O(n log n) (ResearchIndex) [algorithm][net]

<http://citeseer.ist.psu.edu/bender04insertion.html>
未使用領域つき挿入ソートの挿入が、高い確率で O(n log n)

■ h-sequence [perl]

下記の構文にしたがって、受理非受理を決定

h = 0 | 1 h h

LL(1)文法であり、1文字先読みで決定的（バックトラックなし）で解析を進めることができる。

use strict;
use warnings;

my @a = grep /[01]/, split //, scalar <STDIN>;

sub f($$);
sub f($$) {
  my ( $n, $p ) = @_;
  print "$a[$n] $n $p\n";
  scalar <STDIN>;
  if ( $n == $#a ) {
    return $p == 0 && $a[$n] == 0;
  }
  if ( $a[$n] == 0 ) {
    {
      f( $n + 1, $p - 1 );
    }
  } else {
    {
      f( $n + 1, $p + 1 );
    }
  }
}
print f( 0, 0 ) ? 'true': 'false';

■ Saving Emacs sessions [emacs][net]

<http://www.phys.ufl.edu/docs/emacs/emacs_423.html#SEC430>
.emacs に

(desktop-load-default)
(desktop-read)

保存したいセッションの状態で、

M-x desktop-save

■ Perl::Tidy [perl]

perl のフォーマッタ。

perltidy -st -se

で標準入力、ファイル引数から標準出力へのフィルタとして働く。

@a=qw/1 0 1 1 0 0 0/; sub f($$) {($n,$p)=@_; return 1 if($n==$#a&&$a[$n]==0&&$p==0); return 0 if($n==$#a); \
if($a[$n]==0){ if($p>0){f($n+1,$p-1)}else{$n==$#a} } else{ f($n+1,$p+1) }}\
print f(0,0)?'true':'false';

↓

@a = qw/1 0 1 1 0 0 0/;

sub f($$) {
    ( $n, $p ) = @_;
    return 1 if ( $n == $#a && $a[$n] == 0 && $p == 0 );
    return 0
      if ( $n == $#a );
    if ( $a[$n] == 0 ) {
if ( $p > 0 ) { f( $n + 1, $p - 1 ) }
else { $n == $#a }
    }
    else { f( $n + 1, $p + 1 ) }
}
print f( 0, 0 )
  ? 'true
'
  : 'false';

# h = 0 | 1 h h という構文（hは非終端記号）で定義される言語の判定器
# strict な末尾再帰による実装
# 動いてるのかこれ。

■ sideset in amsmath [latex]

■ π ノート [math][net]

<http://www.math.meiji.ac.jp/~mk/labo/text/pi.pdf>
数値計算系の話。

■ TeX Frequently Asked Questions -- question label "algorithms" [latex][net]

<http://www.tex.ac.uk/cgi-bin/texfaq2html?label=algorithms>

■ Convex Optimization / Boyd and Vandenberghe [math][opt][net]

<http://www.stanford.edu/~boyd/cvxbook/>
凸最適化の本。
線形計画とか含む。

■ RAMP2006 [opt][net]

<http://www-or.amp.i.kyoto-u.ac.jp/ramp2006/>
10月、京都。岡本先生の講演がある。

■ learn.perl.org -- Beginning Perl [perl][book][net]

<http://learn.perl.org/library/beginning_perl/>
入門書、PDF。
割とちゃんとしてると思う。

■ Document Space [nlp][lm][net]

<http://www.ipam.ucla.edu/schedule.aspx?pc=ds2006>
テキストモデリング関係の理論のワークショップ。
MP3の録音とか公開されてる。

■ Language Modeling with the Maximum Likelihood Set -- Complexity Issues and the Back-off Formula [lm][stat]

<http://www.ipam.ucla.edu/publications/ds2006/ds2006_5861.pdf>
Maximum Likelihood Set [2006-04-06-4] 応用の解説プレゼン。

最尤推定では、単体上で格子状の点集合のどれかしかとれず、
周縁に位置することにより、0確率がたくさんできてしまう。

可能な点集合（確率分布の集合）は格子状だが、
観測データはそのなかの1点となる。
MLSはそれを囲むある領域のこと。
直感的には、平面の多角形（超平面の凸多面体）分割で、最近傍サイト共有クラスタという感じ。
その多角形の中の点のうち、参照分布の点に一番近い点を解とする。

参照に使うのは、最尤推定とかだと悪いところをそのまま受け継いでしまうので、
スムージングされた分布か、
次元がすごく少ない分布がいいかも。
逆に言うと、そういう参照分布しか手に入らないような場合に有効な気が。
ドメイン適応とか。

実験結果では、
Modified-Kneser-Ney などと比較して、それを参照分布としたときのMLS法は、
パープレキシティ、WERで、
よくなったり悪くなったりという、いまいちな結果。

MLSの領域基準にパラメータを入れて（「ほかのα倍より大きい」）やったバージョンでは、
一応常に改善したらしい。

あと、未知N-gram数は結構減っている。

主張としては、MLS が証拠と参照を裏切らない（カウントが大きければ確率が高い、とか）
のが良い効果を生むだろうということだと思う。
実際、Kneser-Ney は結構裏切るらしい。
パープレキシティは同じでも、中身は結構（よい方へ）違っているのだ、といっている。

理論的に非常にきれいで、分かりやすいのがすばらしい。
証明は多分大変だろうけど。

パラメータフリーであることも長所？
上記のαは、分割してできる領域の平均半径とかで、うまくいくらしい。
それくらいのチューニングの余地を残しておいてもよい気はするが。
αが大きいと、経験分布より参照分布を信頼するようになる。

で、肝心の最適化の手法が分からないんですが。
MLSの不等式制約による表現を見ると、
線形計画問題に落とされているっぽい。
ただ、参照分布にもっとも近いのを選ぶのは不明。
Convex Optimization だとは書いてあるが…

最尤推定に近すぎるんじゃないかとU氏。

枠組みとしては、参照分布とαの選び方に自由度がある。

■ ruby in LaTeX [latex]

確か奥村先生の作。

%%%%%%% ruby{body}{rb}
\makeatletter
\def\kanjistrut{\vrule \@height0.88zw \@depth0.12zw \@width\z@}
\newdimen\mytempdima
\newcommand{\ruby}[2]{%
  \leavevmode
  \setbox0=\hbox{#1}%
  \mytempdima=\f@size\p@
  \setbox1=\hbox{\fontsize{0.5\mytempdima}{0pt}\selectfont #2}%
  \ifdim\wd0>\wd1 \dimen0=\wd0 \else \dimen0=\wd1 \fi
  \hbox{%
    \kanjiskip=0pt plus 2fil
    \xkanjiskip=0pt plus 2fil
    \vbox{%
      \hbox to \dimen0{%
\fontsize{0.5\mytempdima}{0pt}\selectfont \kanjistrut\hfil#2\hfil}%
      \nointerlineskip
      \hbox to \dimen0{\kanjistrut\hfil#1\hfil}}}}
\makeatother

■ subtechグループ - tokuhirom@株主の日記 - first [perl][net]

<http://subtech.g.hatena.ne.jp/tokuhirom/20051119/1132404752>

- $feed_url = (grep {$_->rel eq 'next'} @links)[0]->href;
+ use List::Utils;
+ $feed_url = (first {$_->rel eq 'next'} @links)->href;

俺はこっちの方が好き。どっちでもいいんだけどさ。「オレは最初の一個を取りたいんだぜ感」が強調されるので。

List::Util 便利。
+ first EXPR LIST
+ last EXPR LIST
+ max LIST
+ reduce EXPR($a,$b) LIST # foldlと同じ [2005-10-24]

■ 人力検索はてな - Emacs ユーザーの方に質問です。これは便利! と思える elisp プログラムを教えてください。 [emacs][howto][net]

<http://q.hatena.ne.jp/1137478760>

今日 (windmove-default-keybindings) で shift + カーソルキーで分割したウィンドウが移動できることを知って驚愕してます。

iswitchb-mode
C-x b で buffer を選択するのが楽になります。

session
Emacsを終了してもファイルを編集してた位置や minibuffer への入力内容を覚えててくれます。

minibuf-isearch
minibufferの履歴をインクリメンタルサーチできます。上記の session と一緒に使うとかなり便利です。

ediff - 2つのバッファの差分を色分けで表示、相互に変更。

■ Bayesian Methods for NLP [stat][learning][nlp][net]

<http://www.isi.edu/~hdaume/bayes/>

■ Emacs Lisp Tips [emacs][net]

<http://namazu.org/~tsuchiya/elisp/#yank-pop-summary>
M-y での 「貼り付けなおし」の候補を表示してくれる。

■ TRAMP on Windows [emacs][net]

<http://nijino.homelinux.net/emacs/tramp.html#plink>

PATH 上に plink があれば tramp-default-method は "plink" となるので 特に設定はいりません。
必要に応じて tramp-remote-path にmimencode への path を追加します。 また、サーバに応じて process の coding-sysytem を調整します。

(require 'tramp)
(add-to-list 'tramp-remote-path "/opt/local/bin")
(modify-coding-system-alist 'process "plink" 'euc-japan-unix)

Meadow(Windows) の場合、NetInstall で Tramp を入れて、
Putty のサイトから plink.exe を落として、PATHの通ったディレクトリに置くと、

C-x C-f /username@server:~/xx.txt

で server に username としてログインして、ホームの xx.txt を開くことができる。

■ CPAN で Perl モジュールを全部更新 [perl]

perl -MCPAN -e "CPAN::Shell->install(CPAN::Shell->r)"

cpan シェルで r とやると、更新モジュールの一覧を取得できる。
それを全部 install に渡すというもの。

■ 数学：物理を学び楽しむために [math][book][net]

<http://www.gakushuin.ac.jp/~881791/mathbook/>
量子力学のベースとしての線形代数、
電磁気学のベースとしてのベクトル解析など。
あまり圧縮されていなくて、説明が丁寧。

■ Nonparametric Bayesian Learning conference list [stat][learning][list][learning]

+ Workshop on Learning with Nonparametric Bayesian Methods
June 29, 2006
+ Nonparametric Bayes NIPS*05 Workshop ― Nonparametric Bayesian Methods
+ Bayesian Methods for Natural Language Processing / NIPS 2005 Workshop

■ Volker Tresp. Dirichlet processes and nonparametric bayesian modelling. [stat][net]

<http://wwwbrauer.in.tum.de/~trespvol/papers/DPTresp2006.pdf>

■ Link of NLP/CL Reading List, Cources and Survey Papers [nlp][net]

<http://www.jaist.ac.jp/~n-yoshi/research/reading.html>

■ LaTeX for writing papers in English [latex][net]

<http://www.jaist.ac.jp/~n-yoshi/tips/latex_tricks.html>

■ 備忘録 [emacs][net]

<http://chaosweb.complex.eng.hokudai.ac.jp/~hagi/contents/memo.html>
Meadow, TeX 関係の Tips。
BibTeXの使い方とか。

■ C++ FAQ LITE [cxx][net]

<http://www.parashift.com/c++-faq-lite/index.html>

■ Greasemonkey

Javadoc Incremental Search User Script [java][net]:
<http://www.teria.com/~koseki/tools/gm/javadoc_isearch/>
Javadoc で生成されたドキュメントの検索。
Java でプログラムを書くときは、ドキュメントを片手にすることが多いので、
便利。

■ オモロ検索エンジン SAGOOL サグール [nlp][ui][net]

<http://sagool.jp/>
印象評価済みのデータの検索？
ページ遷移なしで読み進められるUIが面白い。

■ Clarke -- Shortest-substring retrieval and ranking (2000) [ir][string][net]

<http://scholar.google.com/scholar?hl=en&lr=&cluster=2191706408632576091>
AND,OR,region algebra のクエリに対して、
データベースの部分文字列（位置）のリストを返す。

リスト中の部分文字列は、クエリに適合する極小な部分文字列。
リストは文字列の長さ順にソートされている。

演算子が AND だけのときは、
キーワード密度を測って、高い方から返すことに相当する。

この手法は、
[2006-06-01-1]Spectral-based IR の立場からは、
「解像度が非常に細かく、正確だが時間のかかる検索」
とされている。

■ Moses Charikar's Home Page [people][math][algorithm][stat][net]

<http://www.cs.princeton.edu/~moses/>
Similarity Estimation Techniques from Rounging Algorithmsなど。
近似アルゴリズムの専門家。
Locality Sensitive Hashing は、
2つのオブジェクトのハッシュ値が一致する確率が、
2つのオブジェクトの類似度と同じであるようなハッシング。

この論文では、
数ベクトルのコサイン類似度についてのLSHと
内積が定義されたベクトルのEarth Mover DistanceについてのLSHが構築されている。

これによって得られる近似的な類似度を使って、近似的なNearestNeighbourSearchを高速に行うアルゴリズム

■ Li -- Using Sketches to Estimate Two-way and Multi-way Associations - Google Scholar [math][algorithm][stat][net]

<http://scholar.google.com/scholar?hl=en&lr=&cluster=4804964007952417849>
Locality Sensitive Hashing 関連。

■ Generalized Hebbian Algorithm for Incremental Singular Value (2006) [lm][ir][net]

<http://citeseer.ist.psu.edu/746603.html>
yet another SVD algorithm

■ 「統計数理」総目次 [stat][net]

<http://www.ism.ac.jp/editsec/toukei/contents.html>
統計数理研究所の。