うわっ･･･先月のコスト、低すぎ･･･？Hadoopクラスタのクラウド移行とSparkオンデマンド

福田です。

ゆっくりとカモミールを飲みながらラップトップを叩いています。

3年間お世話になったデータセンターのHadoopクラスタをクラウド環境に移行しました。

クラウドでは従量課金を活かしてコストの最適化を図ることができます。

今回、Cloudera ManagerとJenkinsそれぞれのAPIを使用し、クラスタの起動状態を保証するラッパーと自動停止サイクルを実装することで、透過的なクラスタの起動と停止を実現しました。 *1

アーキテクチャ

全てを包むWraps

作業環境となるホストに、ラッパーコマンド（以下Wraps）をインストールします。 *2

Wrapsは、状況に応じてJenkins、Cloudera ManagerのAPIを呼び出し、VMインスタンスおよびCDHクラスタの起動状態を保証します。

また、後述する停止サイクルに対して使用中であることを通知するロックファイルの作成と削除を、開始時と終了時それぞれに行います。

hadoop、spark-shell、spark-submit、hive、hbaseなどクラスタを使用する任意のコマンドに対してエイリアスを設定し、Wraps経由で実行できます。

停止サイクル

クラスタとVMインスタンスの停止は、Jenkinsのジョブを定期的に実行することで行います。前述のロックファイルが存在しない場合にのみ停止します。 *3

Sparkシェルの意図しない繋ぎっぱなしや、接続断によるロックファイル残留によりクラスタが稼働し続けてしまうことへの対策として、Sparkシェルに読み込ませるスクリプト（アイドル検知し、自動的に終了する）や、親プロセスがいないロックファイルの定期削除などの仕組みも実装しました。

Wrapsデモ

実行イメージ：クラスタの起動を伴うsparkシェルの起動

稼働イメージ：テスト環境より

まとめ

クラスタの起動と停止の自動化により、調整のコミュニケーションや手動でクラスタを停止するという人的作業と使用していない時間のインスタンスコストが消滅しました。

空いた時間でハーブティーを入れています。

*1:実際には使用量に応じた割引などがあるため、利用状況に合わせて適切に見積もる必要があります。

*2:Pythonで実装。内部で、便利で気の利いたCloudera Manager API Clientを使用しています。注意点として、使用しているCloudera ManagerがサポートするAPIのバージョンに合ったクライアントを選択する必要があります。

*3:利便性を考慮して、Wrapsを経由したコマンドの実行完了後に一定のアイドル時間を保証するようにしています。これは、終了時のロックファイルの削除を、リネームによるサフィックスの付与とタイムスタンプの更新という実装に置き換え、一定時間以上経過したサフィックス付きのファイルを削除する処理を定期的に実行することで行います。

特異値分解と行列の低ランク近似

はじめまして。テクノロジーインテリジェンス部で主にデータ周りの業務を担当しているshmです。今回、並河さんからご指名を頂き、記事を執筆させて頂くことになりました。

さてデータといえば、最近では統計処理ソフトR、Pythonの数値計算ライブラリNumPyや機械学習ライブラリscikit-learnなど高度なデータ分析を行うための環境を簡単に（しかもフリーで！）手に入れることが出来るようになりました。以前であれば大学の研究者やアナリストといった専門家向けのマニアックなツールとして知る人ぞ知る存在だったはずですが、近年のブームの中、書籍やネットで紹介されることで、その存在が広く知れ渡るようになりました。これらのツールは一定の書式で値を入力するだけで簡単に解析結果を返してくれる大変便利なものですが、得られた結果が妥当なものであるかどうかは別途、評価しなければならないのが普通です。その際、適切な評価を行う為にもツールが前提としている理論について把握しておくことが望ましいのですが、実際にはブラックボックスとして使われることも多いと思われます。

そこで本記事では、こうしたツールが提供する様々な機能の中から、広い応用範囲を持つ特異値分解にスポットを当てて解説したいと思います。

本記事の構成は以下の通りです。

はじめにベクトルや行列について、本記事の内容を理解するために必要なことに絞って簡単に復習します。次に特異値分解を理解するために必要となる固有値分解を紹介した後*1、特異値分解について証明付きで解説します*2。最後に応用として、行列の低ランク近似について取り上げます。行列の低ランク近似は、データを要約して次元を圧縮するためにしばしば使われますが、この記事では行列が近似されていく様子を画像データを使い視覚的に確認します。

ベクトルと行列

以下、 は複素数全体 または実数全体 を表すものとします。

の元 を の様に並べて出来た集合を とします。 に和とスカラー倍 \begin{gather*}(a_{1},\ldots,a_{n})+(b_{1},\ldots,b_{n}) :=(a_{1}+b_{1},\ldots,a_{n}+b_{n})\\\lambda(a_{1},\ldots,a_{n}):=(\lambda a_{1},\ldots,\lambda a_{n})\end{gather*} を定義して線型空間の構造を与えるとき、 の各要素 をベクトルと呼びます。

次に、 個の の要素 を 縦横２次元に並べたものを 行列と呼び、 \[\left(\begin{array}{ccc}a_{11} & \cdots & a_{1n}\\\vdots & \ddots & \vdots\\a_{m1} & \cdots & a_{mn}\end{array}\right)\] と書きます。これをより簡潔に と書くことがあります。 さらに \[\left(\begin{array}{cc}A_{p,q} & A_{p,n-q}\\A_{m-p,q} & A_{m-p,n-q}\end{array}\right)\] （ は 行列を表す）の様にブロックに分けて書くことがあります。

良く目にするタイプの行列には特に名前が付けられています。

定義

• 行列を 次の正方行列と呼ぶ。
• 対角要素以外 0 の行列を対角行列と呼ぶ。対角行列の内、対角要素が全て 1 であるものを単位行列と呼び と書く。
• 行列 の行と列を入れ替えて出来る 行列 を転置行列と呼び と書く。転置した上で複素共役を取った行列 を随伴行列と呼び と書く。
• 正方行列 が を満たすとき、 をエルミート行列と呼ぶ。
• 正方行列 が を満たすとき、 をユニタリ行列と呼ぶ。
• 正方行列 が を満たすとき を射影行列と呼ぶ。

行列には以下の様に和と積が定義されます： 、 を 行列、、 をそれぞれ 、 行列として \begin{gather*}(a_{ij})+(b_{ij}):=(a_{ij}+b_{ij}),\\(c_{ij})(d_{ij}):=\left(\sum_{k=1}^{r}c_{ik}d_{kj}\right).\end{gather*}

行列の内、 行列や 行列はしばしばベクトルと同一視され、それぞれ 次の列ベクトル、 次の行ベクトルと呼ばれます。

なお 、 をベクトルとするとき、\[(a,b)=\sum_{i=1}^{n}\bar{a}_{i}b_{i}\]によって標準内積と呼ばれる演算が定義されます*3が、 および を列ベクトルと同一視するとき\[(a,b)={}^{t}\bar{a}b\]（右辺は行列としての積）が成り立ちます。また を と書くことにします。

さて線型空間 のどの要素も 、 に関する和とスカラー倍で書き表すことができるとき を基底と呼びます。特に が成り立つとき を正規直交基底と呼びます。

固有値分解

正方行列 に対して、\[Ax=\lambda x\] を満たすスカラー と列ベクトル が存在するとき、 を の固有値、 を の固有ベクトルと呼びます。また の固有ベクトル全体から作られる線型空間を に対する固有空間と呼びます。

特異値分解を理解する上で、エルミート行列に対する固有値分解が鍵となるので結果を紹介します。

定理１（固有値分解）   次エルミート 行列 に対して、適切なユニタリ行列 を選んで を 対角化することが出来る： \[U^{*}AU=\left(\begin{array}{ccc}\lambda_{1} & & O\\ & \ddots\\O & & \lambda_{n}\end{array}\right).\] また を 次元列ベクトル を用いて と表すと、上式は \[A=\sum_{i=1}^{n}\lambda_{i}u_{i}{}^{t}\bar{u}_{i}\] と書き表すことが出来る。 がユニタリ行列より は線型空間 の正規直交基底である。

固有値分解に現れる 次正方行列 は の固有ベクトル への射影行列になっています。実際、任意の に対して\[(u_{i}{}^{t}\bar{u}_{i})x=(u_{i},x)u_{i}\]であることから直接計算によって確かめることが出来ます。

余談ですが、行列の固有値は 次の代数方程式\[\det(\lambda I-A)=0\]（固有方程式または特性方程式と呼ばれています）の解であることから、固有値を求める為に固有方程式を解くことを考えるかもしれません*4。しかしそれが実行可能なのは までで、 が 5 以上になると方程式の係数に対する四則演算や根号の組合せによって解を求めることが（一般には）出来なくなります*5。当然、計算機を使って固有値を求める場合にもこの制約は付いて回るため、一般に固有値を求めるアルゴリズムは反復解法に限られることになります。

特異値分解

固有値分解は正方行列に対する分解ですが、全ての正方行列に対して固有値分解が可能であるわけではありません *6。 一方、特異値分解はどのような行列に対しても実行可能です。

定理２（特異値分解）   を 行 列の行列とする。このとき 次のユニタリ行列 と 次のユニタリ行列 が存在して \[U^{*}AV=D:=\left(\begin{array}{cccc}\sigma_{1} & & O\\ & \ddots & & O_{r,n-r}\\O & & \sigma_{r}\\ & O_{m-r,r} & & O_{m-r,n-r}\end{array}\right)\]と書くことができる。ただし \[\sigma_{1}\ge\sigma_{2}\ge\ldots\ge\sigma_{r}>\sigma_{r+1}=\ldots=\sigma_{n}=0.\] を の特異値と呼ぶ。また 、 を 次元列ベクトル 、 次元列ベクトル を用いて 、 と表すと、 上式は\[A=\sum_{i=1}^{\min\{m,n\}}\sigma_{i}u_{i}{}^{t}\bar{v}_{i}\]と書き表すことが出来る。 ここで 、 がユニタリ行列より 、 は線型空間 、 の正規直交基底である。

証明   はエルミート行列であるから対角化可能である。 の任意の固有値を 、それに対する長さ１の固有ベクトルを とすると \[\lambda=\lambda\|x\|^{2}=\left(x,A^{*}Ax\right)=\|Ax\|^{2}\ge0\]より の固有値は非負であるから、 の 固有値分解は \[A^{*}A=\sum_{i=1}^{n}\sigma_{i}^{2}v_{i}{}^{t}\bar{v}_{i}\]と書ける。 ただし は となるように並べるものとする。
さて、 を \[u_{i}:=\frac{1}{\sigma_{i}}Av_{i},\quad i=1,2,\ldots,r\]で定義すると、 は\[(u_{i},u_{j})=\frac{1}{\sigma_{i}\sigma_{j}}\left(v_{i},A^{*}Av_{j}\right)=\delta_{ij}\] を満たす、つまり長さが１で互いに直交しているベクトルの集合である。 さらに を適当に定め、 が の正規直交基底になるようにする。
( ) の定義、および ( )から \[\sum_{i=1}^{\min\{m,n\}}\sigma_{i}u_{i}{}^{t}\bar{v}_{i} =\sum_{i=1}^{r}\sigma_{i}u_{i}{}^{t}\bar{v}_{i}=A\left(\sum_{i=1}^{r}v_{i}{}^{t}\bar{v}_{i}\right)=AP\]が成り立つ。 ここで とした。
一方、任意の に対して \[\begin{split}A^{*}A(1-P)x & =\left(\sum_{i=1}^{n}\sigma_{i}^{2}v_{i}{}^{t}\bar{v}_{i}\right)\left(\sum_{j=r+1}^{n}v_{j}{}^{t}\bar{v}_{j}\right)x\\ & =\sum_{i=r+1}^{n}\sigma_{i}^{2}\left(v_{i},x\right)v_{i}\\ & =0\end{split}\] より\[\|A(I-P)x\|^{2}=\left((I-P)x,A^{*}A(1-P)x\right)=0,\]つまり が成り立つ。
以上より\[A=AP+A(I-P)=\sum_{i=1}^{\min\{m,n\}}\sigma_{i} u_{i}{}^{t}\bar{v}_{i}\]となる。（証明終）

行列の低ランク近似

特異値分解の応用として、行列の低ランク近似を取り上げます。

行列 の特異値分解\[A=\sum_{i=1}^{\min\{m,n\}}\sigma_{i}u_{i}{}^{t}\bar{v}_{i}\]において、 途中の 番目まで和をとって出来る行列 \[A_{k}=\sum_{i=1}^{k}\sigma_{i}u_{i}{}^{t}\bar{v}_{i},\quad k=1,2,\ldots,\min\{m,n\}\] を考えてみましょう。実は、こうして作られる が行列 の持つ情報を 要約したもの（低ランク近似）になっているのですが、このことを画像データを使って視覚的に確認してみたいと思います。

まず次の画像（750 1125ピクセル、8ビットグレイスケール）の輝度を画像処理ソフトを使って テキストデータ（000.csv）として出力します。

画像の輝度が作る行列を とします。 は 750 行 1125 列の行列であり、 の各成分は 0 から 255 までの整数となっています。 この行列 を特異値分解して行列 を計算します。 を算出するために用いた R のコードは以下の通りです。

library(stringr)
file_path <- "C:\\work\\"

# 特異値分解
A <- read.table(str_c(file_path,"000.csv"))
svd_A <- svd(A)

# 近似行列の計算
for (k in c(1,5,10,15,20,25,30,35,40,45,50,75,100,750)){
  
  d <- diag(svd_A$d)[1:k, 1:k, drop=F]
  u <- svd_A$u[,1:k, drop=F]
  v <- svd_A$v[,1:k, drop=F]

  write.table(round(u %*% d %*% t(v)),
              str_c(str_c(file_path,formatC(k,width=3,flag="0")),".csv"),
              sep="\t", row.names=FALSE, col.names=FALSE)
}

出力されたcsvファイルをグレイスケール画像に変換したものが以下の図になります。

の場合 の場合 の場合 の場合 の場合 の場合

実験の結果からは、 を大きくするにつれて徐々に元の画像が再現されていく様子が確認出来ます。 また に比べてそれほど大きくない で元の画像の情報が再現されていることも分かります。

さて、ここで が画像データではない場合（例えば統計調査によって得られたデータ等）を考えましょう。 このとき が に徐々に近づいていくという現象を画像データの時と同様に確認することが出来るのでしょうか？ 画像データの時とは異なり、視覚的に確認するという手は使えません。

実は、近似の度合いを行列に対するノルム*7を使って定量的に評価することが出来ます。

定理３   を 行列のユニタリ不変ノルムとする。 つまり任意の 次、 次ユニタリ行列 、 に対して\[\|UAV\|=\|A\|\]が成り立つとする。 このとき による の近似は、ユニタリ不変ノルムに関して、階数が 以下の行列による近似の中で最良の近似になっている： \[\min_{\substack{B\in\mathrm{Mat}(m,n);\\\mathrm{rank}(B)\le k}}\|A-B\|=\|A-A_{k}\|.\] 特に作用素ノルム\[\|A\|_{op}:=\sup_{x\in\mathbf{K}^{n}\backslash\{0\}}\frac{\|Ax\|}{\|x\|}\]に関して \[\min_{\substack{B\in\mathrm{Mat}(m,n);\\\mathrm{rank}(B)\le k}}\|A-B\|_{op}=\|A-A_{k}\|_{op}=\sigma_{k+1},\] またフロベニウスノルム（ヒルベルト-シュミットノルム） \[\|A\|_{F}:=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}|A_{ij}|^{2}}=\sqrt{\sum_{i=1}^{\min\{m,n\}}\sigma_{i}^{2}}\]に関して \[\min_{\substack{B\in\mathrm{Mat}(m,n);\\\mathrm{rank}(B)\le k}}\|A-B\|_{F}=\|A-A_{k}\|_{F} =\sqrt{\sum_{i=k+1}^{\min\{m,n\}}\sigma_{i}^{2}}\]が成り立つ。

特異値が降順に並んでいたことを思い出すと、上記の定理により を大きくするに従って は に 徐々に近づいていくことが分かります。

最後に

本記事を執筆するにあたり参考にした文献を紹介します。

• 新井仁之, 線形代数 基礎と応用, 日本評論社, 2006

画像データを使った近似行列に関する議論は、この書籍の16.4節を参考にさせて頂きました。500ページ超とかなりボリュームのある書籍ですが、記述自体はとても丁寧であり、読み進めるのに苦労することは（多分）無いと思います。

さて、特異値分解について駆け足で見てきましたが如何だったでしょうか。記事の中でベクトルや行列について簡単に復習はしましたが、実際はこれらの概念に馴染んでいないと読み通すのは難しかったのではないでしょうか。

ベクトルや行列に馴染みの無い方は、これを機会に勉強を始めてみては如何でしょうか。馴染むまでには多少時間は掛かるかもしれませんが、機械学習や統計学の書籍を読むのに必須の知識であり、投資しただけのリターンは確実にあると思います。

*1:固有値分解についての証明は行いません。大学初年時の講義で使われるような線型代数学の教科書であれば、大抵は載っていますのでそちらを参照してください。

*2:特異値分解は内容的には線型代数学の領域に属しますが、線型代数学の書籍の多くが大学初年時に行われる授業の教科書として編纂されているということもあり、応用色が強い特異値分解について、証明付きで解説している書籍はそう多くはありません。

*3:数学の書籍では 側ではなく 側で複素共役をとる流儀が多いと思われます。ちなみに 側で複素共役をとる流儀は物理学の書籍で多く見られます。

*4:実際、線型代数学の教科書には固有方程式を解いて固有値を求める演習問題があります。

*5:いわゆるガロア理論による帰結です。

*6:行列 が対角化可能であるためには、 が正規行列、つまり を満たすことが必要十分であることが知られています。 当然ですが、エルミート行列は正規行列です。

*7:行列 、 に対して、 ()、 ()、 を 満たす のことをノルムと言います。

そうだAsta4dでWebアプリケーションを作ろう(第5回)

Global Handlerとattribute

今回はHandlerの話の続きです。 Handlerの簡単な役割については前回書きましたので、そちらをご覧になってから読んでいただくと理解が深まると思います。 たぶん。

で、今回書く話は個別のルール毎にコントロールを行うHandlerではなく、サイト全体や特定の属性のコントロールを行うHandlerのお話です。

今回のURLルール

package com.astamuse.blog_sample.rules;

import static com.astamuse.asta4d.web.dispatch.HttpMethod.GET;

import com.astamuse.asta4d.web.dispatch.mapping.UrlMappingRuleInitializer;
import com.astamuse.asta4d.web.dispatch.mapping.ext.UrlMappingRuleHelper;
import com.astamuse.blog_sample.handler.DefaultHandler;
import com.astamuse.blog_sample.handler.Handler;
import com.astamuse.blog_sample.handler.LoginCheckHandler;

public class UrlRules implements UrlMappingRuleInitializer{
    private static final String LOGIN_CHECK = "LOGIN_CHECK";

    public void initUrlMappingRules(UrlMappingRuleHelper rules) {
        rules.addDefaultRequestHandler(DefaultHandler.class);
        rules.addDefaultRequestHandler(LOGIN_CHECK, LoginCheckHandler.class);
        rules.add(GET, "/").forward("/html/index.html");
        rules.add(GET, "/{id:[0-9]+}").attribute(LOGIN_CHECK).handler(Handler.class);
    }
}

前回から追加した点を説明していきます。

rules.addDefaultRequestHandler(DefaultHandler.class);
rules.addDefaultRequestHandler(LOGIN_CHECK, LoginCheckHandler.class);

まずはURLルールに今回必要なルールを追加しています。 全体や属性のコントロールなので、個別のルール対してHandlerを設定するのではなくaddDefaultRequestHandlerを使ってルール全体へのコントロールを追加します。

引数1つの場合は、全てのリクエストに対してのルールに対しての処理になり、2つ場合は1つ目の引数に属性を入れてあげて属性が付与されているルールのリクエストに対してのみ処理が行われます。 属性に関してはString型です。定数を作ってあげると管理が楽です。 被ると大惨事が発生してしまうので気を付けなければなりません。 (先に書いた方の処理しか走りません)

rules.add(GET, "/{id:[0-9]+}").attribute(LOGIN_CHECK).handler(Handler.class);

属性を付与する際は個別のルールに対してattibuteで付与します。 こうすることで独自のHandlerの前にaddDefaultRequestHandlerで指定した処理を行ってくれます。

Handlerの実装

package com.astamuse.blog_sample.handler;

import com.astamuse.asta4d.web.dispatch.request.RequestHandler;
import com.astamuse.asta4d.web.dispatch.response.provider.RedirectTargetProvider;

public class LoginCheckHandler {

    @RequestHandler
    public RedirectTargetProvider handle() {
        System.out.println("call LoginCheckHandler");
        return new RedirectTargetProvider("/");
    }
}

package com.astamuse.blog_sample.handler;

import com.astamuse.asta4d.web.dispatch.request.RequestHandler;

public class DefaultHandler {

    @RequestHandler
    public void handle() {
        System.out.println("call DefaultHandler");
    }
}

今回は本題と関係ないので適当です(動けばいいというダメな精神)。 本来であればここで適切なコントロールをすることになります。 Handlerの書き方についてはどんなやり方の時も特に違いはありません。

Global Handlerの実使用例

それでは、実際のケースにおいてどのように使用されているか見ていきましょう。

• ログイン必須ページのログインチェック
• レスポンスにヘッダを設定(主にキャッシュコントロールで使用しています)
• WebAPIの共通チェック

みたいな使い方が例となります。

特定のObjectがHandlerから返却された場合のGlobal処理について

Handlerより特定のObjectが返却された際に表示するページのコントロールを行う方法を合わせて紹介します。 Asta4dでは、Global Forwardの機能が提供されており、特定のObjectが返却された場合、レスポンスステータスと返却するhtmlファイルを指定することが可能となっています。

rules.addGlobalForward(TemplateNotFoundException.class, "/html/error/404.html", 404);

ここではforward先がなかった時にasta4d内で発生するTemplateNotFoundExceptionが発生した場合に404を返すルールを追加しています。

使用例としてはException発生時のエラーコントロールが主となっている。

終わりに

この仕組みを使うことでルールに属性を付与することが可能となり、どのような処理が必要かが一目で分かりやすく表現することが可能になります。

次回予告

最終回はFormを簡単に作れちゃうForm Flowについて説明しようと思います。

関連URL

第1回：環境構築して静的ページを表示するまで
第2回：Snippetを使って動的ページを作ろう
第3回：少し複雑なSnippet
第4回：Handlerの役割と使い方
第5回：Global Handlerとattribute(今ここ)
第6回：Form Flowを使おう