作成者別アーカイブ: eisuke

eisuke について

Pattern Recognition and Machine Learning.

[Algorithms] Algorithms and Data Structure

What is algorithm?

Algorithm: well-defined computational procedure. it has input and output such as some values. it is composed of a sequence of computational steps.

Correctness: for every input instance, the algorithm halts with the correct output.

Correct algorithm solves the given computational problem.

 

What is data structure?

Data Structure: a way to store and organize data in order to facilitate access and modifications.

No single data structure works well for all purposes.

 

Various techniques of algorithm design and analysis

  • Order notation
  • Minimum spanning trees (MST)
  • Maximum flow in a network
  • Divide-and-conquer
  • Dynamic Programming (DP)
  • Amortized analysis

etc.

 

Hard problems

NP-complete: the subset of computational problems.
1) no efficient algorithm for this type of problem has ever been found, and nobody has ever proven that an efficient algorithm for one cannot exist. (In other words, no one knows whether or not efficient algorithm exist for NP-complete problem.)
2) this problem has remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. (!)
3) several NP-complete problems are similar to problems for which we know efficient algorithms.

E.g. Traveling-salesman problem
To deliver goods to several address, we want to know the shortest overall distance traveled by car. => This is NP-complete (no efficient algorithm exists! However under some assumptions, we can use approximate algorithms.)

 

Efficiency

  • Different algorithms devised to solve the same problem often differ dramatically in their efficiency. (=> Discuss Order notation)
  • Difference of efficiency can be much more significant than differences than differences due to hardware and software.

E.g. Time complexity
Two algorithms for sorting. if n items given as input, computational time of each algorithm are
1) Insertion sort: c_1 n^2
2) Merge sort: c_2 n{\rm log}n
where c_1, c_2 are constant.
Although insertion sort usually runs faster than merge sort for small input size, the input size c becomes large enough, merge sort’s advantage of {\rm log}n vs. n.

 

Algorithms are at the core of most technologies.
Skilled programmers with the knowledge of algorithms.

[latex]テーブルのキャプションの文字”表”を”図”に変更する方法

Texでの文書作成時に表のキャプション(i.e. 表1: hogehoge)をつけると思いますが、この「表1」の部分を「図1」に変えたい場合があります。

僕は今までこういうことはしたことがなかったのですが、後輩からの質問で調べてみました。

キャプションは、table環境だと「表」になり、figure環境だと「図」となります。
単純に環境を変えてやれば良いことが分かりました。

\begin{table}
\begin{tabular}
~
\end{tabular}
\end{table}

\begin{figure}
\begin{tabular}
~
\end{tabular}
\end{figure}

と変更すると「表1: hogehoge」となっていたキャプションが、「図1: hogehoge」と変更されます。

Available BCI signal Data Sets

Available BCI signal Data Sets (Linkedin)

Twitter Streaming APIの特定キーワード抽出 track が残念な件

https://dev.twitter.com/docs/streaming-apis/parameters#track

Non-space separated languages, such as CJK and Arabic, are currently unsupported.

単語の間にスペースがある言語のみ検索可能。

日本語はutf-8で一応検索可能ですが、完全一致のものしか返ってきません。微妙…。

  • ハッシュタグの検索 (i.e. #nhkとか)
  • 特定の英数文字列が含まれるURL

などは検索できて便利です。

Algorithms for manifold learning (L.Cayton, 2005)

Manifold learning (多様体学習)のAlgorithmを比較した論文です。

多様体(manifold)とは、局所的にはユークリッド空間とみなせる位相空間のことをいいます。

例えば、地球は丸いので、地球の表面すべてを一度に2次元の地図で表現しようとすると、繋ぎ目で重複が現れたり歪みが生じたりします。

しかし、局所的にみることによって2次元座標で地図の表現ができるようになります。

あるデータにも同じことが言えて、ものすごく高次元な空間にあるデータでも、実質的には低次元で表現できる場合があります。

if data lies in a 100-dimensional space, one cannot get an intuitive feel for what the data looks like.

4次元以上の高次元のデータの場合、視覚化できないので実際にデータがどうなっているか分かりにくかったり、コンピュータで計算をするのに、ものすごく時間がかかることがあります。

機械学習やデータマイニングでは、不要な情報を捨てて、必要な情報を抽出することはいろいろな意味で重要です。
高次元のデータをうまく表現できるように低次元のデータに変換することを次元圧縮(dimension reduction)といいます。

(書きかけ)

多様体の定義

PCA

線形部分空間への射影のみ

  • Isomap
  • Locally Linear Embedding (LLE)
  • Laplacian Eigenmaps
  • Semidefinite Embedding (SDE)

Algorithms for manifold learning (L.Cayton, 2005)

 

[PRML] 1.1 多項式曲線フィッティング (2)

次数 M の決め方
次に、多項式の次数 M は、どう選べばよいのでしょうか。
この問題はモデル選択(model selection)と呼ばれています。

それでは、実際に M の値をいろいろと変えてみたものを見てみましょう。

(図 作成中)

次数 M が小さすぎる場合、ほとんどの訓練データへの当てはまりが悪いのが分かります。
反対に、次数 M が大きすぎる場合、訓練データへの当てはまりが非常に良くなっています。例えば、次数 M = 9 の例では、E({\mathbf w}^*) = 0 となっていて、誤差が無い状態です。

では M = 9 の場合が一番良いのでしょうか。

そうではなさそうですよね。
関数の形が発振したようにぐにゃぐにゃになってしまっています。
このような状態では、訓練データに対する当てはまりが良すぎて、新しいデータ、つまりテストデータに対しては、うまく目標値を予測することができません
この状態を、過学習(over-fitting)とよびます。

では、よい次数 M はどうやって選べばよいのでしょうか。

…答えは単純です。

いろいろとMを変えてみて、それぞれについて誤差 E({\mathbf w}^*) を求め、比較すればいいのです。

実際には、平均二乗平方根誤差(RMS error, root-mean-square error)という指標を使います。

E_{RMS} = \sqrt{\frac{2E({\mathbf w}^*)}{N}}

この指標は、

  • データ数 N で誤差関数を割っているため、異なるデータ数をもつデータに有効
  • 平方根をとっているため、目標値 t と単位が揃う

というメリットがあります。

次数 M の場合の、E({\mathbf w}^*) を訓練集合とテスト集合それぞれについて調べてみると、以下のような結果になりました。

(図 作成中)

次数が高い多項式は次数が低い多項式を特殊な場合として含むので、次数が高くなるにつれてよいモデルになりそうですが、結果は異なります。
これは多項式の次数が高すぎると、データに含まれるノイズに敏感になってしまうためと考えることができます。

データ集合のサイズを大きくする

今度は、次数 M を固定したうえで、データ集合 N のサイズを変えてみましょう。

(図 作成中)

どうでしょうか。

先ほど問題になっていた複雑な多項式モデル M = 9 ですが、データ数 N が増えたことで過学習が緩和されていることが分かります。

訓練データの数が大きくなると、より複雑なモデルをデータに当てはめることができます。

この議論で行くと、入手できる訓練データの数によって、モデルの複雑さ(この場合の次数 M )を選ばなくてはならなくなってしまうので、違和感があります。

限られたサイズの訓練データに対して複雑で柔軟なモデルを使うことができるようにするために、正則化(regularization)というテクニックがあります。

[PRML] 1.1 多項式曲線フィッティング

回帰(regression)とは、教師あり学習(supervised learning)のひとつです。

  1. 機械を訓練するためのデータ(training set) {\mathbf x}_{train} とそれぞれに対応する目標ベクトル(target vector) {\mathbf t}_{train} があらかじめ与えられているので、それらをもとに関数 y を求めます。
  2. 新たな入力 {\mathbf x}_{test} が来たときに、求めた関数 y を使って、対応する目標ベクトル {\mathbf t}_{test} を予測します。

曲線フィッティング(curve fitting)を例に紹介します。
以下の多項式を使ってデータへのフィッティングを行います。
y は、ある入力値 x が与えられると、x^iが係数 \omega_i によって重み付けされた和を返す関数になっています。

y(x, {\mathbf w}) = \omega_0 + \omega_1 x + \omega_2 x^2 + \cdots + \omega_M x^M = \sum_{j=0}^{M} \omega_j x^j

M は多項式の次数、多項式の係数 (\omega_0, \omega_1, \ldots , \omega_M)^T = {\mathbf w} とおくことにします。
この多項式は、未知のパラメータ {\mathbf w} に関して線形になっているのがポイントです。こういった関数を線形モデル(linear model)と呼びます。

訓練データをもとに、この多項式のパラメータが決まれば、新たなデータ x_{test} が来たときに、予測される目標値 t_{test} を出力してくれることになります。

ここで、決めなくてはならないパラメータは2つあります。

  • 多項式の係数 {\mathbf w}
  • 多項式の次数 M

係数 {\mathbf w} の決め方
まず、どうすればパラメータ {\mathbf w} を決めることができるのでしょうか。

あらかじめ与えられているのは訓練データだけです。
そこで、{\mathbf w} を任意の値に固定したときの関数 y(x, {\mathbf w}) の値と訓練データの目標値 t とのずれを測り、この誤差(error)が最も小さくなるときの関数 y(x, {\mathbf w^{*}}){\mathbf w^{*}} を選択します。

誤差を測る関数を誤差関数(error function)と呼びます。
二乗和誤差(sum-of-squares error)が単純なのでよく使われます。

E({\mathbf w}) = \frac{1}{2} \sum_{n=1}^{N} \{t_n - y(x_n, {\mathbf w})\}^2

この関数は係数 {\mathbf w} の二次関数なので、{\mathbf w} に関する微分は線形になります。誤差関数を最小にするただ1つの解を持つことになり、その解 {\mathbf w}^* は閉じた形で求められます。

次数 M の決め方
次に、多項式の次数 M は、どう選べばよいのでしょうか。

[WordPress] ツイートボタンの設置方法

WordPressの記事にTwitterのツイートボタンを設置します。
今回は記事のタイトルの直下に設置することにしました。

/wp-content/themes/twentytwelve/content.php を開き、

<a href=”http://twitter.com/share” data-count=”horizontal” data-via=”****” data-text=”<?php the_title(); ?>” data-url=”<?php the_permalink() ?>” data-lang=”en”>Tweet</a><script type=”text/javascript” src=”http://platform.twitter.com/widgets.js”></script>

を</header>タグ直前に追加する。

ここでのポイントとして、WordPressの関数を呼ぶことで記事のタイトル(the_title)と記事のリンク(the_permalink)を動的にコードに埋め込んでいます。

****は、あなたのTwitter IDを入れましょう。Twitter公式サイトにもありますが、オプションを変えるとあなたの好みに応じてカスタマイズできます。
表示される言語も選択できるようになっていて、「Tweet」がよければ data-lang=”en”を、「ツイート」がよければdata-lang=”ja”にすれば変更できます。

これだけだと記事のタイトルとの余白が無いので、

/wp-content/themes/twentytwelve/style.css を開き、

iframe.twitter-share-button {
margin-top: 10px;
}

を追加すると、ボタンの上に余白が入って見やすくなりました。

[WordPress]「コメントをどうぞ」のリンクの位置を変更する方法

WordPress (ver 3.5.1 / テーマTwenty Twelve)で読者からのコメントを有効にすると、記事のタイトルの下に「コメントをどうぞ」のリンクが表示されるようになります。

タイトルの直下だと正直微妙なので、表示場所を記事の下部へ変更します。

/wp-content/themes/twentytwelve/content.php を開き、

<?php if ( comments_open() ) : ?>
<div class=”comments-link”>
<?php comments_popup_link( ‘<span class=”leave-reply”>’ . __( ‘Leave a reply’, ‘twentytwelve’ ) . ‘</span>’, __( ’1 Reply’, ‘twentytwelve’ ), __( ‘% Replies’, ‘twentytwelve’ ) ); ?>
</div><!– .comments-link –>
<?php endif; // comments_open() ?>

をカットして、</footer>タグの直前にペーストします。

これですべての記事で「コメントをどうぞ」のリングが記事の最下部に表示されるようになりました。

==

追記:2013.03.26

編集方法

編集方法には2種類あります。
A) ファイルを直接編集する方法
B) WordPressの管理画面から、上記ファイルを編集する方法

A) ファイルを直接編集する方法について

ファイルサーバーにアクセスしてファイル(content.php)をエディタで開き、上記部分を編集した後、保存します。

B) WordPressの管理画面から、上記ファイルを編集する方法について

1. WordPressの管理画面を開きます。
2. 左のメニューアイコンで(上から6つ目の)「外観」メニューにマウスカーソルを乗せると、サブメニューが表示され、その一番下「テーマ編集」をクリックします。
ここから基本的なテンプレートの編集が可能です。
3. 右側の「テンプレート」のリストから「content.php」をクリックしてファイルの編集画面を出します。
4. 上記部分を書き換えた後、「ファイルを更新」ボタンをクリックしておしまいです。

Q&A

Q. テンプレートを編集したのに表示が切り替わらない
A. まずはBの手順でWordPressの管理画面からソースコードがきちんと変更できているか、確認します。
プラグインの「WP Super Cache」が有効になっていると、キャッシュが残っているために変更が反映されるまでに時間がかかることがあります。
有効になっている場合、開発の際は一時的に停止します。
1. WordPress管理画面の左のメニューアイコンで(上から7つ目の)「プラグイン」メニューをクリックし、プラグインの一覧を表示する。
2. プラグインの中の「WP Super Cache」の「停止」というリンクをクリックして、一時的に無効化します。