ex12noteB.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/takatakamanbou/ML/blob/2022/ex12noteB.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2UzDNLmVS3po"
      },
      "source": [
        "# ML ex12noteB\n",
        "\n",
        "<img width=72 src=\"https://www-tlab.math.ryukoku.ac.jp/~takataka/course/ML/ML-logo.png\"> [この授業のウェブページ](https://www-tlab.math.ryukoku.ac.jp/wiki/?ML/2022)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_WXvQDHGjLD8"
      },
      "source": [
        "----\n",
        "## 次元削減(1) 主成分分析 - 前編\n",
        "----\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "---\n",
        "### 次元削減とは\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "m_05KKmfwFQ_"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### ［復習］次元削減とは"
      ],
      "metadata": {
        "id": "EpJuLvvIHMs8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**次元削減**(次元圧縮とも，dimensionality reduction)は，その名の通り，データの「次元数」(dimensionality)を減らす手法です．\n",
        "$D$個の特徴量から成る $D$ 次元ベクトル $\\mathbf{x}$ がデータとして与えられた場合，これを $H$ 次元（$H<D$）のベクトル $\\mathbf{y}$ に変換します．\n",
        "変換後のデータは元データよりも少数の特徴で表されているため，その後の分析がより簡単になります．\n",
        "また，データを処理する際に必要な記憶容量や計算量の削減にもつながります．"
      ],
      "metadata": {
        "id": "TFNpSM4ctlC_"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "例1: 学生たちの20科目の成績を表すデータ（$D=20$）を次元削減．\n",
        "\n",
        "例えば，元データの特徴をよくとらえた3次元のデータに変換できたならば...．3つの特徴量の値によって一人ひとりの学生の傾向を分析することができる．次元を減らすことで分析や可視化が容易になる．"
      ],
      "metadata": {
        "id": "dyrpeh1zwpqx"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "例2: 様々なひとの顔画像（幅100画素高さ100画素のRGBカラー画像，$D = 30000$）を次元削減．\n",
        "\n",
        "元画像の本質的な特徴をなるべく保ったままで30次元のデータに変換できたならば...．ネットワーク越しに顔画像のデータを送信するとして，3万個の画素値を送るかわりに，30個の数値を送るだけで済ませられるかも？\n"
      ],
      "metadata": {
        "id": "PUfz7CiIFdo8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 線形変換による次元削減"
      ],
      "metadata": {
        "id": "R9wMLNREHSje"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "上記の通り，次元削減の問題は，データとして与えられる $D$ 次元ベクトル $\\mathbf{x}\\in {\\cal R}^{D}$ を何らかの方法で $H$ 次元（$H<D$）ベクトルへと変換することです．\n",
        "その方法として最も簡単なのは，線形変換（一次変換）を用いることです．\n",
        "\n",
        "ベクトルを列ベクトルとして表すことにして，上記の $\\mathbf{x}$ を\n",
        "\n",
        "$$\n",
        "\\mathbf{x} = \\begin{pmatrix}\n",
        "x_1\\\\ x_2 \\\\ \\vdots \\\\ x_D\n",
        "\\end{pmatrix} \n",
        "$$\n",
        "\n",
        "のように $D\\times 1$ 行列として表します．このとき，適当な $H\\times D$ 行列 $W$ を用意すれば，$\\mathbf{y} = W\\mathbf{x}$ という変換によって $H\\times 1$行列すなわち$H$次元ベクトルを得ることができます．このように線形変換によって次元削減を実現する場合，この行列 $W$ を問題に応じて決めてやればよいことになります．つまり，この$W$が線形変換による次元削減のモデルパラメータです．\n",
        "\n",
        "線形変換による次元削減は，次元削減の方法としては単純なものですが，データ分析や機械学習の分野で幅広く用いられています．\n",
        "以下では，その方法の代表例として，「主成分分析」を取り上げます．\n",
        "実際のデータ分析・機械学習の問題では，より高度な次元削減を実現するために非線形変換を利用したもっと複雑な方法も用いられますが，この授業では説明しません．"
      ],
      "metadata": {
        "id": "X9QHEPw6BFMj"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "ここで，線形変換のことを理解しやすくするために，少し補足をしておきます．\n",
        "上記の行列 $W$ の要素を\n",
        "$$\n",
        "W = \\begin{pmatrix}\n",
        "w_{1,1} & w_{1,2} & \\dots & w_{1,D}\\\\\n",
        "w_{2,1} & w_{2,2} & \\dots & w_{2,D}\\\\\n",
        "w_{H,1} & w_{H,2} & \\dots & w_{H,D}\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "と表して，\n",
        "その各行（列ではありません）の要素をならべて次のような $D\\times 1$ 行列をつくります．\n",
        "$$\n",
        "\\mathbf{w}_h = \\begin{pmatrix}\n",
        "w_{h,1}\\\\\n",
        "w_{h,2}\\\\\n",
        "\\vdots\\\\\n",
        "w_{h,D}\n",
        "\\end{pmatrix} \\quad (h = 1, 2, \\ldots, H)\n",
        "$$\n",
        "つまり，\n",
        "$$\n",
        "W = \\begin{pmatrix}\n",
        "\\mathbf{w}_{1}^{\\top}\\\\\n",
        "\\mathbf{w}_{2}^{\\top}\\\\\n",
        "\\vdots\\\\\n",
        "\\mathbf{w}_{H}^{\\top}\n",
        "\\end{pmatrix}\n",
        "$$\n",
        "です．このとき，\n",
        "$$\n",
        "W\\mathbf{x} = \\begin{pmatrix}\n",
        "\\mathbf{w}_{1}^{\\top}\\\\\n",
        "\\mathbf{w}_{2}^{\\top}\\\\\n",
        "\\vdots\\\\\n",
        "\\mathbf{w}_{H}^{\\top}\n",
        "\\end{pmatrix} \\mathbf{x}\n",
        "= \\begin{pmatrix}\n",
        "\\mathbf{w}_{1}^{\\top}\\mathbf{x}\\\\\n",
        "\\mathbf{w}_{2}^{\\top}\\mathbf{x}\\\\\n",
        "\\vdots\\\\\n",
        "\\mathbf{w}_{H}^{\\top}\\mathbf{x}\n",
        "\\end{pmatrix} \n",
        "$$\n",
        "となりますので，\n",
        "$$\n",
        "\\mathbf{y} = \\begin{pmatrix}\n",
        "y_{1}\\\\\n",
        "y_{2}\\\\\n",
        "\\vdots\\\\\n",
        "y_{H}\n",
        "\\end{pmatrix} = \\begin{pmatrix}\n",
        "\\mathbf{w}_{1}^{\\top}\\mathbf{x}\\\\\n",
        "\\mathbf{w}_{2}^{\\top}\\mathbf{x}\\\\\n",
        "\\vdots\\\\\n",
        "\\mathbf{w}_{H}^{\\top}\\mathbf{x}\n",
        "\\end{pmatrix} \n",
        "$$\n",
        "と書けます．したがって，変換後のベクトルの $h$ 番目の要素 $y_h$ は\n",
        "$$\n",
        "y_h = \\mathbf{w}_{h}^{\\top}\\mathbf{x}\\quad (h = 1, 2, \\ldots, H)\n",
        "$$\n",
        "となります．この式の右辺は，$D$次元ベクトル $\\mathbf{w}_h$ と $\\mathbf{x}$ の内積に等しいですので，次のように表記することもできます．\n",
        "$$\n",
        "y_h = \\mathbf{w}_h\\cdot\\mathbf{x} \\quad (h = 1, 2, \\ldots, H)\n",
        "$$\n",
        "すなわち，$H\\times D$ 行列 $W$ による $\\mathbf{y} = W\\mathbf{x}$ という変換は，$H$本の$D$次元ベクトル $\\mathbf{w}_h$ ($h = 1, 2, \\ldots, H$)を用意して，そのそれぞれと $\\mathbf{x}$ との内積を求める計算をしていることに相当します．"
      ],
      "metadata": {
        "id": "mAewW8q5AnPw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "####［余談だよん］\n",
        "\n",
        "上記では，データひとつを $D\\times 1$ 行列として表記していますので，要素が縦に並んでいます．\n",
        "しかし，コンピュータでデータを扱う際は，数値を横に並べて，1行が1つのデータという形式で表すことがよくあります．\n",
        "その場合，複数のデータをまとめて扱う際に，それを表す配列・行列が数式で想定しているものと縦横逆になっている，つまり転置になっていたりしますので，注意が必要です．\n",
        "\n",
        "ちなみに，データひとつを $1 \\times D$ 行列として扱うことにした場合，上記の変換は\n",
        "$$\n",
        "\\mathbf{y} = \\mathbf{x}W^{\\top}\n",
        "$$\n",
        "と書けます．"
      ],
      "metadata": {
        "id": "WYSCjGYPObiQ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "---\n",
        "### 主成分分析（前編）\n",
        "\n",
        "データ分析・多変量解析の方法としてよく知られた **主成分分析** (Principal Component Analysis, PCA)は，線形変換による次元削減の方法のひとつです．\n",
        "ここでは，削減後の次元数が $1$ である場合，つまり，$D$ 次元のベクトルを1つの数値に変換する場合に限定して，主成分分析を導入します．"
      ],
      "metadata": {
        "id": "SrsO1YCeQF1C"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 主成分分析の考え方"
      ],
      "metadata": {
        "id": "EZaZtghaReYS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "主成分分析では，「変換後のデータの分散がなるべく大きくなるように（元のデータの分散を保つように）」次元削減を行います．\n",
        "ここでは，元のデータの次元数 $D = 2$ の場合を例として，これを1次元に次元削減する場合を図に描きながら考えてみましょう．\n"
      ],
      "metadata": {
        "id": "WrGVPXTSm8Dx"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "下図の左は，とある2次元のデータを散布図に描いたものです．二つの破線はそれぞれ，横軸と縦軸の値の平均を表しています．\n",
        "このデータの値を，それらの平均が $\\mathbf{0}$ になるように平行移動させると，散布図は下図の右のようになります．\n",
        "以降，このように平均が $\\mathbf{0}$ になるように平行移動させたデータの集合を \n",
        "$$\n",
        "\\{ \\mathbf{x}_n \\in {\\cal R}^{D} | n = 1, 2, \\ldots, N\\}\n",
        "$$\n",
        "と表すことにします．\n",
        "\n",
        "<img src=\"https://www-tlab.math.ryukoku.ac.jp/~takataka/course/ML/pcafig01.png\">\n"
      ],
      "metadata": {
        "id": "-c1lfi3GkKTw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "このようなデータを1次元に次元削減する線形変換は，$D$次元ベクトル $\\mathbf{u} \\in {\\cal R}^{D}$ をひとつ定めて，下図のように$D$次元ベクトル $\\mathbf{x}$ を1つの実数値 $y$ に変換する操作と考えられます．\n",
        "\n",
        "\n",
        "<img src=\"https://www-tlab.math.ryukoku.ac.jp/~takataka/course/ML/pcafig02.png\">\n",
        "\n",
        "この図の左の赤い直線は，ベクトル $\\mathbf{u}$ の向きを表しています．個々のデータ $\\mathbf{x}$ に対して，「その点がこの赤い直線上に落とす影」を考えて，この直線上でのその影の位置を $y$ とおくと，右図に示すように\n",
        "$$\n",
        "y = \\Vert\\mathbf{x}\\Vert\\cos\\theta\n",
        "$$\n",
        "となります．$\\theta$ は $\\mathbf{x}$ と $\\mathbf{u}$ の成す角，$\\Vert\\mathbf{x}\\Vert$ は $\\mathbf{x}$ の大きさです．\n",
        "$\\mathbf{u}\\cdot\\mathbf{x} = \\Vert\\mathbf{u}\\Vert\\Vert\\mathbf{x}\\Vert\\cos\\theta$ であることから，上の式は，次のように書き換えられます．\n",
        "$$\n",
        "y = \\frac{\\mathbf{u}\\cdot\\mathbf{x}}{\\Vert\\mathbf{u}\\Vert}\n",
        "$$\n",
        "与えられたデータに対して，ベクトル $\\mathbf{u}$ を適当に定めてやれば，この式によって $D$ 次元のデータを1つの実数値に変換できます．\n",
        "\n",
        "ここで，ベクトル $\\mathbf{u}$  として，向きが同じで大きさのみ異なる二つの候補があったとしてみましょう．その場合，得られる $y$ の値はどちらを用いても同じとなります．つまり，ここで考えている変換では，ベクトル $\\mathbf{u}$ の向きのみが重要ということになります．\n",
        "そのため，ベクトル $\\mathbf{u}$ の大きさは $1$ に限定して考えることができます．この場合，$\\Vert\\mathbf{u}\\Vert = 1$ ですので，上の式はより簡単に\n",
        "$$\n",
        "y = \\mathbf{u}\\cdot\\mathbf{x}\n",
        "$$\n",
        "と表せます．"
      ],
      "metadata": {
        "id": "EopPQdzVnEGO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "以上より，大きさ$1$の$D$次元ベクトル $\\mathbf{u}$ を適当に定めれば，$y_n = \\mathbf{u}\\cdot\\mathbf{x}_n$ という式で1次元への次元削減ができることが分かりました．\n",
        "では，$\\mathbf{u}$ はどのように定めればよいでしょうか？\n",
        "\n",
        "主成分分析の目的は，「変換後のデータの分散がなるべく大きくなるように（元のデータの分散を保つように）」することでした．$\\mathbf{u}$の向きを変えると，変換後の値 $y_n$ の分散の大きさも変化します．\n",
        "以下の図(a), (b), (c) は，3種類の $\\mathbf{u}$ で2次元のデータを1次元に変換した様子と，変換後の値の分散を示しています．\n",
        "右図は横軸に $y_n$ の値をとっており，'variance'の値が $y_n$ の分散です．\n",
        "\n",
        "\n",
        "<img src=\"https://www-tlab.math.ryukoku.ac.jp/~takataka/course/ML/pcafig03.png\">\n",
        "\n",
        "<img src=\"https://www-tlab.math.ryukoku.ac.jp/~takataka/course/ML/pcafig04.png\">\n",
        "\n",
        "<img src=\"https://www-tlab.math.ryukoku.ac.jp/~takataka/course/ML/pcafig05.png\">\n",
        "\n",
        "図を見ると，データの散らばりが大きい方向を $\\mathbf{u}$ が向いたときに，変換後の分散が大きくなっていることがわかります．\n",
        "直感的な説明になりますが，変換後の値だけを見て元のデータの様子を想像するなら，分散が大きい方が，個々の値の違いがわかりやすくてうれしいですね．\n",
        "\n",
        "ここまで，データを1次元に次元削減する場合限定で，主成分分析の考え方を説明してきました．\n",
        "次のセクションでは，このような主成分分析の問題をきちんと定式化して，その解がどのようなものかを説明します．"
      ],
      "metadata": {
        "id": "0HVeIJQGvmIF"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 主成分分析の問題の解（1次元にする場合）"
      ],
      "metadata": {
        "id": "yTqwvU2Q0jd8"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "［主成分分析の問題設定（1次元にする場合）］\n",
        "\n",
        "$N$個の$D$次元ベクトルから成る学習データが与えられるとする．\n",
        "$$\n",
        "\\{ \\mathbf{x}_n \\in {\\cal R}^{D} | n = 1, 2, \\ldots, N\\}\n",
        "$$\n",
        "このデータの平均は \n",
        "$$\n",
        "\\frac{1}{N}\\sum_{n=1}^{N}\\mathbf{x}_{n} = \\mathbf{0}\n",
        "$$\n",
        "と仮定する（$\\mathbf{0}$でない場合は，平均を求めてそれをデータから差し引いたものをあらためて学習データとすればよい）．\n",
        "大きさ $1$ の $D$ 次元ベクトル $\\mathbf{u}$ を用いて，次式によって $D$次元ベクトル $\\mathbf{x}$ を1つの実数値 $y_n$ に変換することを考える．\n",
        "$$\n",
        "y_n = \\mathbf{u}\\cdot \\mathbf{x}_n \\quad (n = 1, 2, \\ldots, N)\n",
        "$$\n",
        "ベクトル $\\mathbf{u}$ を，大きさ1($\\Vert\\mathbf{u}\\Vert = 1$)のベクトルの中で $y_n$の分散が最大となるように定めたい．\n"
      ],
      "metadata": {
        "id": "C0p945uO1KZz"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "これが主成分分析の問題設定です．\n",
        "この問題の解，つまり，$y_n$ の分散を最大にする $\\mathbf{u}$ は，「データ$\\mathbf{x}_n$の分散共分散行列（注）の固有ベクトルのうち，最大の固有値に対応するもの」となります（導出過程は後述）．\n",
        "したがって，学習データから分散共分散行列を計算し，その固有値固有ベクトルを求めれば，主成分分析による次元削減を実現できます．\n",
        "\n",
        "<span style=\"font-size: 75%\">\n",
        "※注: 「分散共分散行列」とは何かという話は省略します．興味のあるひとは，データ分析・多変量解析・統計の書籍等で調べてみてね．\n",
        "</span>"
      ],
      "metadata": {
        "id": "eACBZ0j485rE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### ［発展］主成分分析の問題の解の導出（1次元にする場合）\n",
        "\n",
        "上記の解の導出過程の概略を以下に示します．"
      ],
      "metadata": {
        "id": "ftx-JdAM8-2R"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "$\\mathbf{x}_n$ の平均が $\\mathbf{0}$ なので，$y_n$ の平均も $0$ となります．そのため，$y_n$ の分散は\n",
        "$$\n",
        "\\frac{1}{N}\\sum_{n=1}^{N}y_n^2\n",
        "$$\n",
        "と表せます．この式は，次のように変形できます．\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\frac{1}{N}\\sum_{n=1}^{N}y_n^2 &= \\frac{1}{N}\\sum_{n=1}^{N} (\\mathbf{u}\\cdot\\mathbf{x}_n)(\\mathbf{u}\\cdot\\mathbf{x}_n) \\\\\n",
        "&= \\frac{1}{N}\\sum_{n=1}^{N} \\left(\\mathbf{u}^{\\top}\\mathbf{x}_n\\right) \\left(\\mathbf{u}^{\\top}\\mathbf{x}_n\\right)^{\\top}\\\\\n",
        "&= \\frac{1}{N}\\sum_{n=1}^{N} \\mathbf{u}^{\\top}\\mathbf{x}_n\\mathbf{x}_n^{\\top} \\mathbf{u}\\\\\n",
        "&= \\mathbf{u}^{\\top}\\left( \\frac{1}{N}\\sum_{n=1}^{N}\\mathbf{x}_n\\mathbf{x}_n^{\\top}\\right) \\mathbf{u} = \\mathbf{u}^{\\top}V\\mathbf{u}\n",
        "\\end{aligned}\n",
        "$$\n",
        "ただし，\n",
        "$$\n",
        "V = \\frac{1}{N}\\sum_{n=1}^{N}\\mathbf{x}_n\\mathbf{x}_n^{\\top}\n",
        "$$\n",
        "は，$\\mathbf{x}_n$ の平均が $\\mathbf{0}$ であるため，$\\mathbf{x}_n$の分散共分散行列に一致します．\n",
        "\n"
      ],
      "metadata": {
        "id": "Nys0svaO20HI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "求めたいのは，$y_n$ の分散 $\\mathbf{u}^\\top V\\mathbf{u}$ を最大にするベクトル $\\mathbf{u}$ です．ただし，$\\mathbf{u}$ には $\\Vert\\mathbf{u}\\Vert = 1$ という条件があります．\n",
        "このような制約条件付きの最適化問題を解く定番の手法は，「ラグランジュの未定乗数法」です（注）．\n",
        "この問題の場合，ラグランジュ乗数を $\\lambda$ として，\n",
        "$$\n",
        "L = \\mathbf{u}^{\\top}V\\mathbf{u} - \\lambda(\\mathbf{u}^{\\top}\\mathbf{u} - 1)\n",
        "$$\n",
        "とおけば，$\\frac{\\partial L}{\\partial \\mathbf{u}} = \\mathbf{0}$ を満たす $\\mathbf{u}$ が解の候補となります．\n",
        "\n",
        "<span style=\"font-size: 75%\">\n",
        "※注: 「ラグランジュの未定乗数法」は，大学初年次の微積分で学んでいる...かも．興味のあるひとは数学の参考書を調べてね．\n",
        "</span>"
      ],
      "metadata": {
        "id": "O7wp00oc5zgi"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "ここで，\n",
        "$$\n",
        "\\frac{\\partial L}{\\partial \\mathbf{u}} = 2V\\mathbf{u} - 2\\lambda\\mathbf{u}\n",
        "$$\n",
        "なので（注），解は\n",
        "$$\n",
        "V\\mathbf{u} = \\lambda\\mathbf{u}\n",
        "$$\n",
        "を満たさねばなりません．この式より，解の候補は $V$ の単位固有ベクトルであることがわかります．この式を $L$ の式に代入すると，\n",
        "$$\n",
        "L = \\lambda\\mathbf{u}^\\top\\mathbf{u} - \\lambda\\cdot 0 = \\lambda\n",
        "$$\n",
        "となりますので，この問題の解は，$V$の最大固有値に対する固有ベクトルであることがわかります．\n",
        "\n",
        "<span style=\"font-size: 75%\">\n",
        "※注: $\\frac{\\partial L}{\\partial \\mathbf{u}}$ は，「$L$を $\\mathbf{u}$ の各要素で偏微分したものをならべたベクトル」です．\n",
        "</span>"
      ],
      "metadata": {
        "id": "mJMtkVi69mKN"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "dxEEwi_41bNI"
      },
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.9.7"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}