$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

ちょっとしたことでも雑にブログに書いておくと良いことが起こる

misc tech

　僕は自分がやったこと・勉強したこと・気づいたことなどはどんなにちょっとしたことでも、公開の場のブログに書くようにしている。その内容はある程度雑でも良いので、とにかく公開の場に書くようにしている。それによって、結構良いことが起こっているというのを社内の日記に書いていたのだけど、これも公開の場に書いておいても良いかと思ったので書く。

　これまでの経験だと、次のような良いことが起こっている。

  • 最低限未来の自分に理解できる程度まで記事にまとめることで、知識が頭の中で言語化され、定着する
  • 時々他の人からフィードバックを受けて、さらに学習が進むことがある
  • 「あれ昔なんか勉強したけど覚えてないな」という時に自分のブログ見たらすぐ思い出す
  • 分からないことを調べようとググったら自分のブログが出てきてすぐ思い出す
  • 初めからブログに書くつもりでインプットすると、自然と体系化・汎化しながらインプットできるようになる
  • 自分がちょっとしたことって思っていることが、意外と他の人の参考になるということが起こる
  • 他の人が困っていて、それが自分が昔経験したことなら、ここにまとめておきましたと自分のブログからシュッと出せる
  • 記事を書き続けていると意外と読者が増えていて、気合を入れた記事を書いた時もみんなに見てもらえる
  • 徐々にフォーマットも出来てきて、アウトプットのリズムが生まれる

　雑でも良いので、自分のやったことはどんどんブログに書いておくことで、上記したような良いことが起こるので、今後も続けていきたいと思う。質より量という気持ち。

【余談】最低限の雑さ

　「雑に」と書いているけど、最低限気をつけていることがある。それは本当のことを書き、嘘や軽薄なことを書かないこと。もし正しいか分からないときは、その旨を記事の最初に書いておくこと。

　アウトプットの質はそこまで求めなくて良いとは思うが、他の人を嘘で惑わすような記事にしないようにできる限り心がけたい。

4/16 10:23追記

　最低限の雑さについてさらに考えを深めてブログに書きました。
blog.shibayu36.org

Coursera Machine Learning Week2の学習

tech

　前回 に引き続き、Coursera Machine Learning Week 2を受講した。

　前回は線形回帰モデルとは何か、最小化すべきCost Functionは何か、最急降下法とは何かについて学ぶことができた。Week 2の講義を受けるとさらに次のことを理解することができる。

  • 多変量(x1, x2, x3, ...など変数が多数あるもの)の線形回帰をどのように考えれば良いか
  • 最急降下法のための、正規化や学習率の決め方について
  • 最急降下法でなくて、正規方程式を利用した線形回帰モデルの計算方法
  • Octaveのチュートリアル

　課題もやってみたけど、行列演算を利用することで難しい方程式を一気に計算できるようになるというのが面白いところだった。以下メモを置いておく。

Multivariable Linear Regression

Multiple Features

  • 多変量の線形回帰
  • x0=1と仮定すると、多変量の予測関数は次のように表せる
    • \begin{align*}h_\theta(x) =\begin{bmatrix}\theta_0 \hspace{2em} \theta_1 \hspace{2em} ... \hspace{2em} \theta_n\end{bmatrix}\begin{bmatrix}x_0 \newline x_1 \newline \vdots \newline x_n\end{bmatrix}= \theta^T x\end{align*}

Gradient Descent For Multiple Variables

\begin{align*} & \text{repeat until convergence:} \; \lbrace \newline \; & \theta_0 := \theta_0 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_0^{(i)}\newline \; & \theta_1 := \theta_1 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_1^{(i)} \newline \; & \theta_2 := \theta_2 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_2^{(i)} \newline & \cdots \newline \rbrace \end{align*}

なので

\begin{align*}& \text{repeat until convergence:} \; \lbrace \newline \; & \theta_j := \theta_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \; & \text{for j := 0...n}\newline \rbrace\end{align*}

x_0を1と置くことにより、全てを一括で表せるようになり、可愛い感じになった。

Gradient Descent in Practice Ⅰ - Feature Scaling

  • より収束しやすくするために、それぞれの変数を正規化する
  • -1 <= x(i) <= 1くらいなら良い
    • 経験的に -3 <= x(i) <= 3, -1/3 <= x(i) <= 1/3くらいなら許容
  • x_i := \dfrac{x_i - \mu_i}{s_i}
    • μiがxiの全ての値の平均、siがrange = (max - min)

Gradient Descent in Practice Ⅱ - Learning Rate

  • ずっとcost functionが下がり続けるLearning Rateを選ぶこと
  • Learning Rate αが小さすぎると、収束するのが遅くなる
  • Learning Rate αが大きすぎると、cost functionが減らなくなり、収束しなくなる可能性がある

Features and Polynomial Regression

  • 複数のfeatureを一つにまとめることもできる。例えばfeature1 = 縦、feature2 = 横だとしたら、featureをまとめてfeature3=面積(=縦*横)とすることもできる。
  • x_2 = x_1^2, x_3 = x_1^3と変数を定義することもできる。こうすると多項式の回帰のグラフとなる

Computing Parameter Analytically

Normal Equation

  • Normal Equation = 正規方程式
  • Normal Equationでのθ計算: \theta = (X^T X)^{-1}X^T y

Gradient DescentとNormal Equationのメリット・デメリット

Gradient Descent Normal Equation
学習率αの計算が必要 学習率の計算が不要
たくさんのiterationが必要 iterateが必要ない
計算量がO (kn^2) O (n^3)の計算量である, X^TXの転置行列計算が必要
nが多くても計算できる nが多いと遅くなる
  • n=10000を超えてくると、Normal Equationでは計算が大変になる

Octave/Matlab Tutorial

Basic Operations

  • 等しくないは ~=で表す
  • 1:0.1:2は 1から増分0.1で2まで増やした行ベクトルを表している(?)
  • histによって分布を見ることが出来る
  • help (command)でhelpを見れる

Moving Data Around

  • loadとsaveでファイルの入出力

Plotting Data

  • plot系
  • imagesc(A), colorbar, colormap gray;

Vectorization

  • forループをベクトルの掛け算に変換することで、簡単にかつ高速に演算できる

MySQLのfilesortは何ソートで行われているのか

　最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。

　調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。

調査結果

最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。

  • sort_buffer_size以内のメモリ量でソートが可能な場合、メモリ内でのみソートされる
  • ソートにsort_buffer_size以上のメモリが必要な場合、sort_buffer_sizeでメモリが足りる単位でメモリ内ソートが行われ、それぞれの結果を一時ファイルに書き出す。最後に一時ファイルからマージソートする
  • メモリ内のソートには、クイックソートか、Priority Queueを使ったTop-kソートが用いられる
  • ソートしなければならない行数が、最終的に必要な行数の3倍を超える時、Priority Queueを使ってソートされる。そうでなければクイックソートが使われる

filesortは基本的にクイックソートとマージソートの組み合わせ

MySQL :: MySQL 5.6 リファレンスマニュアル :: 8.2.1.15 ORDER BY の最適化 を見てみると、filesortのアルゴリズムが書かれていた。これによると、filesortのアルゴリズムには、「元のアルゴリズム」と「変更されたアルゴリズム」の二つがあるらしい。「変更されたアルゴリズム」は「行を 2 回読み取ることを回避する最適化が行われたもの」らしいので、今回は考えないことにして、「元のアルゴリズム」の内容を見てみる。

　「元のアルゴリズム」は次のステップで進むらしい。

1. キーに従って、またはテーブルスキャンによって、すべての行を読み取ります。WHERE 句に一致しない行をスキップします。
2. 行ごとに、ソートバッファーに値のペア (ソートキー値と行 ID) を格納します。
3. すべてのペアがソートバッファーに収まる場合は、一時ファイルが作成されません。そうでない場合は、ソートバッファーがいっぱいになると、メモリー内でそれに対して qsort (quicksort) が実行され、それが一時ファイルに書き込まれます。ソートされたブロックへのポインタを保存します。
4. すべての行が読み取られるまで、前の手順を繰り返します。
5. 別の一時ファイルで、最大 MERGEBUFF (7) 領域の 1 つのブロックへのマルチマージを実行します。最初のファイルのすべてのブロックが 2 番目のファイルに格納されるまで、この処理を繰り返します。
6. 残りが MERGEBUFF2 (15) ブロックより少なくなるまで、次を繰り返します。
7. 最後のマルチマージで、行 ID (値のペアの最後の部分) のみが結果ファイルに書き込まれます。
8. 結果ファイルで、行 ID を使用して、ソートされた順序で行を読み取ります。これを最適化するには、行 ID の大きなブロックを読み取り、それらをソートして、それらを使用して、ソートされた順序で行を行バッファーに読み込みます。行バッファーサイズは read_rnd_buffer_size システム変数値です。この手順のコードは sql/records.cc ソースファイルにあります。

　単純に書くと

  • sort_buffer_sizeに収まりソートできるなら、quicksortが実行され、結果として返される
  • 収まらないなら、分割してquicksortした結果を一時ファイルに書き出しておき、最後にマージソートしていく

というイメージだろうか。

　メモリ上でソートするなら、クイックソートは計算時間も速く、かつ無駄な空間も使わないので効率的である。また一旦ファイルに書き出したソート済配列を結合するなら、シーケンシャルに先頭から見ていけばソートが完了するマージソートの手法が効率的である。これからクイックソート+マージソートの組み合わせになるのは自然だなと感じた。

参考

メモリ内のソートはクイックソートでなく、Priority Queueを使ったソートが使われる時もある(?)

　以上の知識を持って、filesortのコード を読んでみると、なぜかPriority Queue sortという文字列が出てきて混乱している。https://github.com/mysql/mysql-server/blob/567bb732bc0e2de38f10c1793dcc0a0c6f877742/sql/filesort.cc#L1313 あたり。

　Priority Queueを使うと、n個の中から上位k個を取り出すTop-k sortという手法が使われることになり、この時間計算量はO(n * log(k))となる。クイックソートの時間計算量はO(n * log(n))なので、nが大きくkが小さい時、つまりたくさんの候補の中から取り出したい数が少ないときは、クイックソートよりPriority Queueを使ったほうが速いように見える。

　この辺りの前提から考えると、WHERE句でそこまで絞り込まれない時(nが大きい時)に、LIMIT句が指定されて取り出したい個数が少ない時(kが小さい時)に、クイックソートの代わりにPriority Queueを使うイメージだろうか。

　軽くコードを見てみると

  • 計測してみるとクイックソートよりPriority Queueのソートのほうが3倍ほど遅いことが分かっている
  • なので、LIMITで指定した数に対して、候補となる件数が3倍以上になるなら、クイックソートよりPriority Queueを使ったほうが良い

という風に見えた。

　このあたりのコード、かなり難しくて、本当に今回調べた結果が正しいのか分からない...

参考

まとめ

　アルゴリズムでソートの勉強をしていて、ふとMySQLのfilesortはどうやっているんだろうと気になったので、軽く調査をしてみた。MySQLのコード初めて読んだのだけど、非常に難しくて正しく読み解くことが出来たか怪しい。間違っている可能性も大いにあるので、何かおかしいことがあれば指摘してもらえるとうれしいです。