読んだフリ論文[Shinh, 2011]りすと
SPIRE 2010
CST++
"Compressed Suffix Tree++"の意味。この論文は正直Ohelbusch, Fischer & Gogの昔の論文シリーズを知らないと理解できないと思う。
要約
Compressed Suffix Tree（圧縮接尾辞木）は、文字列検索でおなじみのsuffix treeを圧縮したまま利用できるようにしよう、というもの。で、今回の報告は、文字列
文字に対し
ビットあれば十分で、しかもsuffix treeの木を辿ったり, 次のノードを探したりという殆どの操作が
で出来る。実装にはCartesian treeという木を使う。
http://en.wikipedia.org/wiki/Cartesian_tree
実はCartesian treeの数え上げはカタラン数で決まるので、そのlogぶんのビットがあれば1つの木を表現できる。実際にはBPR(Balanced Parenthesis Representation - カッコの左右が対応した木の表記法)と、追加のビット表記で表す。
Approximate String Matching with Stuck Address Bits
「あいまい文字列検索」というと文字列の構成要素がずれることが多いですが、文字列の位置のアドレスがずれる時に問題を変えてみましょう、という論文。えーと面白いのはそうなんですが……これ応用あるの？？ ちなみにbackgroundは読めば多くの方がニヤリとできるかと思います。
String Matching with Variable Length Gaps
概要
「僕と契約して○○になって欲しいんだ」など、一部が可変のフレーズを検索したい欲求は常にあります。これが固定長のフレーズであれば割とどうにかなりますが、可変長のフレーズだと簡単ではありません。こういうgapをどう処理しますか？ という問題。文字列
, パターン長
, gap回数
の時、時間計算量
, 空間計算量
で可能。
は本文中でのパターン出現回数、
は最低gap長の和。
方法
固定パターン全てに対しAho-Corasickオートマトンを作ります。本文を順に処理し、パターンが見つかったら「生きているマッチ位置リスト」を更新していきます。最後のパターンが生きているマッチ位置に見つかったらマッチ位置を報告して終了。
NIPS 2010
Random Projections for 
-means Clustering
前提知識: Johnson-Lindenstrauss Lemma
Johnson-Lindenstrauss Lemma(以下JL Lemma)は、ざっくり言うと「高次元の点をランダムに低次元に射影すると距離は近似的に保存されるよ」「どれぐらい保存するかは射影先の次元の多さで決められるよ」というもの。
前提知識: -means approximate Clustering
-means クラスタリングは実は
の時ですらNP困難な問題である。なので、実際には
-meansの近似をこんな感じで定義する。
これが
-meansクラスタリングの
近似である。
はデータ行列。
はクラス情報行列で、
行
列目の要素は
、それ以外は0になる。
は
列にあるnon-zero要素の個数。
要約
ランダム射影を組み合わせることで
-meansの近似を効率よく解けるぜフーハーハー。特に、次元を
までに落とし、計算時間も
に対して線型となったのがポイント。手法は鼻血が出るほど簡単で、+1/-1行列を掛けてから解くだけ。
手法
ランダム行列を作成し、
を射影する。射影結果に対し
-近似
-meansクラスタリングを実行。終わり。
Robust PCA via Outlier Pursuit
要約
PCA(主成分分析)ははずれ値に弱いという問題がある。俺たちは一定割合のはずれ値を無視してPCAを計算する問題設定を考えた。提案解法の"Outlier Pursuit"は凸最適化だから簡単に解けるぜ。
問題設定
-次元、
-点のデータに対するOutlier Pursuitは、データ点のうち、
点を
除く点の分散を最小化する。従って、問題はこの「はずれ値」データと、Outlier Pursuit空間を同時に決めることだ。
解法
Algorithm 1 参照。データがノイズを含む場合は、式(3)を参照。チューニングパラメータ
の設定は3.1節を参照。
適用範囲
そもそもこの問題設定は、well-definedでないケースが存在する(see 2.1)。Column-incoherence(2.1)が成立しないといけない。
最終更新：2011年03月06日 18:30
