2017-07-15

加藤昌治『考具 -考えるための道具，持っていますか？』，CCCメディアハウス，2003

書評ビジネス思考術

　専門書ばかりを読んでいて時間がなかったのだが，一段落ついたので久々に本を読んでみた．毎日寝る前の30分を読書に充てれば，一週間で一冊は読めそう．読書習慣を取り戻していきたい．
　今回読んだのは，博報堂で働くアイデアマンが書いた『考具』．

作者: 加藤昌治
出版社/メーカー: CCCメディアハウス
発売日: 2003/04/04
メディア: 単行本（ソフトカバー）
購入: 37人クリック: 305回
この商品を含むブログ (293件) を見る

著者のページ考具Web! 考える、を普通の習慣に。の中では以下のような記述がある．

　スポーツには競技ごとに特有の「カラダの動かし方」があります。それを体得しない限りはいきなり試合に出たって活躍はできません。

　そうですよね？

　しかし「考える」「アイデアを出す」「企画をこさえる」については、ただ闇雲に「やれ（試合に出ろ）」と云われるばかりで、カラダとアタマの動かし方については教えてもらえる機会がほとんどありません。

全く同じことを思っていたので，衝動買いしてしまった．修士課程では課題解決プロセスの中でも「調査」「課題発見」を鍛えることができた．一方で，発見した課題に対して解決策を考える方法のトレーニングはあまり積めなかった結果，アイデアを出すことについては苦手意識がある．だから惹かれたのだろう．

　本書の中で「アイデア」は，ジェームス・ウェブ・ヤング著の『アイデアのつくり方』での定義「既存の要素の新しい組み合わせ以外の何物でもない」とされている．このため，必要となるのは，

アイデアを出すために必要なインプットの方法
溜めたインプットを効率的に引き出してアイデアを量産する方法
出したアイデアを企画に収束させる方法

の3つ．

　具体的な考具のメモに移る前に，印象的だった箇所を．

　考えるための道具＝考具という考え方，そしていくつかの考具の使用法を取り上げてきました．いろんな工具がありますし，使い方によってはどんなものでも考具になります．そしてどんな考具であっても結果としては同じことで，アイデアを出し，企画を立てる時の頭の動き方をより自然に，よりスムーズにすることが目的です．

全ての考具を使いこなせる必要はなくて（もちろん使いこなせた方が良いのだろうが），自分にとって使いやすい考具を使ってアイデアを出し，企画に出来ればそれでOK，ということ．以下で自分にとって使いやすそうな考具をまとめていく．

アイデアを出すために必要なインプットの方法

1. カラーバス

　家を出る前に，今日一日着目する色を決めて，その色を持つものを見つける手法．もちろん形状や位置，音など色以外でも良いが，最初はハードルの低い色から．ということで「青」に注目してみたが，いつも通っている道でも結構目につく．
試した結果，研修で「人間は聞きたい／知りたいと思っていることしか聞けない／知れない」と言われたことを思い出した．（「知りたい」を明確にするためにも先にアジェンダを教えてくれ，と思ったが）

2. ちょいメモ

　人はすぐに忘れる生き物なので，メモをする．何に書いても構わない．思いついたものがアイデアなら，ある程度溜まったらどこかにまとめておくと良いかもしれない．グループワークで同僚が白紙の自由帳を持ち歩いていて非常に良いな〜と思ったので，真似して白紙にメモをしてみる．

3. 七色いんこ

　自分でやってみると，色々なところが気になる／目につく，という話．その通りである…

溜めたインプットを効率的に引き出してアイデアを量産する方法

1. アイデアスケッチ

　紙やスライドに，アイデアのタイトルと3行くらいの説明文を書く．説明文の内容は必要性とかなんでも良いと思われる．

2. マンダラート

　個人的に一番使いやすいと思ったフレームワーク． 3×3の表を書いて，中心に課題や質問を置く．そして，それに関連する要素で周囲のマスを埋める．埋めたら任意のマスに書かれた要素に対して更にマンダラを開き，同様にマスを埋めていく．
　何が良いかというと，8個という明確なゴールがある点．ブレストやマインドマップも同じことをやっているはずなのだが，いくつ出せばええんや〜となるので，1つのマンダラに対して8つという終了条件があるのは，終わりが見えないことを続けられない自分にはピッタリ．

3. 連想ゲーム

　そのまんま．関係ないものを連想してもOK（そのうち仕事に関連するものを連想するので）．

4. オズボーンのチェックリスト

　詰まった時はコレ．

- 転用したら？  
    現在のままでの新しい使い道は？
- 応用したら？  
    似たものはないか？真似はできないか？
- 変更したら？  
    意味，色，動きや匂い，形を変えたらどうする？
- 拡大したら？  
    大きくする，長くする，頻度を増やす，時間を延ばすとどうなる？
- 縮小したら？  
    小さくする，短くする，軽くする，圧縮する，短時間にするとどうなる？
- 代用したら？  
    代わりになる人や物は？材料，場所などを変えられないか？
- 置換したら？  
    入れ替えたら，順番を変えたらどうなる？
- 逆転したら？  
    逆さまにしたら？上下左右・役割を反対にしたら？
- 結合したら？  
    合体，混ぜる，合わせたらどうなる？

出したアイデアを企画に収束させる方法

1. 5W1H

　テンプレ．What, How, Who, Why, When, Where(, How much)．

2. マンダラート

　中心をWho，それ以外をWhat, Where, When, Whyとしてマンダラを開く．その結果，更にマンダラを開いたりしても良い．

　本書を補足する『アイデアはどこからやってくるのか』も一緒に購入したので，借りているアジャイル開発の本を早く読み終えたい．

アイデアはどこからやってくるのか考具基礎編

作者: 加藤昌治
出版社/メーカー: CCCメディアハウス
発売日: 2017/03/01
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

2017-06-27

ISLR: Chapter 9 Support Vector Machine

数学機械学習統計学 ISLR

9.1　Maximal Margin Classifier

9.1.1　What is a Hyperplane?

9.1.2 　Classification Using a Separating Hyperplane

　magnitude of $f(x^{*})$ :　 $f(x^{*})$ が超平面から離れてるほど予測の確信度が高い．逆に，あまり離れてなければ疑わしい．

9.1.3　The Maximal Margin Classifier

　分離平面と，それに最も近い観測との距離をマージンという．このマージンを最大化するように学習して良い分類を期待するのは自然な発想．でもマージン最大化は $p$ が大きいと過学習してしまう．

　マージンから最小の距離にあるサンプルをサポートベクターという．超平面の上下で最低2つは存在する．

9.1.4　Construction of the Maximal Margin Classifier

　マージン $M$ の最大化は最適化問題として以下のように書ける． $\displaystyle \begin{align} \max_{\beta_0,\ \beta_1,\ldots,\ \beta_p} M,\ \mbox{subject to }\sum_{j=1}^{p}\beta_j^{2}=1,\ y_i(\beta_0+\sum_{j=1}^{p}\beta_jx_{ij}) \geq M\ \ \forall i=1,\ldots,n \end{align}$ 制約の後者は全てのサンプルがマージンを境界として正しく分類されていることを意味している．前者は，パラメタを大きくしてしまえば後者の制約の右辺 $M$ よりも左辺を大きくすることが可能になってしまうので，総和が1という制約を設けている．

9.1.5　The Non-separable Case

　マージン最大化は，そもそも分離可能な超平面が存在する時はうまくいくが，存在しない場合の方が圧倒的に多い．というわけで，いくつか誤分類してても良いですよ，というようにマージンを拡張したソフトマージンを考える．このキレイに分離できない場合に対してマージン最大化分類器を一般化したものがSupport Vector Classifier．

9.2　Support Vector Classifiers

9.2.1　Overview of the Support Vector Classifier

　Support Vector Classifierは個別の観測に対してロバストで，かつ，多くの訓練用の観測に対してうまく分類できるsoft margin classifierの一種．

9.2.2　Details of the Support Vector Classifier

　Support Vector Classifierは最適化問題として以下の形で書ける． $\displaystyle \begin{align} \max_{\beta_0,\ \beta_1,\ldots,\ \beta_p} M \end{align}$ $\displaystyle \begin{align} \mbox{subject to }\sum_{j=1}^{p}\beta_j^{2}=1,\ y_i(\beta_0+\sum_{j=1}^{p}\beta_jx_{ij}) \geq M(1-\epsilon_i)\ \ \forall i=1,\ldots,n, \end{align}$ $\displaystyle \begin{align} \epsilon_i \geq 0,\ \sum_{i=1}^{n}\epsilon_i \leq C \label{slack} \end{align}$ $C$ は非負のパラメタ． $\epsilon_1,\ldots,\epsilon_n$ はどれくらい誤分類を許すかを表すスラック変数． $\epsilon_i=0$ の時はマージンの外側にある． $\epsilon_i>0$ ならば，マージンを超えて超平面に近づいた状態． $\epsilon_i=1$ なら超平面の向こう側，つまり，完全な誤分類になる． $C$ はクロス・バリデーションとかで決める．こいつがバイアス・バリアンスのトレードオフを決める．式 $\eqref{slack}$ を見て分かる通り， $C$ が小さければ誤分類を認めない狭いマージンになり， $C$ が大きければ大きなマージンになる．

　面白いのは，Support Vector Classifierのは全ての観測ではなく，サポートベクターとマージン内の観測のみで決まる点．

9.3　Support Vector Machines

9.3.1　Classification with Non-linear Decision Boundaries

　Support Vector Classifierは線形分離可能な時に使う．非線形に分離したい時は二乗の項や相乗項を追加し，それに対応して制約も追加する．そうすると，追加された項を含めた時は線形に分離できるが，元の変数のみでは非線形な分離平面を得ることができる． $\displaystyle \begin{align} \max_{\beta_0,\ \beta_1,\ldots,\ \beta_p} M \label{margin} \end{align}$ $\displaystyle \begin{align} \mbox{subject to }\sum_{j=1}^{p}\beta_j^{2}=1,\ y_i(\beta_0+\sum_{j=1}^{p}\beta_{j1}x_{ij} + \sum_{j=1}^{p}\beta_{j2}x_{ij}^{2}) \geq M(1-\epsilon_i)\ \ \forall i=1,\ldots,n, \label{const1} \end{align}$ $\displaystyle \begin{align} \epsilon_i \geq 0,\ \sum_{i=1}^{n}\epsilon_i \leq C,\ \sum_{j=1}^{p}\sum_{k=1}^{2}\beta_{jk}^{2}=1 \label{const2} \end{align}$

9.3.2　The Support Vector Machine

　SVMはカーネルを使って高次元に写像された特徴空間を用いて得られるSupport Vector Classifierの拡張の一種らしい．

　Support Vector Classifierを，内積を使って書くと下式になる． $\displaystyle \begin{align} f(x)=\beta_0+\sum_{i=1}^{n}\alpha_i \langle x, x_i \rangle,\ \mbox{where } \langle x_i, x_{i'} \rangle = \sum_{j=1}^{p}x_{ij}x_{i'j} \end{align}$ $n$ 個のパラメタ $\alpha_i$ は観測の一つ一つに対応する．具体的には，その観測がサポートベクターなら非0，そうでないなら0．パラメタ $\alpha_1,\ldots,\alpha_n,\ \beta_0$ を求めるために ${}_nC_2$ 個の内積 $\langle x_i, x_{i'} \rangle$ を計算する必要がある．ただサポートベクターでない項は結果に効いてこないので，インデックス $S$ を使うと以下のように書き換えられる． $\displaystyle \begin{align} f(x)=\beta_0+\sum_{i \in S}\alpha_i \langle x, x_{i} \rangle \end{align}$ こうした方が計算軽いよね，という話．

　内積を一般化して，カーネル $K(x_i,x_{i'}$ を考える．カーネルが内積の場合，つまり， $\displaystyle \begin{align} K(x_i,x_{i'})=\sum_{j=1}^{p}x_{ij}x_{i'j} \end{align}$ の時は線形カーネルになる．これを使ったSVMは単なるSupport Vector Classifier．線形カーネルは観測のペアの類似度をピアソン相関係数を使って定量化していることになるらしい．

　また，多項式カーネルというのもある． $\displaystyle \begin{align} K(x_i,x_{i'})={(1+sum_{j=1}^{p}x_{ij}x_{i'j})}^{d} \end{align}$ $d>1$ なら線形カーネルよりも柔軟な決定境界が得られる．多項式カーネルは，本質的には，d次の項を含んだSupport Vector Classifierだと言える．

　SVMは以下の通り．ただ単にSVCの内積の項をカーネルで一般化しただけ． $\displaystyle \begin{align} f(x)=\beta_0+\sum_{i \in S}\alpha_i K(x,x_{i}) \end{align}$

　多項式カーネルと同様に，非線形な決定境界を与えるカーネルとしてradial kernelがある． $\displaystyle \begin{align} K(x_i,x_{i'})=\exp \bigl(-\gamma \sum_{j=1}^{p}{(x_{ij}-x_{i'j})}^{2} \bigr),\ \mbox{where }\gamma > 0 \end{align}$ こいつがどう動くのか？新たな観測 $x^{*}$ を予測したいとする． $x^{*}$ と訓練データ中のある観測 $x_i$ とのユークリッド距離はかなり離れているとする．そうすると， $\sum_{j=1}^{p}{(x_{ij}-x_{i'j})}^{2}$ は大きくなるのだが， $\exp$ を取ってるので，最終的な値は非常に小さくなる．要するに，観測から離れた訓練データは類似度を計算する上でほぼ機能せず，観測に近い位置にある訓練データのみを用いてラベルを予測している．

　カーネルの何が嬉しいかというと，高次元特徴空間を明示的に触る必要がない点が良い．つまり，手持ちの要素の ${}_nC_2$ 通りの組み合わせに対する $K(x_i,x_{i'}$ の演算だけで，高次元空間で操作した結果と同じ結果を得られるのが良い．

9.3.3　An Application to the Heart Disease Data

9.4 SVMs with More than Two Classes

9.4.1　One-Versus-One Classification

　多クラス分類する時はOne-Versus-Oneという手法がある．これは ${}_KC_2$ 個の分類器を造って，全ての分類機に対して入力を与え，最も多く予測されたクラスを結果として与える．

9.4.2　One-Versus-All Classification

　 $k$ 番目のクラスだったら+1，そうでないなら-1とする $K$ 個の分類器を作って，各分類機に入力を与え，分類機による結果が最も大きい分類機が属するクラスを，予測結果とする．

9.5　Relationship to Logistic Regression

　サポートベクター分類器 $\displaystyle f(X)=\beta_0+\sum_{j=1}^{p}\beta_jX_{j}$ に関する式 $\eqref{margin}-\eqref{const2}$ は以下のように書き換えられる． $\displaystyle \begin{align} \min_{\beta_0,\ \beta_1,\ldots,\beta_p} \biggl\{ \sum_{i=1}^{n}\max [0, 1-y_if(x_i)]+\lambda \sum_{j=1}^{p} \beta_j^{2} \biggr\},\ \mbox{where }\lambda > 0 \label{rewrite} \end{align}$ $\lambda$ が大きければ $\beta_1,\ldots,\beta_p$ は小さくなり，より多くの観測がマージン内に位置づけられる．結果としてlow-varianceでhigh-biasな分類器が出来上がる． $\lambda$ が小さければ，逆に，high-varianceでlow-biasな分類器が出来上がる．そういうわけで $\lambda$ は式 $\eqref{slack}$ の $C$ と同じ役割を果たしている．また，式 $\eqref{rewrite}$ にはRidge罰則項があるが，これがsupport vector classifierにおけるbias-varianceトレードオフをコントロールしている．式 $\eqref{rewrite}$ は損失関数と罰則項を使って以下のようにも書き換えられる． $\displaystyle \begin{align} \min_{\beta_0,\ \beta_1,\ldots,\beta_p} \{ L(\mathbf{X},{\bf y},\beta)+\lambda P(\beta) \},\ \mbox{where }\lambda > 0 \label{rewrite2} \end{align}$ $L$ はパラメタ $\beta$ の下でデータ $(\mathbf{X},\bf{y})$ にフィットさせた際の損失， $P(\beta)$ はパラメタ $\beta$ についての損失関数．RidgeやLassoなら損失は最小二乗法になるし，罰則項はL2ノルムの2乗もしくはL1ノルムになる．式 $\eqref{rewrite}$ の場合は $\displaystyle \begin{align} L(\mathbf{X},{\bf y},\beta)=\sum_{i=1}^{n}\max [0, 1-y_i(\beta_0+\beta_1x_{i1}+\ldots+\beta_px_{ip})] \end{align}$ になり，こいつはヒンジロスと呼ばれてるらしい．Fig 9.12を参照してほしいのだが，ヒンジロスは $y_i(\beta_0+\beta_1x_{i1}+\ldots+\beta_px_{ip})$ が1を超えた場合0になってる．これは結局マージンの正しい方，つまりサポートベクターではない例に反応しているので，そうしたデータはSVMがラベルを予測する上で使われないことに対応してる．一方ロジスティック回帰のロスは，ヒンジロスを滑らかにしたような結果になってる．そういうわけでSVMとロジスティック回帰はある意味似ており，かなり似た結果を返す．使い分けとしては，クラス間が明確に分離できるならSVM，そうでないならロジスティック回帰の方が精度が出るらしい．

2017-06-25

ISLR: Chapter 8 Tree-Based Methods

数学機械学習統計学 ISLR

8.1　The Basics of Decision Trees

8.1.1　Regression Trees

Predicting Baseball Players' Salaries Using Regression Trees

Prediction via Stratification of the Feature Space

　regression treeの構築方法は以下の2ステップ．

説明変数 $X_1, X_2,\ldots , X_p$ を，重複がないように $J$ 個の領域 $R_1, R_2, \ldots , R_J$ に切り分ける．
全ての $R_J$ について，観測が $R_J$ に属する場合は， $R_J$ に属する訓練データの平均値を予測値として返す．

　どうやって $R_J$ を見つけるかが問題だが，残差二乗和が最小になるようにする． $\displaystyle \begin{align} \sum_{j=1}^{J}\sum_{i \in R_j} {(y_i-\hat{y}_{R_j})}^{2} \end{align}$ ここで， $\hat{y}_{R_j}$ は $R_j$ に属する訓練データの平均値，要するに決定木による予測値を表す．もう少し具体的に言うと， $R_1(j,s)={X\mid X_j \lt s} \mbox{ and } R_2(j,s)={X\mid X_J \geq s}$ となる $s$ を見つけなければならないが，それを残差二乗和が最小になるように決めるということ．つまり，下式を最小化するような $j,s$ を求める． $\displaystyle \begin{align} \sum_{i:x_i\in R_1(j,s)} {(y_i-\hat{y}_{R_1})}^{2} + \sum_{i:x_i\in R_2(j,s)} {(y_i-\hat{y}_{R_2})}^{2} \end{align}$ で，終了条件を満たすまでこれを繰り返していくと分岐がどんどん増える．

Tree Pruning

　ところが上の方法でできる決定木は複雑過ぎるので過学習になりやすい．そこで，バイアスを少し大きくする代わりに，より分散が小さく，かつ解釈しやすい木が欲しい．

　では，どうやるのか？一度巨大な木 $T_0$ を作って，そこから部分木を刈り取っていく．Cost complexity pruningもしくはweakest link pruningと呼ばれる効率的な刈り取り方がある．これは以下の式を最小化する． $\displaystyle \begin{align} \sum_{m=1}^{|T|}\sum_{x_i\in R_m} {(y_i-\hat{y}_{R_m})}^{2}+\alpha |T|,\mbox{ where } T \subset T_0\mbox{ and }\alpha > 0 \end{align}$ $|T|$ はterminal nodesの総数．部分木の数が増えると $|T|$ の項が最小化において効いてくるので，結果的に小さくなる． $\alpha$ はvalidation setもしくはcross-validationで決める．詳細は以下のアルゴリズムの通り．

各terminal nodeの中の観測の個数が一定数以下になるまで領域に分割する．
$\alpha$ の関数としてcost complexity pruningを適用する．
K-fold cross-validationを行う．For each $k=1,\ldots, K:$
1. Step1, 2をk番目のデータセット以外に適用する．
2. $\alpha$ の関数として，k番目のデータセットを除いたMean squared prediction errorを求める．そして， $\alpha$ 毎に結果を平均し，average errorが最小となる $\alpha$ を選択する．
Step 3で求まった $\alpha$ をStep 2で求めた関数に代入し，部分木を返す．

8.1.2　Classification Trees

　予測として返すのは，その領域に含まれている観測の中で最も属する観測が多いクラス．Regression Treesでは残差二乗和を使ってたが，Classfication Treesではそれに対応する概念として，classification error rate $E$ を用いて定義されるジニ係数がある． $\displaystyle \begin{align} E=1 - \max_{k}\hat{p}_{mk} \end{align}$ ここで， $\hat{p}_{mk}$ は $R_m$ に含まれる観測におけるクラス $k$ の比率．したがって， $E$ で求まるのは， $R_m$ で最も出現しているクラスに属していない観測の割合ということになる．また，ジニ係数は以下のように定義される． $\displaystyle \begin{align} G=\sum_{k=1}^{K}\hat{p}_{mk}(1-\hat{p}_{mk}) \end{align}$ 結局これは $K$ 個のクラスについて分散を求めており， $\hat{p}_{mK}$ が0か1に近ければジニ係数は非常に小さくなるので，node purityを測るのに使われる．ジニ係数が小さければ，領域内でのクラスのばらつきの少ない木ということになる．また，ジニ係数の代わりとしてクロス・エントロピーもある． $\displaystyle \begin{align} D=-\sum_{k=1}^{K}\hat{p}_{mk}\log \hat{p}_{mk} \end{align}$ $0 \leq \hat{p}_{mk} \leq 1$ というのは $0 \leq -\hat{p}_{mk}\log \hat{p}_{mk}$ であるので，クロス・エントロピーはジニ係数と同様の尺度として扱える．そういうわけで，ジニ係数とクロス・エントロピーはclassification error rateよりもnode purityに強く反応するので，pruningする際に使われる．classification error rateはprediction accuracyを重視する時はジニ係数やクロス・エントロピーよりも良い指標になる．

8.1.3　Trees Versus Linear Models

　線形回帰は $\displaystyle \begin{align} f(X)=\beta_0+\sum_{j=1}^{p}\beta_jX_j \end{align}$ であるのに対し，regression treeは $\displaystyle \begin{align} f(X)=\sum_{m=1}^{M}c_m\cdot 1_{(X\in R_m)} \end{align}$ という形を取るので，かなり違う．というわけで気になるのはどちらが優れているのか．問題が線形に近いなら線形回帰の方が良いし，そうでないならregression treeの方が良い場合が多い．とは言えどのくらいモデルを解釈したいか，可視化したいかというのも手法選択の規準になりうるので，目的に合わせて自分で選べという感じ．

8.1.4　Advantages and Disadvantages of Trees

メリット
- 決定木の方が線形回帰よりも人に説明しやすい．
- 決定木による分類は，これまでの章で扱ってきた手法よりも人の意思決定に近いと信じる人もいる（なんのこっちゃ）
- 可視化が楽なので専門家でなくても解釈しやすい
- 質的データに対してわざわざダミー変数を作らなくても木を構築できるため，他の手法よりも質的な説明変数を扱いやすい
デメリット
- 決定木は他の手法よりも予測精度が悪い
- 決定木はrobustじゃない．つまり，データが変われば簡単に木構造が変わってしまう．

　ただし，Bagging, Random Forests, Boostingを使えば予測精度は上がる．

8.2　Bagging, Random Forests, Boosting

8.2.1　Bagging

　決定木は分散が大きいのでつらい．そこでbootstrapを応用したBaggingを考える．bootstrapは欲しい量の標準偏差を直接求めることが困難な場合に使われる．具体的には，それぞれの分散が $\sigma^{2}$ であるようなn個の観測集合 $Z_1,\ldots , Z_n$ を平均すると，平均した観測集合の分散が $\displaystyle \frac{\sigma^{2}}{n}$ になり，結果的にデータセットの分散が小さくなってハッピー，だからなるべく母集団からたくさんの観測をサンプルしようという話でした．

　Baggingは，bootstrapでたくさんデータセットを生成し，それらを用いて $\hat{f}^{*b}(x)$ を求め，平均する．つまり， $\displaystyle \begin{align} \hat{f}_{bag}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{*b}(x). \end{align}$ もちろんBaggingは他の手法にも適用可能だが，決定木には特に有効．というのもそれぞれの決定木はhigh variance, low biasだが，それらを平均すると分散が小さくなるから．分類問題に対しては，それぞれの決定木で予測し，その結果の中で最も多かった予測値を採用するという方法で対応可能．

Out-of-Bag Error Estimation

Variable Importance Measures

8.2.2　Random Forests

　Baggingとほぼ同じ．違いは，Baggingでは各ブートストラップサンプルに対し全ての変数を用いて決定木を構築していたのに対し，Random Forestsでは各ブートストラップサンプルに対しランダムに選択された $m$ （ $m \approx \sqrt{p}$ とすることが多いらしい）個の変数を使って決定木をサンプルの個数分作る．Baggingと比べて変数の数が少ないので，結果的に，各木の分散が小さくなって良い．

8.2.3　Boosting

　BaggingやRandom Forestsのようなもの，これらは並列計算できるが，Boostingはその前のモデルに依存して新しいモデルが作られるので並列計算不可．また，Boostingは他の手法にも適用可能．パラメタとしては $\lambda$ （よく使われるのは0.01もしくは0.001），サンプル数 $B$ （ $\lambda$ が大きければ $B$ も大きい必要があるが，過学習しやすくなる），各木の分割数 $d$ の3種類．最適な $B$ はクロス・バリデーションで決める．

2017-06-17

ISLR: Chapter 7 Moving Beyond Linearity

数学統計学機械学習 ISLR

　これまで扱ってきた線形モデルは解釈や推論のしやすさという面では他のモデルよりも優れているが，代わりに予測性能には限界がある．本章では線形仮定を緩和しつつ，できるだけ解釈のしやすいモデルを紹介する．

7.1　Polynomial Regression

　多項式回帰． $\displaystyle \begin{align} y_i=\beta_0+\beta_1x_i+\beta_2x_i^{2}+\beta_3x_i^{3}+\ldots+\beta_dx_i^{d}+\epsilon_i \end{align}$ 3, 4以上の次数はあまり使わないらしい．

　推定値 $\hat{f}(x_0)$ の分散 $Var[\hat{f}(x_0)]$ は，例えば， $\hat{C}$ を $5 \times 5$ の共分散行列とし， $\ell_0^{T}=(1,x_0,x_0^{2},x_0^{3},x_0^{4})$ とした時， $Var[\hat{f}(x_0)]=\ell_0^{T}\hat{C}\ell_0$ で与えられる．

7.2　Step Functions

　 $X$ をbinsに分割することを考える．これにより，連続値を順序付きのカテゴリカルな変数に変換することができる．まず， $\displaystyle C_0(X)=I(X \lt c_1), \ C_1(X)=I(c_1 \leq X \lt c_2), \ C_2(X)=I(c_2 \leq X \lt c_3), \cdots,\\ C_{K-1}(X)=I(c_{K-1} \leq X \lt c_K), \ C_K(X)=I(c_K \leq X)$ の $K+1$ 個の区間に分割する．ここで $I(\cdot)$ は条件が真の時に1，そうでない時に0を与える指示関数（ダミー変数とも呼ばれる）．ゆえに，任意の値 $X$ について， $C_0(X)+C_1(X)+\ldots+C_K(X)=1$ になる， $C_1(X),C_2(X),\ldots,C_K(X)$ を説明変数とする線形モデル $\displaystyle \begin{align} y_i=\beta_0+\beta_1C_1(x_i)+\beta_2C_2(x_i)+\ldots+\beta_KC_K(x_i)+\epsilon_i \end{align}$ に最小二乗法を適用すると， $C_1(X),C_2(X),\ldots,C_K(X)$ のうち多くても1つの係数がnon-zeroになる．もし $X\lt c_1$ なら全ての係数は0になる．そういうわけで， $\beta_0$ は $X \lt c_1$ の時の $Y$ の平均値として解釈できる．また $\beta_0+\beta_j$ に対するレスポンスを考えると， $\beta_j$ は， $c_j\leq X \lt c_{j+1}$ であるような $X$ についての， $X\lt c_1$ と比較した時の，レスポンスにおける平均的な増加量を表している．

7.3　Basis Functions

　上で扱った多項式回帰やpiecewise-constant regressionは以下のbasis function approachの特殊な場合． $\displaystyle \begin{align} y_i=\beta_0+\beta_1b_1(x_i)+\beta_2b_2(x_i)+\ldots+\beta_Kb_K(x_i)+\epsilon_i \end{align}$ ここで $b(\cdot)$ は何かの関数もしくはtransformation．

7.4　Regression Splines

7.4.1　Piecewise Polynomials

　区間ごとに異なる多項式回帰 $\displaystyle \begin{align} y_i=\beta_0+\beta_1x_i+\beta_2x_i^{2}+\ldots+\beta_Kx_i^{K}+\epsilon_i \end{align}$ を適用する．区間の切れ目となる点はknotと呼ぶ．つまり，点 $c$ をknotとする場合は， $\displaystyle \begin{align} y_i= \begin{cases} \beta_{01}+\beta_{11}x_i+\beta_{21}x_i^{2}+\ldots+\beta_{K1}x_i^{K}+\epsilon_i \ \ \ \ \mbox{if } x_i \lt c\\ \beta_{02}+\beta_{12}x_i+\beta_{22}x_i^{2}+\ldots+\beta_{K2}x_i^{K}+\epsilon_i \ \ \ \ \mbox{if } x_i \geq c \end{cases} \end{align}$ となる．

　もちろん，関数が不連続だったり，変な形になったりする．

7.4.2　Constraints and Splines

7.4.3　The Spline Basis Regression

7.4.4　Choosing the Number and Locations of the Knots

7.4.5　Comparing to Polynomial Regression

7.5　Smoothing Splines

7.5.1　An Overview of Smoothing Splines

7.5.2　Choosing the Smoothing Parameter $\lambda$

7.6　Local Regression

7.7　Generalized Additive Model

7.7.1　GAMs for Regression Problems

　GAMの一例を以下に示す． $\displaystyle \begin{align} y_i=\beta_0+\sum_{j=1}^{p}f_j(x_{ij})+\epsilon_i \end{align}$ additive modelと呼ばれる理由は， $X_j$ それぞれに対して $f_j$ を計算し，和を取っているため．

Pros and Cons of GAMs

　メリットデメリットの検討．

GAMは非線形関係のモデリングが可能．ゆえに各変数について様々な変換を試したりしなくてよい．
一般に非線形でのフィッティングの方が正確に予測できる．
モデルには加法性があるため，他の変数を固定した状態で変数 $X_j$ を動かした時の $Y$ への影響を把握できる．なので推論とかしたい場合，GAMは有効．
変数 $X_j$ に対する関数 $f_j$ の滑らかさは，自由度で決まる．
GAMは加法性に強く縛られているので，相乗効果みたいなのは扱えない．が， $f_{jk}(X_j,X_k)$ のような相乗項を入れてしまえばOK.

7.7.2　GAMs for Classification Problems

　予測が質的データでもGAMを適用可能．

2017-06-15

ISLR: Chapter 6 Linear Model Selection and Regularization

数学機械学習統計学 ISLR

　回帰において標準的な線形モデルは以下のように書かれる． $\displaystyle \begin{align} Y=\beta_0+\sum_{i=1}^p\beta_iX_i+\epsilon \label{standardLinearModel} \end{align}$ この線形モデルに，最小二乗法よりも良い予測の正確さ（Prediction Accuracy）とモデルの解釈性（Model Interpretability）を持つフィッティングの方法を適用したい．

Prediction Accuracy:　説明変数と目的変数の関係がほぼ線形だとする．この時， $n \gg p$ ，つまり，説明変数の数 $p$ に対して観測の数 $n$ が十分に大きいなら最小二乗法で推定されたパラメタはバイアスが低いので，テストデータに対してもうまく機能することが期待できる．しかし， $n$ が十分に大きくなかったらうまく機能しないだろう．また， $p>n$ なら分散が無限大になるので，最小二乗法は有効ではない．そこで，推定されたパラメタを縮小することで，バイアスをほんの少し増加させる代わりに分散を小さくし，性能を上げることができる．
Model Interpretability:　多変量回帰では，全ての説明変数が目的変数に貢献しているわけではない．そういった変数は無駄に解釈を難しくしているので，それらの説明変数に対する係数を0にして，解釈しやすいモデルを獲得したい．

6.1　Subset Selection

　Subset Selectionは， $p$ 個の説明変数のうち，目的変数をよく説明しているいくつかの説明変数を選び出す．

6.1.1　Best Subset Selection

　以下のアルゴリズムの通り．

$M_0$ をnull modelとする． $M_0$ はそれぞれの観測について標本平均を予測する．
$k=1,\ 2,\ldots,\ p$ について，

(a)　 ${}_pC_k$ 個のモデルをフィットさせる．

(b)　 ${}_pC_k$ 個のモデルの中で最も良いモデルを $M_k$ とする．良さは $RSS$ や $R^{2}$ で決める．
$M_0,\ldots,\ M_p$ の中から，AIC, BIC, adjusted $R^{2}$ , cross-validated prediction errorなどを用いて，一番良いモデルを選ぶ．

　Step 2によって， $2^{p}$ 個のモデルのうち1つを選ぶ問題から， $p+1$ 個のモデルのうち1つを選ぶ問題に置き換わっている．

　ただ，何も考えずに $RSS,\ R^{2}$ の値の最小／最大だけで決めてはいけない．というのも，説明変数の数を増やせば $RSS$ は単調減少， $R^{2}$ は単調増加するから．この低い $RSS$ や高い $R^{2}$ はtraining errorが低いことを意味するが，我々が欲しいのはlow test error．ゆえに，Step 3でcross-validated prediction errorやAIC, BIC, adjusted $R^{2}$ を使ってモデルを選択している．

　最小二乗法に対してBest Subset Selectionする方法を示したが，基本的に他の手法に対しても同じように適用可能．ただ，ロジスティック回帰の場合は $RSS$ の代わりに，最大対数尤度に-2をかけた逸脱度（ $deviance$ ）を用いる．この $deviance$ は低いほどうまくフィットしていることを表す．

　Best Subset Selectionの欠点としては， $p$ が大きいときに計算が大変という点が挙げられる．

6.1.2　Stepwise Selection

　Best Subset Selectionが $p$ が大きい時に計算量が多いという問題に加え，探索空間が巨大になるので過学習やパラメタ推定の分散が大きいという問題も起こり得る．以下の方法は探索空間がBest Subset Selectionより小さい．

Forward Stepwise Selection

　以下のアルゴリズムの通り．

$M_0$ をnull modelとする． $M_0$ はそれぞれの観測について標本平均を予測する．
$k=0,\ 1,\ldots,\ p-1$ について，

(a)　 $M_k$ に説明変数を1つ加えた， $p-k$ 個のモデルを考える．

(b)　 $p-k$ 個のモデルの中で最も良いものを選択し，それを $M_{k+1}$ とする．良さの尺度は $RSS,\ R^{2}$ ．
$M_0,\ldots,\ M_p$ の中から，AIC, BIC, adjusted $R^{2}$ , cross-validated prediction errorなどを用いて，一番良いモデルを選ぶ．

　Best Subset Selectionが $2^{p}$ 個のモデルを検討するのに対し，Forward Stepwise Selectionは $\displaystyle 1+\frac{p(P+1)}{2}$ 個のモデルを検討する．ただし，Forward Stepwise Selectionによって得られるモデルは $2^{p}$ 個のモデルの中でのベストとは限らない（最初に得たベストのモデル $M_1$ に変数を1つずつ加えていくので，例えば $M_1$ が $X_1$ を含んでいた場合， $X_2,\ X_3$ から成る2変数のモデルを検討することはできない）．

　Forward Stepwise Selectionは $n \lt p$ の時でも使えるが，この場合は $M_0,\ldots,\ M_{n-1}$ 個のモデルしか作れない（ $p \geq n$ の時は一意の解を得られらないという性質を持つ最小二乗法で各サブモデルをフィッティングしてるため）．

Backward Stepwise Selection

　Forward Stepwise Selectionの逆で，1つずつ変数を落としていく．以下のアルゴリズムの通り．

$M_p$ を全ての説明変数を含んだfull modelとする．
$k=p,\ p-1,\ldots,\ 1$ について，

(a)　 $M_k$ から説明変数を1つ落とした， $k$ 個のモデルを考える．

(b)　 $k$ 個のモデルの中で最も良いものを選択し，それを $M_{kｰ1}$ とする．良さの尺度は $RSS,\ R^{2}$ ．
$M_0,\ldots,\ M_p$ の中から，AIC, BIC, adjusted $R^{2}$ , cross-validated prediction errorなどを用いて，一番良いモデルを選ぶ．

　Forward Stepwise Selectionと同様に，探索する範囲は $\displaystyle 1+\frac{p(p+1)}{2}$ 個のモデルで， $p$ が巨大でも適用可能．ただし，Backward Stepwise Selectionでは $n>p$ であることがマスト（ $n > p$ じゃないとそもそもfull modelを作ることができない）．つまり， $n \lt p$ の時は使えない．

Hybrid Approaches

　Forward Stepwise SelectionとBackward Stepwise Selectionのハイブリッド．Forward~のように変数を1つずつ追加していくが，その度にモデルの性能改善に貢献してない変数を落としていく．Forward~/Backward~の計算量を維持しつつ，得られたモデルはBest Subset Selectionによる結果に近い．

6.1.3　Choosing the Optimal Model

　サブモデルを作ったはいいが，その中からtest errorが最小のモデルをどのように選ぶのか．training errorが必ずしもtest errorをpoor estimateしてるとは限らないので，training errorに関連している $RSS, R^{2}$ 以外の尺度が必要．よく使われるのは，(1) 過学習によるバイアスを考慮した補正をtraining errorにかけることで間接的にtest errorを推定，(2) 5章で説明したvalidation setやcross-validation approachを使って直接的にtest errorを推定，という2つのアプローチ．

$C_p$ , AIC, BIC, and Adjusted $R^{2}$

　一般に，training set $MSE$ はtest set $MSE$ よりも小さくなる．なぜならテストデータではなく訓練データを用いて最小二乗法で $RSS$ を最小化しているから． $\displaystyle \begin{align} MSE=\frac{1}{n}\sum_{i=1}^{n}(y_i-\hat{f}(x_i))^{2}=\frac{RSS}{n} \end{align}$ そういうわけで $RSS,\ R^{2}$ はモデル選択には有効ではない．そこで，モデル選択に有効な4つの指標 $C_p$ ，赤池情報量規準（AIC），ベイズ情報量規準（BIC），adjusted $R^{2}$ を示す．

　最小二乗法でフィットされたモデルが $d$ 個の説明変数を含んでいる時，test error MSEの $C_p$ は以下のように書ける． $\displaystyle \begin{align} C_p=\frac{1}{n}(RSS+2d\hat{\sigma}^2) \end{align}$ ここで， $\hat{\sigma}^{2}$ は式 $\eqref{standardLinearModel}$ の誤差項 $\epsilon$ の分散の推定量である．式の解釈としては，training errorがtest errorを過小評価する傾向にあるのを考慮して $RSS$ にペナルティ $2d\hat{\sigma}^2$ を加えている．説明変数が増えれば増えるほどばらつきも増えるので，説明変数を増やした際に $RSS$ が減少するのを補正している．また，もし $\hat{\sigma}^{2}$ が $\sigma^{2}$ の不偏推定量だった場合， $C_p$ はtest MSEの不偏推定量になる． $C_p$ は小さい値ほどよいモデルであることを表す．

　 $\displaystyle {C’}_p=\frac{RSS}{\hat{\sigma}^{2}}+2d-n$ で与えられるMarrow’s $C_p$ もあるが，これを用いると， $C_p$ は次のようにも書ける． $\displaystyle \begin{align} C_p=\frac{1}{n}\hat{\sigma}^{2}({C’}_p+n) \end{align}$ 結局，Marrow’s $C_p$ の最小化と $C_p$ の最小化は同じ話．

　次に，AIC．AICは最尤推定で定義される． $\epsilon$ がガウスノイズの場合の線形モデル（式 $\eqref{standardLinearModel}$ ）についてのAICは下式で与えられる． $\displaystyle \begin{align} AIC=\frac{1}{n\hat{\sigma}^{2}}(RSS+2d\hat{\sigma}^2) \end{align}$ 本来は定数項も存在するが，記述の簡略化のため除去している．最小二乗法でフィットされた線形モデルの場合は， $C_p$ とAICは比例関係にある．したがって，AICでモデル選択する場合もAICが最小となるモデルを選ぶ．

　BICはベイジアンの視点で導出される． $d$ 個の説明変数を持つ最小二乗モデルの場合のBICは下式． $\displaystyle \begin{align} BIC=\frac{1}{n\hat{\sigma}^{2}}(RSS+\log(n)d\hat{\sigma}^{2}) \end{align}$ BICでモデル選択する場合もBICが最小となるモデルを選ぶ．ペナルティ項が $C_p$ やAICの $2d\hat{\sigma}^{2}$ から $\log(n)d\hat{\sigma}^{2}$ に変わっている点に注意．任意の $n>7$ について $\log n>2$ なので，BICは変数が多いモデルに強いペナルティを課す．ゆえに $C_p$ よりも説明変数の少ないモデルが選ばれやすい．

　最後にadjusted $R^{2}$ ．調整前の $R^{2}$ は $\displaystyle R^{2}=1-\frac{RSS}{TSS},\ \mbox{where } TSS=\sum {(y_i - \hat{y}_i)}^{2}$ で定義される．adjusted $R^{2}$ は以下のように定義される． $\displaystyle \begin{align} \mbox{Adjusted } R^{2}=1-\frac{RSS\ /\ (n-d-1)}{TSS\ /\ (n-1)} \end{align}$ adjusted {tex:R^{2}]の場合は，値が最大のモデルを選択する．adjusted {tex:R^{2}]の最大化は $RSS/(n-d-1)$ の最小化と等価． $RSS$ は単調減少だが，分母に組み込んだ説明変数の個数 $d$ があるので， $RSS/(n-d-1)$ は $d$ に応じて増加または減少する．直感的には，理想のモデル選択を行った場合，そこに更に変数を追加しても $RSS$ はほぼ減らないが， $d$ が増加しているので， $RSS/(n-d-1)$ は増加する．ゆえにadjusted $R^{2}$ は減少する．本書で述べられているように， $C_p$ やAICで選ばれたモデルとは異なるモデルが選択される場合もある．

　もちろん最小二乗モデル以外のモデルにも適用可能．

Validation and Cross-Validation

　validation set approachやcross-validationで直接的にtest errorを推定する方法．test errorを直接推定している点や真のモデルへの仮定が少ない点で上述の規準よりも優れている．モデルの自由度（説明変数の個数）を正確に求めたり， $\epsilon$ の分散 $\sigma^{2}$ を推定するのが困難な場合は，上述の規準よりこちらの方が良い．

　ただし，バリデーションやクロスバリデーションは分割の仕方に依存するので，分割を変える度に選択されるモデルが変わる．これを解決する方法として，one-standard-error-ruleがある．まず，各モデルについてtest errorの推定量の標準誤差を求める．次に，誤差曲線が最小の値を示す点から標準誤差内に収まっているモデルのうち，最小のtest errorを示すモデルを選択する．

6.2　Shrinkage Methods

　係数を0に近づけて分散を小さくすると同時に，説明変数の数を減らし，フィットを改善する．

6.2.1　Ridge Regression

　3章では，実際の観測と線形モデルによる予測値との二乗の差 $RSS$ を最小化してパラメタ $\beta_0,\ \beta_1,\ldots,\ \beta_p$ を求めた． $\displaystyle \begin{align} RSS=\sum_{i=1}^{n} {\biggl(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij} \biggr)}^{2} \end{align}$ リッジ回帰も線形回帰の最小二乗法によるフィッティングと似ている．リッジ回帰におけるパラメタの推定量 $\hat{\beta}^{R}$ は下式を最小化することで求める． $\displaystyle \begin{align} \sum_{i=1}^{n} {\biggl(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij} \biggr)}^{2} + \lambda \sum_{j=1}^{p} \beta_j^{2} = RSS + \lambda \sum_{j=1}^{p} \beta_j^{2} \label{Ridge} \end{align}$ ここで $\lambda \geq 0$ は，フィッティングとは別に決定されるチューニングパラメタ．最小二乗法同様にリッジ回帰も $RSS$ を小さくする方向でのフィットを試みるが，罰則項や正則化項と呼ばれる第2項 $\lambda \sum_{j=1}^{p} \beta_j^{2}$ は $\beta_0,\ \beta_1,\ldots,\ \beta_p$ が0に近いほど小さくなる．つまり，正則化項には $\beta_j$ を0に近づける効果がある． $\lambda$ は回帰式全体における正則化項の影響力の大きさということになり， $\lambda=0$ なら最小二乗法による学習と同じ結果を得る．逆に $\lambda$ を大きくするとパラメタを0に近づける方向でフィットさせる．我々が行いたいのは説明変数に対する係数を0に近づけるなので，上式を見てわかるように，正則化項は切片 $\beta_0$ には適用されない． $\beta_0$ は単なるレスポンスの平均の指標に過ぎない．例えば，各説明変数の平均が0になるように調整されていたら $\displaystyle \hat{\beta}_0=\overline{y}=\sum_{i=1}^{n} \frac{y_i}{n}$ になる．

　最小二乗法による線形回帰ではパラメタは一意に定まったが，リッジ回帰では $\lambda$ の値によってパラメタが変わる．つまり，本質的に重要なのは $\lambda$ の選択．あとでクロスバリデーションで $\lambda$ を選択する方法を示す．

An Application to the Credit Data

　最小二乗法では説明変数を定数倍しても $X_j\hat{\beta}_j$ の値は変わらないが，リッジ回帰では $RSS$ に罰則項が加わっているため，スケールによって $X_j\hat{\beta}_{j,\ \lambda}^{R}$ の値が変わる．このため，回帰する前に全ての説明変数を下式で標準化しておくべき． $\displaystyle \begin{align} \tilde{x}_{ij}=\frac{x_{ij}}{\sqrt{\frac{1}{n}\sum_{i=1}^{n}{(x_{ij}-\overline{x}_j)}^{2}}} \end{align}$ 上式で分母は $j$ 番目の説明変数の標準偏差の推定値を表している．

Why Does Ridge Regression Improve Over Least Squares?

　最小二乗法と比べた時，リッジ回帰の利点はバイアス・バリアンスのトレードオフにある． $\lambda$ を大きくするとリッジ回帰の表現力は減少し，その結果，分散が小さくなり，代わりにバイアスが大きくなる． $\lambda$ を0にすると，分散が大きくなり，代わりにバイアスが0になる．一般に，説明変数と目的変数が線形関係にある時，最小二乗法による線形回帰は分散が小さく，バイアスが大きい．特に， $p$ と $n$ が同じ位の時はものすごくばらつく．また， $p>n$ の時は最小二乗法では一意に定まらないが，リッジ回帰はほんの少しのバイアスを増加させることで分散を小さくできるのでうまくいく．そういうわけでリッジ回帰が最も効くのは最小二乗法の分散が大きい時．

6.2.2　The Lasso

　Ridgeの正則化項が $\ell_2$ ノルムの2乗だったが，Lassoの正則化項は $\ell_1$ ノルム． $\displaystyle \begin{align} \sum_{i=1}^{n} {\biggl(y_i-\beta_0-\sum_{j=1}^p\beta_jx_{ij} \biggr)}^{2} + \lambda \sum_{j=1}^{p} \mid \beta_j \mid = RSS + \lambda \sum_{j=1}^{p} \mid \beta_j \mid \label{Lasso} \end{align}$

　Ridgeは説明変数全体について係数を0に近づけるだけ，つまり， $\lambda$ の値を大きくしようと説明変数の個数は減らない．ゆえにモデルの解釈性に難あり．だが，Lassoなら $\lambda$ を調整することで係数を0に近づけることができる．Fig. 6.6にあるように $\lambda$ の値を大きくするとどんどんと説明変数に対応した係数が0になっていく．Lassoのように，ある説明変数の係数を0にすることで説明変数の個数を減らされたモデルはスパースモデルというらしい．

Another Formulation for Ridge Regression and the Lasso

　Ridge回帰（式 $\eqref{Ridge}$ ）とLasso（式 $\eqref{Lasso}$ ）は，それぞれ以下の形に書き直せる． $\displaystyle \begin{align} \mbox{minimize}_{\beta} \biggl\{ \sum_{i=1}^{n} { \biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\biggr) }^{2} \biggr\} \ \ \mbox{ subject to }\sum_{j=1}^{p} \beta_j^{2} \leq s \label{ridgeAnother} \\ \mbox{minimize}_{\beta} \biggl\{ \sum_{i=1}^{n} { \biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\biggr) }^{2} \biggr\} \ \ \mbox{ subject to }\sum_{j=1}^{p}\mid \beta_j \mid \leq s \label{lassoAnother} \end{align}$ こう書き直すと，正則化項が $s$ 以下という制約の下で最小二乗法していることになる． $s$ が大きければただの最小二乗法になるし，小さければ，Ridgeならあらゆる説明変数に対する係数が0に近づき，Lassoなら説明変数それぞれの係数が0に近づき，変数が減っていく．

　ここで，Best Subset Selectionの定式化は以下のようになる． $\displaystyle \begin{align} \mbox{minimize}_{\beta} \biggl\{ \sum_{i=1}^{n} { \biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\biggr) }^{2} \biggr\} \ \ \mbox{ subject to }\sum_{j=1}^{p} I(\beta_j \neq 0) \leq s \label{BSS} \end{align}$ ここで $I$ は， $\beta_i \neq 0$ の時に1，そうでない時に0を取る指示関数（Indicator Variable）．式 $\eqref{BSS}$ は式 $\eqref{ridgeAnother},\ \eqref{lassoAnother}$ とよく似てる．もちろん， $\ell_1$ ノルムのLassoのほうがBest Subset Selectionに近い．

The Variable Selection Property of the Lasso

　 $\ell_1$ ノルムの描く軌跡は正方形を45度回転させた形， $\ell_2$ ノルムの描く軌跡は円．この正則化項の領域と， $RSS$ の描く等高線との接点が，最小化によって求まるパラメタ．そう考えると， $\ell_2$ ノルムより $\ell_1$ ノルムのほうが接点は軸に近くなるので，変数選択の効果があるねという話．

Comparing the Lasso and Ridge Regression

　LassoはRidgeと比べて変数選択によるモデルの解釈のしやすさという利点がある．が，予測性能はどうだろうか？そんなものは問題設定による．レスポンスにあまり貢献しない説明変数が多ければLassoの方が良いし，そうでないならRidgeの方が良い．

A Simple Special Case for Ridge Regression and the Lasso

　RidgeとLassoのパラメタの動きの違いを理解するために $n=p$ ，入力を単位行列とした場合，パラメタはそれぞれ以下の通り． $\displaystyle \begin{align} \hat{\beta}_j^{R}=\frac{y_j}{1+\lambda} \end{align}$ $\displaystyle \begin{align} \hat{\beta}_j^{L}= \begin{cases} y_j-\frac{\lambda}{2}\ \ \ \ \ \ \mbox{if } y_j > \lambda\ /\ 2 \\ y_j+\frac{\lambda}{2}\ \ \ \ \ \ \mbox{if } y_j \lt \lambda\ /\ 2 \\ 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{if } \mid y_j \mid \leq \lambda\ /\ 2 \end{cases} \end{align}$ Ridgeは同じ比率で係数を潰していくのに対し，Lassoは $\mid y_j \mid$ が $\lambda\ /\ 2$ 以下の場合0にする．グラフにすると一目瞭然なのでFig. 6.10を見てもらいたい．簡単のために単位行列を用いたが，一般の入力データについても，係数の潰れ方は同じような感覚でいいみたい．

Bayesian Interpretation for Ridge Regression and the Lasso

　ベイジアン的な視点からRidgeとLassoを見る．パラメタ $\beta$ は， $g$ を何かしらの密度関数として，事前分布 $\displaystyle p(\beta)=\prod_{j=1}^{p}g(\beta_j)$ を持っていることを仮定する．そうすると，観測が与えられた時のパラメタの事後分布は，尤度を $f(Y \mid X, \beta)$ とすると， $\displaystyle \begin{align} p(\beta \mid X,Y) \propto f(Y \mid X, \beta)p(\beta \mid X)=f(Y \mid X, \beta)p(\beta) \end{align}$ と書ける．前半はベイズの定理による変形．後半の等式は，観測が与えられている前提なので， $X$ は固定されているため変形できている．

　そうすると，Ridgeによって得られる解は， $g$ が平均0，標準偏差が $\lambda$ の関数の正規分布だった場合， $\beta$ は事後確率の平均値（事後モード？と言うらしい？）になる．

　また，Lassoによって得られる解は， $g$ が平均0でパラメタ $\lambda$ を持つラプラス分布の場合， $\beta$ も事後確率の平均に相当するらしい．が，実際には，Lasso解は事後確率の平均ではない．というのも事後確率の平均はスパースベクトルじゃないので．

　Fig. 6.11を見ると，Lassoは0の周りで尖ってるので，多くの説明変数は0だと仮定していることになる．逆にRidgeは係数が0の周りでランダムに散らばってると仮定している．

6.2.3　Selecting the Tuning Parameter

　クロスバリデーションしてcross-validation errorが最小となる $\lambda$ を選ぶだけ．

6.3　Dimension Reduction Methods

　Ridge, Lassoは $p$ 個の説明変数で予測してたけど，説明変数を $M\ (M \lt p)$ 個に減らしてから予測したい．とりあえず，以下のような $Z_1,\ Z_2,\ldots,\ Z_M$ を考える． $\displaystyle \begin{align} Z_m=\sum_{j=1}^{p}\phi_{jm}X_j \label{reduction} \end{align}$ ここで $\phi_{1m},\ \phi_{2m},\ldots,\ \phi_{pm},\ m=1,\ldots,\ M$ は何かの定数とする．これらを使って最小二乗法でフィッティングしたい． $\displaystyle \begin{align} y_i=\theta_0+\sum_{m=1}^{M}\theta_mz_{im}+\epsilon_i,\ \ \ i=1,\ldots,n \end{align}$ ちなみに，変数の個数減らしてもやってる事自体は， $\beta_j=\sum_{m=1}^{M}\theta_m\phi_{jm}$ とすると，同じであることが以下の式変形でわかる． $\displaystyle \begin{align} \sum_{m=1}^{M}\theta_mz_{im}=\sum_{m=1}^{M}\theta_m\sum_{j=1}^{p}\phi_{jm}X_{ij}=\sum_{j=1}^{p}\sum_{m=1}^{M}\theta_m\phi_{jm}x_{ij}=\sum_{j=1}^{p}\beta_jx_{ij} \end{align}$ $p$ 個の説明変数で最小二乗法するより， $M$ 個の説明変数で最小二乗法したほうがいい結果が出るかもしれない．なぜかというと，例えば $p \gg n$ の時，説明変数を $M(M \lt p)$ 個にすることで推定されたパラメタの分散が小さくなることが期待できる．

　というわけで， $\phi_{1m},\ \phi_{2m},\ldots,\ \phi_{pm}$ をどうやって決めるかという話になる．

6.3.1　Principal Components Regression

An Overview of Principal Components Analysis

　説明変数を主成分分析（Principal Component Analysis, PCA）で次元縮小してから回帰．PCA自体はChapter 10で詳しく話す．　PCAは，まず，データのばらつきが最大になるように（第一主成分に射影した時の分散が最大になるように）第一主成分を決める．別の見方をすると，第一主成分は元のデータをできるだけ再現するように決まる．元のデータを第一主成分に射影した時の距離を最小にする．そういう意味で，なるべく元のデータを保存できるように第一主成分が決定される．第一成分が決まったら，第二成分は第一成分と相関がないという条件の下で分散が最大になるように決定される．第三成分以降も，既存の軸と相関を持たないようにしつつ，分散最大になるように決定される．

The Principal Components Regression Approach

　PCRは単に $p$ 個より少ない $M$ 個の変数で回帰してるだけなので，変数選択ではない．本書の例ではAdとpopulationが混ざったような形になってる．

　PCAは分散が最大になるように軸を決めるので，適用する前にスケールの標準化を行わなければならない．そうしないと分散が以上に大きい説明変数の影響を強く受けてしまう．

6.3.2　Partial Least Squares

　PCAで分散最大の軸を探す仮定でレスポンス $Y$ は使ってない．つまり，これって一種の教師なし学習だよね．だからこそ，PCAには「分散最大の軸を見つけ，それに従って軸を回転させるけど，それが予測する上で最適な軸とは限らない」という問題がある．

　そこでPLSを考える．PLSは，大雑把にまとめると，データの表現をできるだけ保つ軸を探しつつ $Y$ との関連性も見る教師あり学習．実際には，まず標準化する．その後，式 $\eqref{reduction}$ の $\phi_{jm}$ を $X$ と $Y$ の相関係数に比例するようにする．そうすると， $Y$ に最も関連する $X$ に一番重い重みが与えられることになる．これで $Z_1$ が求まる．次に，それぞれの変数で $Z_1$ を回帰して残差を取り，各変数を $Z_1$ について補正する．この残差は $Z_1$ で表現しきれなかった情報として解釈できる．その上で先程と同様に $Z_2$ の最小化を行い，また同様に補正をかけて…という具合に繰り返していく．

　パラメタ選択はクロスバリデーション．

　ただし，実用上はPCAやRidgeより性能がでないらしい．理由は，PLSはバイアスは減るが，代わりに分散が大きくなりやすいから．

6.4　Considerations in High Dimensions

6.4.1　High-Dimensional Data

　 $p>n$ もしくは $p$ と $n$ がほぼ同じ時，教師あり学習する時に気をつけること．

6.4.2　What Goes Wrong in High Dimensions

　最小二乗法は $n\gg p$ じゃないとダメ．理由は，説明変数とレスポンスの数がほぼ同じだったりすると，残差0でフィット，つまり過学習してしまうから．別の言い方をすると， $p>n$ もしくは $p$ と $n$ がほぼ同じ時，最小二乗法は表現力が高すぎる．　また，教師あり学習では $R^{2}$ とTraining MSEだけで判断してはいけない． $R^{2}$ は変数の数を増やせば増える（つまり， $n$ と $p$ を近くする）し，そうすろと過学習になるのでTraining MSEはどんどん減っていく．そうならないために変数選択として $C_p$ , AIC, BICを扱ったが，高次元（ $n\gg p$ ではない）の時は $\hat{\sigma}^{2}=0$ のため，それらは有効ではない．同様の理由でAdjusted $R{2}$ も簡単に1になるのでダメ．何か別の方法がいる．

6.4.3　Regression in High Dimensions

　forward stepwise selection, Ridge, Lasso, PCAは，最小二乗法よりも表現力の低い手法なので，結果的に過学習を回避することができ，高次元の問題設定では有効．　大事なポイントは，(1) regularization/shrinkageが高次元の問題設定では重要，(2) パラメタチューニング大事，(3) 出力と関係ない変数を突っ込むと精度はどんどん悪化していく（次元の呪い），の3点．

6.4.4　Interpreting Results in High Dimensions

　高次元の問題に対してLassoやRidgeを使うのはいいけど，それで全てが解決するわけではない．高次元だと共線性が発生しやすいという問題がある．　また，変数選択とかでいくつか変数を減らしたモデルを得ることができたとしても，それは単に考え得る無数のモデルから1つを獲得しただけということは念頭に置いておく必要がある．　さらに，高次元（ $p>n$ ）の時はSSE (Sum of Squared Errors), $p$ 値， $R^{2}$ などの統計量を用いてモデルを評価してはいけない．例えば $R^{2}=1$ になったりしやすいので．そういう場合は独立にテストデータを用意するかクロスバリデーションを行う．もちろんその中でのテストデータに対して統計量を用いるのは良いが，訓練データについて算出した統計量は有効ではない．

2017-06-11

ISLR: Chapter 5 Resampling Methods

数学機械学習統計学 ISLR

　Resampling methodsは訓練データから何度もサンプルを取り出し，モデルにフィットさせる．これにより，一度だけのフィッティングでは得られない情報を得られる．

　本章ではクロスバリデーションとブートストラップ法を扱う．クロスバリデーションはテストエラーの推定やモデルの適切な表現力を決める際に用いる．モデルの性能を評価するプロセスはモデル評価（model assessment）というのに対し，モデルの適切な柔軟性を決めるプロセスはモデル選択（model selection）という．ブートストラップ法は，一般に，与えられたモデルのパラメタ推定の正確さを測る際に用いる．

5.1　Cross-Validation

　モデルを作ったら，test error rateを見てどの程度うまくいってるか確認したい．が，テストデータが少なければそんなことはできない．そういう時は訓練データの一部をバリデーションデータとし，それをテストデータとみなして扱う．

5.1.1　The Validation Set Approach

　量的データを想定．量的データに対しては，二乗誤差の平均（Mean Squared Error, $MSE$ ）を使うことが多い． $\displaystyle \begin{align} MSE=\frac{1}{n}\sum_{i=1}^{n}(y_i-\hat{f}(x_i))^{2}=\frac{RSS}{n} \end{align}$

　テストデータを十分に確保できない時に訓練データとバリデーションデータに分けてしまうこの方法の欠点は，

分割の仕方によってtest error rateがかなりばらつく
テストデータに充てた分，訓練データが少なくなり，性能が悪化する．結果，validation set error rateは真のtest error rateを過大評価してしまう．

5.1.2　Leave-One-Out Cross-Validation (LOOCV)

　LOOCVもthe validation set approachと同様に訓練データとバリデーションデータに分ける．が，LOOCVではバリデーションデータは観測 $(x_i,\ y_i)$ 1つのみ．それ以外の観測は全て訓練データ．訓練データを用いてフィットさせたモデルに $x_i$ を入力し $MSE$ （この場合は $(y_i-\hat{y}_i)^{2}$ ）を求める．これはtest errorの不偏推定量の近似になってる．で，これを全てのデータについて繰り返す．そうすると，LOOCVによるtest $MSE$ の推定量は $n$ 個の $MSE$ の平均になる． $\displaystyle \begin{align} CV_{(n)}=\frac{1}{n}\sum_{i=1}^{n}MSE_i \end{align}$

　LOOCVには，(1) バイアスが小さく，test error rateを過大評価しにくい，(2) 全てのデータについて $MSE_i$ を求めているため，分割のランダムネスに左右されるthe validation set approachのように分散が大きいという問題がない，という2つの利点がある．

　欠点としては，観測の数だけモデルをフィットさせる必要があるので，観測が多い時もしくはフィッティングに時間がかかる時は計算コストが高いことが挙げられる．が，最小二乗法による線形回帰もしくは多項式回帰なら以下の式で $MSE$ を推定すると，1回のフィッティングで済むらしい． $\displaystyle \begin{align} CV_{(n)}=\frac{1}{n}\sum_{i=1}^{n} {\biggl( \frac{y_i-\hat{y}_i}{1-h_i} \biggr)}^{2},\ \mbox{where }h_i=\frac{1}{n}+\frac{(x_i-\overline{x})^2}{\sum_{i’=1}^n(x_{i’}-\overline{x})^2} \label{magicFormula} \end{align}$ $h_i$ はleverage statistic．leverage statistic $h_i$ は $\displaystyle \frac{1}{n},\ 1]$ の値を取り，フィッティングにおける $i$ 番目の観測の影響力を表している． $i$ 番目の残差を $1-h_i$ で割ることで，high-leverageな $x_i$ の残差を重視している．式 $\eqref{magicFormula}$ は一般には成り立たない．

5.1.3　k-Fold Cross-Validation

　LOOCVは観測の数だけフィット・予測を行うが，k-Fold Cross-Validationでは観測を $k$ 個のグループに分割し，あるグループをバリデーションデータ，それ以外は訓練データとしてフィッティング・予測を行う．これを $k$ 回繰り返す． $\displaystyle \begin{align} CV_{(k)}=\frac{1}{k}\sum_{i=1}^{k}MSE_i \end{align}$

　LOOCVと比べた時のメリットは計算量（LOOCV: $n$ , k-Fold Cross-Validation: $k\ (k\leq n)$ ．

5.1.4　Bias-Variance Trade-Off for k-Fold Cross-Validation

　k-fold Cross-ValidationがLOOCVより優れている点として，計算量に加え，一般にtest error rateをLOOCVよりも正確に推定できる点が挙げられる．

　LOOCVは $n-1$ 個の観測を訓練データとして用いているのに対し，k-fold CVの訓練データに含まれる観測の数は $(k-1)n/k$ 個．つまり，k-fold CVの訓練データのサイズはLOOCVより小さく，the validation set approachより多い．したがってバイアス削減の観点から見たら，k-fold CVよりLOOCVの方が優れている．

　だが，得られたtest errorのバリアンスについてはLOOCVよりk-fold CVの方が小さい．というのは，LOOCVは $n-1$ 個の観測でモデルをフィッティングしているため， $n$ 個のフィットされたモデルはほぼ変わらない．つまり， $n$ 個のモデルには相関関係がある．一方，k-fold CVは観測を $k$ 個に分割しているので，観測の重複が少なく，結果として，k-fold CVで構築したモデル群の相関は，LOOCVで構築されたモデル群よりも弱い．相関が強いと分散が大きくなるので，test errorの分散の観点から見たら，LOOCVよりk-fold CVの方が優れている．

5.1.5　Cross-Validation on Classification Problems

　今度は質的データを分類したい時のCross-Validationの話．量的データの場合は $MSE$ を用いたが，質的データを扱う場合にはエラー率 $Err_i$ を用いる．エラー率を用いてLOOCVは以下のように書くことができ，k-fold CVもアナロジーで書ける． $\displaystyle \begin{align} CV_{(n)}=\frac{1}{n}\sum_{i=1}^{n}Err_i,\ \mbox{where } Err_i=I\ (y_i \neq \hat{y}_i) \end{align}$

5.2　The Bootstrap

　ブートストラップ法は，線形回帰の係数の標準誤差など，推定量や学習手法の不確かさを評価することができる．色々な手法に対して適用可能という守備範囲の広さも魅力．

　パラメタを推定したい時はサンプルを何度も生成して平均を取れば良いが，そもそもサンプル生成のためのパラメタが未知なのでそんなことはできない．ブートストラップ法なら母集団のパラメタが未知でも，手持ちのデータセットから繰り返しサンプルして異なるデータセットを作ることで，パラメタを推定する．

　具体的な方法は以下の通り．まず， $n$ 個の観測を含む手持ちのデータセット $Z$ から $k\ (n \lt k)$ 個の観測を抽出し，取り出された $k$ 個の観測をブートストラップデータセット $Z^{*1}$ とする．次に $Z^{*1}$ を用いてパラメタを推定し，推定されたパラメタを $\hat{\alpha}^{*1}$ とする．これらの手順を $B$ 回繰り返し， $Z^{*1},\ Z^{*2},\ldots,\ Z^{*B}$ と $\hat{\alpha}^{*1},\ \hat{\alpha}^{*2},\ldots,\ \hat{\alpha}^{*B}$ を得る．そして，これらのパラメタの標準誤差を下式で求める． $\displaystyle \begin{align} SE_B(\hat{\alpha})=\sqrt{\frac{1}{B-1}\sum_{r=1}^{B} {\biggl( \hat{\alpha}^{*r}-\frac{1}{B}\sum_{r’=1}^{B}\hat{\alpha}^{*r’} \biggr)}^{2}} \end{align}$ これは元のデータセットで $\hat{\alpha}$ を推定した時の標準誤差の推定量になっている．

2017-06-10

ISLR: Chapter 4 Classification

数学機械学習統計学 ISLR

　回帰ではレスポンスが量的データの場合を扱ったが，レスポンスを質的データとしたい場合もある．そういう時は回帰ではなく分類を用いる．

4.1　An Overview of Classification

　問題設定：顧客がデフォルトするかしないかを判定

4.2　Why Not Linear Regression?

　ダミー変数を置いて回帰するアプローチは，その質的データの取りうる値が2値の場合は有効．ダミー変数が2値の場合に最小二乗法で学習された線形回帰モデルは $\mbox{Pr}(Y=1 \mid X)$ の推定値になってる．ただ，回帰なので実際に予測した時に値が $[0,\ 1]$ の範囲に収まらないため，確率として解釈するにはちょっと無理がある．

　しかし，ダミー変数の数が2つ以上になると，ダミー変数の置き方によってダミー変数の間の差に意味が生じるので基本的にダメ．例えば，ラベルが脳卒中，薬物中毒，癲癇だとして，それぞれのダミー変数を1, 2, 3とする．そうすると，3-2=2-1=1となるので，癲癇と薬物中毒の差は薬物中毒と脳卒中の差と同じであるということを意味してしまう．もちろん差の意味が同じことを表してるなら1, 2, 3とダミー変数を置くのも良いが，そうでない場合が多いので，レスポンスが質的データの場合は分類手法を使う方が良い．

4.3　Logistic Regression

　確率を， $\displaystyle \begin{align} p(X)=\mbox{Pr}(Y=1 \mid X) \end{align}$ とする．

4.3.1　The Logistic Model

　線形回帰モデル $p(X)=\beta_0+\beta_1X$ でモデル化すると $[0,\ 1]$ の範囲を超える値を取ってしまう．そこで，ロジスティック回帰では $p(X)$ をロジスティック関数を使ってモデル化する． $\displaystyle \begin{align} p(X)=\frac{e^{\beta_0+\beta_1X}}{1+e^{\beta_0+\beta_1X}} \label{logisticRegression} \end{align}$ 関数の形はFig. 4.2にあるようにS字型．パラメタは最尤推定で求める．式 $\eqref{logisticRegression}$ は次のように変形できる． $\displaystyle \begin{align} \frac{p(X)}{1-p(X)}=e^{\beta_0+\beta_1X} \label{odds} \end{align}$ この式の左辺はoddsと呼ばれ， $[0,\ \infty]$ の範囲で値をとる．oddsは0に近いほど低い確率， $\infty$ に近いほど大きい確率であることを表す．

　式 $\eqref{odds}$ の対数を取ると， $\displaystyle \begin{align} \log\biggl( \frac{p(X)}{1-p(X)}\biggr) = \beta_0+\beta_1X \label{logit} \end{align}$ この式の左辺をlog-oddsまたはlogitと呼び，式 $\eqref{logisticRegression}$ は $X$ について線形の関係にあるlogitを持っていることがわかる．

　説明変数 $X$ の係数 $\beta_1$ は，線形回帰では $X$ を1単位分動かした時に目的変数 $Y$ に及ぼす変化の平均値を意味しているが，ロジスティック回帰では $X$ を1単位分動かした時にlogitが $\beta_1$ ずつ変化する（つまり，oddsに $e^{\beta_1}$ をかけることと等価）．

　 $p(X)$ と $X$ の関係は直線で表現できない． $p(X)$ の変化量は $X$ の値によって変化するから，S字カーブを描く．

4.3.2　Estimating the Regression Coefficients

　最小二乗法で学習してもいいけど，最尤推定というもっといい方法がある．最尤推定の性質として，式 $\eqref{logisticRegression}$ のパラメタ $\beta_0,\ \beta_1$ を観測に最も近くなるように学習する．最尤推定は以下の形で定式化できる． $\displaystyle \begin{align} \ell(\beta_0,\ \beta_1)=\prod_{i: y_i=1} p(x_i) \prod_{i’:y_{i’}=0} (1-p(x_{i’})) \end{align}$ 線形回帰での最小二乗法は実は最尤推定の特殊なケースになってる．

4.3.3　Making Predictions

　パラメタ $\beta_0,\ \beta_1$ が求まれば予測は簡単にできるという話．ロジスティック回帰でも質的説明変数に対してダミー変数のアプローチを使える．

4.3.4　Multiple Logistic Regression

　式 $\eqref{logisticRegression},\ \eqref{logit}$ を多変量に拡張すると以下のように書ける． $\displaystyle \begin{align} p(X)=\frac{e^{\beta_0+\beta_1X_1+\cdots+\beta_pX_p}}{1+e^{\beta_0+\beta_1X_1+\cdots+\beta_pX_p}},\ \mbox{where } X=(X_1,\ldots,\ X_p)\mbox{ are }p\mbox{ predictors.} \label{multiLR} \end{align}$ $\displaystyle \begin{align} \log\biggl(\frac{p(X)}{1-p(X)}\biggr)=\beta_0+\beta_1X_1+\ldots+\beta_pX_p \end{align}$

　多変量（income, balance, student）でロジスティック回帰した時には，incomeとbalanceを固定した時，学生よりも非学生のほうが高いデフォルト確率を示すが，studentのみでロジスティック回帰した時は非学生よりも学生の方が高いデフォルト確率を示す．これはbalanceとstudentに相関があるから．balanceとstudentを繋ぐ要素は，本書では「学生はより大きな負債を抱えている（奨学金かな？）」とされている．3章でも話したけど，説明変数間に相関があると，単変量と多変量で結果が変わる．この現象は一般に交絡（confounding）と呼ばれる．

4.3.5　Logistic Regression for >2 Response Classes

　ロジスティック回帰で多クラス分類もできるけど，実際には次章で紹介する線形判別分析（Linear Discriminant Analysis, LDA）を用いるので本書では割愛．Rでは簡単に使えるらしい．

4.4　Linear Discriminant Analysis

　ロジスティック回帰（式 $\eqref{logisticRegression},\ \eqref{multiLR}$ ）では直接 $\mbox{Pr}(Y=k \mid X=x)$ をモデリングした．つまり，説明変数 $X$ を与えた時のレスポンス $Y$ の条件付き分布をモデル化している．

　ただ，多クラス分類においてロジスティック回帰は，レスポンスを綺麗に分けることができる場合はパラメタ推定が安定しない．また，観測が少なく，かつ各クラス毎の説明変数 $X$ の分布が正規分布の場合は，もっと良い手法がある．それがLDA．分離平面が綺麗に分かれる場合のパラメタ不安定問題も，この手法なら気にすることはない．

　LDAでは $\mbox{Pr}(Y=k \mid X=x)$ を直接モデル化しない．代わりに，各クラスごとの説明変数 $X$ の分布をモデル化し，ベイズの定理を使って $\mbox{Pr}(Y=k \mid X=x)$ を求める．

4.4.1　Using Bayes' Theorem for Classification

　 $\pi_k$ をある観測が $k$ 番目のクラスに所属している事前確率とする．また， $k$ 番目のクラスに属する観測 $X$ を得た時の密度関数を $f_k(X)\equiv \mbox{Pr}(X=x \mid Y=k)$ とする． $f_k(X)$ は確率なので，大きな値を取れば $k$ 番目のクラスに属する観測 $X$ は $X \approx x$ だろうし，小さな値をとった時には $X \approx x$ である確率は低い．で，ベイズの定理を使うと，求めたい確率 $\mbox{Pr}(Y=k \mid X=x)$ は以下のように書ける． $\displaystyle \begin{align} \mbox{Pr}(Y=k \mid X=x)=\frac{\pi_k f_k(x)}{\sum_{l=1}^{K} \pi_l f_l(x)} \label{lda} \end{align}$ $\mbox{Pr}(Y=k \mid X)$ は以下 $p_k(X)$ と書く．母集団からのランダムなサンプルがある場合は $\pi_k$ は非常に簡単に求まるが， $f_k(x)$ は密度関数を簡単な形だと仮定しない限りはかなり難しい．

4.4.2　Linear Discriminant Analysis for p=1

　まず，説明変数1つの場合を考える．密度関数 $f_k(x)$ を正規分布だと仮定する． $\displaystyle \begin{align} f_k(x)=\frac{1}{\sqrt{2\pi}\sigma_k}\exp\biggl(-\frac{1}{2\sigma_k^{2}}(x-\mu_k)^2\biggr) \label{densityFunc} \end{align}$ クラス毎の分散は全て $\sigma^2$ ，つまり， $\sigma_1^{2}=\ldots =\sigma_k^{2}=\sigma^{2}$ と仮定し，式 $\eqref{densityFunc}$ を式 $\eqref{lda}$ に代入すると， $\displaystyle \begin{align} p_k(x)=\frac{\pi_k \frac{1}{\sqrt{2\pi}\sigma_k}\exp\biggl(-\frac{1}{2\sigma_k^{2}}(x-\mu_k)^2\biggr)}{\sum_{l=1}^{K} \pi_l \frac{1}{\sqrt{2\pi}\sigma_l}\exp\biggl(-\frac{1}{2\sigma^{2}}(x-\mu_l)^2\biggr)} \label{lda2} \end{align}$ となる．ここで， $\mu_k$ は $k$ 番目のクラスの平均を表す．ベイズ分類器は式 $\eqref{lda2}$ の確率が最大となるクラスを，観測が所属するであろうクラスとする．式 $\eqref{lda2}$ のlogを取って整理すると， $\displaystyle \begin{align} \delta_k(x)=x \cdot \frac{\mu_k}{\sigma^{2}}-\frac{\mu_k^{2}}{2\sigma^{2}}+\log(\pi_k) \label{logLDA} \end{align}$ となる．

　実際に予測するためには， $\mu_1,\ldots,\ \mu_k,\ \pi_1,\ldots,\ \pi_k,\ \sigma^{2}$ を推定する必要がある．LDAは，式 $\eqref{logLDA}$ を用いて $\pi_k,\ \mu_k,\ \sigma^{2}$ を推定するとベイズ分類器の近似になる．肝心の推定量は下式で与えられる． $\displaystyle \begin{align} \hat{\mu}_k=\frac{1}{n_k}\sum_{i:y_i=k}x_i \label{estMU} \end{align}$ $\displaystyle \begin{align} \hat{\sigma}^2=\frac{1}{n-K}\sum_{k=1}^{K}\sum_{i:y_i=k}(x_i-\hat{\mu}_k)^{2} \label{estSIGMA} \end{align}$ ここで， $n$ はトレーニング用の観測の総数， $n_k$ は $k$ 番目のクラスのトレーニング用観測の総数を表す． $\hat{\mu}$ はクラス $k$ の観測の平均， $\sigma^{2}$ はそれぞれのクラスの標本分散の重み付き平均になっている．もし事前確率 $\pi_k$ についての情報がなければ，LDAでは $\displaystyle \begin{align} \hat{\pi}_k=\frac{n_k}{n} \label{estPI} \end{align}$ とする．式 $\eqref{estMU},\ \eqref{estSIGMA},\ \eqref{estPI}$ を式 $\eqref{logLDA}$ に代入すると，観測 $X=x$ の所属クラスは $\displaystyle \begin{align} \hat{\delta}_k(x)=x \cdot \frac{\hat{\mu}_k}{\hat{\sigma}^{2}}-\frac{\hat{\mu}_k^{2}}{2\hat{\sigma}^{2}}+\log(\hat{\pi}_k) \label{logLDA2} \end{align}$ が最大となるクラス．LDAという名前がついているのは判別関数 $\hat{\delta}_k$ が $x$ の線形関数になっているから．

　LDAは各クラスの観測がクラス固有の平均 $\mu$ と，クラス共通の分散 $\sigma^{2}$ の正規分布から生成されていると仮定している．Section 4.4.4ではクラス固有の分散 $\sigma_k^{2}$ を持てるように仮定を緩める．

4.4.3　Linear Discriminant Analysis for p>1

　LDAを多変量に拡張する． $p=1$ の時は観測 $X$ は正規分布に従うとしていたが，多変量の場合，観測 $X=(X_1,\ X_2,\ldots,\ X_p)$ は多変量正規分布に従う．それぞれの成分は単変量の正規分布に従い，成分間には多少の相関あり． $p$ 次元のランダムな変数 $X$ が平均 $\mu$ ，共分散 $\Sigma$ の多変量正規分布に従うことを $X \sim N(\mu,\ \Sigma)$ で表す．下式は多変量正規分布の確率密度関数． $\displaystyle \begin{align} f(x)= \frac{1}{ \sqrt{(2\pi)^{p}} \sqrt{\left|\Sigma\right|}} \exp \biggl( -\frac{1}{2}(x-\mu)^{T}\Sigma^{-1}(x-\mu) \biggr) \label{densityFunc2} \end{align}$

　 $k$ 番目のクラスに属する観測はクラス固有の平均 $\mu_k$ とクラス共通の共分散 $\Sigma$ を持つ多変量正規分布 $N(\mu_k, \Sigma)$ に従う．観測があるクラスに所属する確率は，式 $\eqref{densityFunc2}$ を式 $\eqref{lda}$ に代入し，logを取って整理すると，下式で与えられる． $\displaystyle \begin{align} \delta_k(x)=x^{T}\Sigma^{-1}\mu_k-\frac{1}{2}\mu_k^{T}\Sigma^{-1}\mu_k+\log \pi_k \end{align}$ 観測が所属するクラスは上式が最大となるクラス．

　単変量でのLDAと同様に $\mu_1,\ldots,\ \mu_k,\ \pi_1,\ldots,\ \pi_k,\ \Sigma$ を求める必要がある．推定量は式 $\eqref{estMU},\ \eqref{estSIGMA},\ \eqref{estPI}$ と似たような感じで与えられるみたい．

　LDAはベイズ分類器の近似になってる．モデルが正しければベイズ分類器はtotal error rateを最小，つまり誤分類した観測の総数が最も少なくなるようにする．total error rateはどちらのエラーも含んでるので，その辺は，例えば $\mbox{Pr(default}=\mbox{Yes}\mid X=x)>0.5$ というように，閾値で調整する．

4.4.4　Quadratic Discriminant Analysis

　LDAではクラス共通の共分散 $\Sigma$ を用いたが，共分散が共通ではない場合には2次判別分析（Quadratic Discriminant Analysis, QDA）を用いる．

　クラス固有の共分散を $\Sigma_k$ とすると，観測 $x$ がクラス $k$ に所属する確率は次のようになる． $\displaystyle \begin{align} \delta_k(x) =-\frac{1}{2}(x-\mu_k)^{T}\Sigma_k^{-1}(x-\mu_k)-\frac{1}{2}\log \left|\Sigma_k \right| + \log \pi_k \end{align}$ こいつを整理して， $\displaystyle \begin{align} \delta_k(x)=-\frac{1}{2}x^{T}\Sigma_k^{-1}x+x^{T}\Sigma_k^{-1}\mu_k-\frac{1}{2}\mu_k^{T}\Sigma_k^{-1}\mu_k-\frac{1}{2}\log \left|\Sigma_k \right|+\log \pi_k. \end{align}$ クラスに属する確率を求める上式が $x$ の2次関数の形になってるので，QDAと呼ぶ．

　LDAとQDAのどちらを使うべきなのか？答えはバイアス・バリアンスのトレードオフの関係にある．LDAでは共分散行列を求めるために $\displaystyle \frac{p(p+1)}{2}$ 個のパラメタを推定する必要があり，QDAではクラスによって共分散が異なるため，クラス数をかけた $\displaystyle \frac{Kp(p+1)}{2}$ 個のパラメタの推定が必要になる．LDAは $x$ について線形なので，QDAより表現力が低い代わりに分散が小さい．つまり，より良い分類精度を示す可能性がある．だが，バイアスとバリアンスはトレードオフの関係にあるので，LDAのバイアスは高い．使い分けとしては，テストデータが小さく，予測器の分散が重要でないならLDA．テストデータが十分に大きい，もしくは，共分散がクラス間で共通しているという仮定が妥当でなければQDAの方が良い．

4.5　A Comparison of Classification Methods

　ロジスティック回帰，LDA，QDA，kNNを比較する．

　まず，ロジスティック回帰とLDAを比較する．結論から言うと，ロジスティック回帰とLDAはかなり似てる．単変量でクラス1への所属確率を $p_1(x)$ ，クラス2への所属確率を $p_2(x)=1-p_1(x)$ とする．ロジスティック回帰のlogitは式 $\eqref{logit}$ ．LDAの枠組みで $\displaystyle \log \biggl( \frac{p_1(x)}{1-p_1(x)} \biggr)$ を求めると， $c_0,\ c_1$ を $\mu_1,\ \mu_2,\ \sigma^2$ の関数とすると，式 $\eqref{lda2},\ \eqref{logLDA}$ より， $\displaystyle \begin{align} \log \biggl( \frac{p_1(x)}{1-p_1(x)} \biggr)=\log \biggl( \frac{p_1(x)}{p_2(x)} \biggr) = c_0+c_1x \end{align}$ と書ける．ロジスティック回帰もLDAも $x$ の線形関数になってるので，どちらも直線の決定境界を与える．両者の違いはパラメタの求め方．ロジスティック回帰では最尤推定，LDAでは正規分布のパラメタ $\mu,\ \sigma^2$ を用いて $c_0,\ c_1$ を求めてる．フィッティングにおけるこの関係性は多変量になっても同じ．だがしかし，フィッティングの方法が似てるからといって必ずしも同じような結果を得るとは限らない．LDAは観測が正規分布に従うと仮定してるので，実際に正規分布に従う場合はロジスティック回帰よりもLDAの方が優れた精度を示すし，正規分布の仮定が間違っているならLDAよりロジスティック回帰の方が優れた精度を示す．

　kNN分類器は決定境界の形を仮定しないノンパラメトリックな手法．kNNは非線形な決定境界を与えるので，真の決定境界が非線形の時はロジスティック回帰やLDAより有効．ただ，各説明変数毎のパラメタを持たないので，どの説明変数が効いてるのかはわからない．

　QDAは非線形なkNNと線形なロジスティック回帰・LDAとの折衷案．決定境界は2次関数の形になってるので線形な決定境界を与える手法よりはより幅広い問題を扱えるが，ノンパラメトリックなkNNほどではない．訓練用の観測が少ない時には決定境界の形をある程度仮定できるので，kNNよりQDAの方が良い精度を示す．

　LDAやロジスティック回帰に2次の項 $X_1^{2},\ X_2^{2},\ X_1X_2$ を導入すれば2次関数の形の決定境界を得られるが，その場合はLDA ・ロジスティック回帰とQDAの中間になるらしい．

アイデアを出すために必要なインプットの方法

1. カラーバス

2. ちょいメモ

3. 七色いんこ

溜めたインプットを効率的に引き出してアイデアを量産する方法

1. アイデアスケッチ

2. マンダラート

3. 連想ゲーム

4. オズボーンのチェックリスト

出したアイデアを企画に収束させる方法

1. 5W1H

2. マンダラート

9.1 Maximal Margin Classifier

9.1.1 What is a Hyperplane?

9.1.2 Classification Using a Separating Hyperplane

9.1.3 The Maximal Margin Classifier

9.1.4 Construction of the Maximal Margin Classifier

9.1.5 The Non-separable Case

9.2 Support Vector Classifiers

9.2.1 Overview of the Support Vector Classifier

9.2.2 Details of the Support Vector Classifier

9.3 Support Vector Machines

9.3.1 Classification with Non-linear Decision Boundaries

9.3.2 The Support Vector Machine

9.3.3 An Application to the Heart Disease Data

9.4 SVMs with More than Two Classes

9.4.1 One-Versus-One Classification

9.4.2 One-Versus-All Classification

9.5 Relationship to Logistic Regression

8.1 The Basics of Decision Trees

8.1.1 Regression Trees

Predicting Baseball Players' Salaries Using Regression Trees

Prediction via Stratification of the Feature Space

Tree Pruning

8.1.2 Classification Trees

8.1.3 Trees Versus Linear Models

8.1.4 Advantages and Disadvantages of Trees

8.2 Bagging, Random Forests, Boosting

8.2.1 Bagging

Out-of-Bag Error Estimation

Variable Importance Measures

8.2.2 Random Forests

8.2.3 Boosting

7.1 Polynomial Regression

7.2 Step Functions

7.3 Basis Functions

7.4 Regression Splines

7.4.1 Piecewise Polynomials

7.4.2 Constraints and Splines

7.4.3 The Spline Basis Regression

7.4.4 Choosing the Number and Locations of the Knots

7.4.5 Comparing to Polynomial Regression

7.5 Smoothing Splines

7.5.1 An Overview of Smoothing Splines

7.5.2 Choosing the Smoothing Parameter

7.6 Local Regression

7.7 Generalized Additive Model

7.7.1 GAMs for Regression Problems

Pros and Cons of GAMs

7.7.2 GAMs for Classification Problems

6.1 Subset Selection

6.1.1 Best Subset Selection

6.1.2 Stepwise Selection

Forward Stepwise Selection

Backward Stepwise Selection

Hybrid Approaches

6.1.3 Choosing the Optimal Model

, AIC, BIC, and Adjusted

Validation and Cross-Validation

6.2 Shrinkage Methods

6.2.1 Ridge Regression

An Application to the Credit Data

Why Does Ridge Regression Improve Over Least Squares?

6.2.2 The Lasso

Another Formulation for Ridge Regression and the Lasso

The Variable Selection Property of the Lasso

Comparing the Lasso and Ridge Regression

A Simple Special Case for Ridge Regression and the Lasso

Bayesian Interpretation for Ridge Regression and the Lasso

6.2.3 Selecting the Tuning Parameter

9.1　Maximal Margin Classifier

9.1.1　What is a Hyperplane?

9.1.2 　Classification Using a Separating Hyperplane

9.1.3　The Maximal Margin Classifier

9.1.4　Construction of the Maximal Margin Classifier

9.1.5　The Non-separable Case

9.2　Support Vector Classifiers

9.2.1　Overview of the Support Vector Classifier

9.2.2　Details of the Support Vector Classifier

9.3　Support Vector Machines

9.3.1　Classification with Non-linear Decision Boundaries

9.3.2　The Support Vector Machine

9.3.3　An Application to the Heart Disease Data

9.4.1　One-Versus-One Classification

9.4.2　One-Versus-All Classification

9.5　Relationship to Logistic Regression

8.1　The Basics of Decision Trees

8.1.1　Regression Trees

8.1.2　Classification Trees

8.1.3　Trees Versus Linear Models

8.1.4　Advantages and Disadvantages of Trees

8.2　Bagging, Random Forests, Boosting

8.2.1　Bagging

8.2.2　Random Forests

8.2.3　Boosting

7.1　Polynomial Regression

7.2　Step Functions

7.3　Basis Functions

7.4　Regression Splines

7.4.1　Piecewise Polynomials

7.4.2　Constraints and Splines

7.4.3　The Spline Basis Regression

7.4.4　Choosing the Number and Locations of the Knots

7.4.5　Comparing to Polynomial Regression

7.5　Smoothing Splines

7.5.1　An Overview of Smoothing Splines

7.5.2　Choosing the Smoothing Parameter $\lambda$

7.6　Local Regression

7.7　Generalized Additive Model

7.7.1　GAMs for Regression Problems

7.7.2　GAMs for Classification Problems

6.1　Subset Selection

6.1.1　Best Subset Selection

6.1.2　Stepwise Selection

6.1.3　Choosing the Optimal Model

$C_p$ , AIC, BIC, and Adjusted $R^{2}$

6.2　Shrinkage Methods

6.2.1　Ridge Regression

6.2.2　The Lasso

6.2.3　Selecting the Tuning Parameter

6.3　Dimension Reduction Methods

6.3.1　Principal Components Regression

6.3.2　Partial Least Squares

6.4　Considerations in High Dimensions

6.4.1　High-Dimensional Data

6.4.2　What Goes Wrong in High Dimensions

6.4.3　Regression in High Dimensions

6.4.4　Interpreting Results in High Dimensions

5.1　Cross-Validation

5.1.1　The Validation Set Approach

5.1.2　Leave-One-Out Cross-Validation (LOOCV)

5.1.3　k-Fold Cross-Validation

5.1.4　Bias-Variance Trade-Off for k-Fold Cross-Validation

5.1.5　Cross-Validation on Classification Problems

5.2　The Bootstrap

4.1　An Overview of Classification

4.2　Why Not Linear Regression?

4.3　Logistic Regression

4.3.1　The Logistic Model

4.3.2　Estimating the Regression Coefficients

4.3.3　Making Predictions

4.3.4　Multiple Logistic Regression

4.3.5　Logistic Regression for >2 Response Classes

4.4　Linear Discriminant Analysis

4.4.1　Using Bayes' Theorem for Classification

4.4.2　Linear Discriminant Analysis for p=1

4.4.3　Linear Discriminant Analysis for p>1

4.4.4　Quadratic Discriminant Analysis

4.5　A Comparison of Classification Methods