閃 き

閃き- blog

きらびやかに、美しく、痛烈に.

Ubuntu 16.04.6 LTS (GNU/Linux / x86_64) のGPUセットアップ

https://images.techhive.com/images/article/2016/04/ubuntu-16.04-xenial-xerus-100656151-large.jpg

実行環境

latest update : 2019/05/15

  • OS : Ubuntu 16.04.6 LTS (GNU/Linux 4.4.0-145-generic x86_64)
  • Memory : 16 GB
  • CPU(x8) : Intel Core i7-6700 CPU @ 3.40GHz
  • GPU(x1) : NVIDIA Geforce GTX 1080
    • NVIDIA CUDA : 9.0.176 (/usr/local/cuda-10.1/)
    • NVIDIA cuDNN : 7.5.1 (/usr/lib/x86_64-linux-gnu/libcudnn.so.7.5.1)
    • Python3 : 3.5.2 (/usr/bin/python3)
    • Python2 : 2.7.12 (/usr/bin/python)
      • tensorflow : 1.13.1 ($HOME/.local/lib/python3.5/site-packages)
      • tensorflow-gpu : 1.10.0 ($HOME/.local/lib/python3.5/site-packages)
      • keras : 2.2.4 ($HOME/.local/lib/python3.5/site-packages)

OS

/etc/os-releaseをみる.

# OSの確認
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.6 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.6 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

unameコマンドを使う.

# OS名,ホスト名,OSリリース,OSバージョン,マシンアーキテクチャ,CPUタイプ,プラットフォーム,OS名
$ uname -a
Linux XXXX 4.4.0-145-generic #171-Ubuntu SMP Tue Mar 26 12:43:40 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
# Linuxディストリビューションを確認
$ cat /etc/issue
Ubuntu 16.04.6 LTS \n \l

HDD

$ df -h
Filesystem      Size  Used Avail Use% Mounted on
udev            7.8G     0  7.8G   0% /dev
tmpfs           1.6G   34M  1.6G   3% /run
/dev/sda1       214G  101G  103G  50% /
tmpfs           7.9G     0  7.9G   0% /dev/shm
tmpfs           5.0M  4.0K  5.0M   1% /run/lock
tmpfs           7.9G     0  7.9G   0% /sys/fs/cgroup
tmpfs           1.6G   64K  1.6G   1% /run/user/1001
/dev/loop0       89M   89M     0 100% /snap/core/7270
/dev/loop1      384K  384K     0 100% /snap/patchelf/61
/dev/loop2      384K  384K     0 100% /snap/patchelf/69

メモリ

  • メモリデバイスの確認 /proc/meminfoをみる.
# メモリの確認
$ cat /proc/meminfo
MemTotal:       16377200 kB
MemFree:         3077848 kB
MemAvailable:   15767804 kB
Buffers:          363052 kB
Cached:         12274992 kB
SwapCached:        66936 kB
Active:          8048088 kB
Inactive:        4689560 kB
Active(anon):      25860 kB
Inactive(anon):    86584 kB
Active(file):    8022228 kB
Inactive(file):  4602976 kB
Unevictable:           0 kB
Mlocked:               0 kB
SwapTotal:      16720892 kB
SwapFree:       16630144 kB
Dirty:                 0 kB
Writeback:             0 kB
AnonPages:         34796 kB
Mapped:            45308 kB
Shmem:             12840 kB
Slab:             443464 kB
SReclaimable:     406084 kB
SUnreclaim:        37380 kB
KernelStack:        3440 kB
PageTables:         4512 kB
NFS_Unstable:          0 kB
Bounce:                0 kB
WritebackTmp:          0 kB
CommitLimit:    24909492 kB
Committed_AS:     547432 kB
VmallocTotal:   34359738367 kB
VmallocUsed:           0 kB
VmallocChunk:          0 kB
HardwareCorrupted:     0 kB
AnonHugePages:         0 kB
CmaTotal:              0 kB
CmaFree:               0 kB
HugePages_Total:       0
HugePages_Free:        0
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
DirectMap4k:     1907316 kB
DirectMap2M:    14815232 kB
DirectMap1G:           0 kB

freeを使う.

$ free
              total        used        free      shared  buff/cache   available
Mem:       16377200     4286984     2705876       29268     9384340    11676988
Swap:      16720892       90724    16630168

vmstatを使う.

$ vmstat
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 2  0  90724 1771068 363852 9020168  322  295   335   492    1    1  2  0 97  1  0

topを使う.

$ top
top - 20:17:14 up 56 days,  1:17,  5 users,  load average: 2.02, 1.99, 1.66
Tasks: 180 total,   3 running, 177 sleeping,   0 stopped,   0 zombie
%Cpu(s): 25.0 us,  0.0 sy,  0.0 ni, 75.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
KiB Mem : 16377200 total,  1078612 free,  5914516 used,  9384072 buff/cache
KiB Swap: 16720892 total, 16630168 free,    90724 used. 10049856 avail Mem 

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                                                                                                      
14461 xxxxxxx   20   0 54.634g 1.768g  12740 R 100.0 11.3  18:30.96 python3                                                                                                      
14499 xxxxxxx   20   0 54.634g 1.752g  12448 R 100.0 11.2  17:54.35 python3                                                                                                      
    1 root      20   0  119680   4616   3084 S   0.0  0.0   0:31.51 systemd                                                                                                      
    2 root      20   0       0      0      0 S   0.0  0.0   0:00.20 kthreadd                                                                                                     
    3 root      20   0       0      0      0 S   0.0  0.0   0:05.32 ksoftirqd/0                                                                                                  
    5 root       0 -20       0      0      0 S   0.0  0.0   0:00.00 kworker/0:0H                                                                                                 
    7 root      20   0       0      0      0 S   0.0  0.0  18:07.52 rcu_sched                                                                                                    
    8 root      20   0       0      0      0 S   0.0  0.0   0:00.00 rcu_bh                                                                                                       
    9 root      rt   0       0      0      0 S   0.0  0.0   0:00.25 migration/0        
...     

CPU

  • CPUデバイスの確認 /proc/cpuinfoをみる.
# CPUデバイスの確認
$ cat /proc/cpuinfo
processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 94
model name  : Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
stepping    : 3
microcode   : 0xc6
cpu MHz     : 800.062
cache size  : 8192 KB
physical id : 0
siblings    : 8
core id     : 0
cpu cores   : 4
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 22
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch epb invpcid_single intel_pt ssbd ibrs ibpb stibp kaiser tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d
bugs        : cpu_meltdown spectre_v1 spectre_v2 spec_store_bypass l1tf
bogomips    : 6816.61
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor   : 1
vendor_id   : GenuineIntel
cpu family  : 6
model       : 94
model name  : Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
...

GPU

# GPUデバイスの確認
$ sudo lshw -C display 
  *-display
       詳細: VGA compatible controller
       製品: GP104 [GeForce GTX 1080]
       ベンダー: NVIDIA Corporation
       物理ID: 0
       バス情報: pci@0000:01:00.0
       バージョン: a1
       幅: 64 bits
       クロック: 33MHz
       性能: pm msi pciexpress vga_controller bus_master cap_list rom
       設定: driver=nvidia latency=0
       リソース: irq:16 メモリー:de000000-deffffff メモリー:c0000000-cfffffff メモリー:d0000000-d1ffffff IOポート:e000(サイズ=128) メモリー:df000000-df07ffff

lspciでハードウェアデバイス一覧が確認できる.

# GPUデバイスの確認
$ lspci  | grep -i nvidia 
01:00.0 VGA compatible controller: NVIDIA Corporation GP104 [GeForce GTX 1080] (rev a1)
01:00.1 Audio device: NVIDIA Corporation GP104 High Definition Audio Controller (rev a1)

CUDA

# CUDAの.debパッケージをインストール
$ sudo dpkg -i cuda-repo-ubuntu1604_9.0.176-1_amd64.deb 
$ sudo apt update
$ sudo apt install cuda-9-0
  • CUDAの確認 nvccのPATHを通すために,~/.bashrcに以下を書いておく.
# export PATH=/usr/local/cuda-9.0/bin:${PATH}
# export LD_LIBRARY_PATH=/usr/local/cuda-9.0/lib64:${LD_LIBRARY_PATH}

CUDAの詳細情報は,nvccコマンドで取得できる.

# CUDAの確認
$ nvcc -V
nvcc: NVIDIA (R) Cuda compiler driver
Copyright (c) 2005-2017 NVIDIA Corporation
Built on Fri_Sep__1_21:08:03_CDT_2017
Cuda compilation tools, release 9.0, V9.0.176

CUDAのバージョンを確認したい場合,/usr/local/cuda/version.txtをみればよい.

# CUDAのバージョン確認
$ cat /usr/local/cuda/version.txt
CUDA Version 9.0.176

cuDNN

  • cuDNNのインストール https://developer.nvidia.com/rdp/cudnn-download にて,3つのパッケージをDownload(Loginする必要あり)
    • "Download cuDNN v7.5.1 (April 22, 2019), for CUDA 10.1"
    • cuDNN Runtime Library for Ubuntu16.04 (Deb)
    • cuDNN Developer Library for Ubuntu16.04 (Deb)
    • cuDNN Code Samples and User Guide for Ubuntu16.04 (Deb)
# パッケージをダウンロードしたディレクトリで,パッケージをインストール
# 公式ドキュメント: https://docs.nvidia.com/deeplearning/sdk/cudnn-install/index.html
$ sudo dpkg -i libcudnn7_7.5.1.10-1+cuda10.1_amd64.deb     # Runtime library
$ sudo dpkg -i libcudnn7-dev_7.5.1.10-1+cuda10.1_amd64.deb # Developer library 
$ sudo dpkg -i libcudnn7-doc_7.5.1.10-1+cuda10.1_amd64.deb # Code sample & User guide
  • cuDNNの動作確認
# サンプルコードを実行してcuDNNの動作確認
# ホームディレクトリにサンプルコードをコピー
$ cuda-install-samples-10.1.sh ~
$ cd ~/NVIDIA_CUDA-10.1_Samples
$ make
$ cd 2_Graphics/volumeRender
$ ./volumeRender # exeファイルを実行する
$ rm -rfv ~/NVIDIA_CUDA-10.1_Samples/ # サンプルコードを消す。
  • cuDNNの確認 dpkg -lコマンドでインストール済みのパッケージを一覧表示する.
# マシンにインストール済みのcuDNNパッケージを一覧表示
$ dpkg -l | grep cudnn
ii  libcudnn7                                  7.5.1.10-1+cuda10.1                          amd64        cuDNN runtime libraries
ii  libcudnn7-dev                              7.5.1.10-1+cuda10.1                          amd64        cuDNN development libraries and headers
ii  libcudnn7-doc                              7.5.1.10-1+cuda10.1                          amd64        cuDNN documents and samples
  • cuDNNの保存場所
# debパッケージが保存されているディレクトリを確認(-Lオプション)
$ dpkg -L libcudnn7
/.
/usr
/usr/share
/usr/share/lintian
/usr/share/lintian/overrides
/usr/share/lintian/overrides/libcudnn7
/usr/share/doc
/usr/share/doc/libcudnn7
/usr/share/doc/libcudnn7/changelog.Debian.gz
/usr/share/doc/libcudnn7/copyright
/usr/lib
/usr/lib/x86_64-linux-gnu
/usr/lib/x86_64-linux-gnu/libcudnn.so.7.5.1
/usr/lib/x86_64-linux-gnu/libcudnn.so.7

NVIDIA ドライバ

# マシンにインストール済みのNVIDIAドライバを一覧表示
$ dpkg -l | grep nvidia
rc  nvidia-384                                 384.130-0ubuntu0.16.04.2                     amd64        NVIDIA binary driver - version 384.130
rc  nvidia-418                                 418.56-0ubuntu0~gpu16.04.1                   amd64        NVIDIA binary driver - version 418.56
ii  nvidia-430                                 430.09-0ubuntu0~gpu16.04.1                   amd64        NVIDIA binary driver - version 430.09
ii  nvidia-cuda-doc                            7.5.18-0ubuntu1                              all          NVIDIA CUDA and OpenCL documentation
ii  nvidia-cuda-gdb                            7.5.18-0ubuntu1                              amd64        NVIDIA CUDA Debugger (GDB)
rc  nvidia-cuda-toolkit                        7.5.18-0ubuntu1                              amd64        NVIDIA CUDA development toolkit
ii  nvidia-modprobe                            418.67-0ubuntu1                              amd64        Load the NVIDIA kernel driver and create device files
ii  nvidia-opencl-dev:amd64                    7.5.18-0ubuntu1                              amd64        NVIDIA OpenCL development files
rc  nvidia-opencl-icd-384                      384.130-0ubuntu0.16.04.2                     amd64        NVIDIA OpenCL ICD
rc  nvidia-opencl-icd-418                      418.56-0ubuntu0~gpu16.04.1                   amd64        NVIDIA OpenCL ICD
ii  nvidia-prime                               0.8.2                                        amd64        Tools to enable NVIDIA's Prime
ii  nvidia-settings                            418.67-0ubuntu1                              amd64        Tool for configuring the NVIDIA graphics driver
# NVIDIA ドライバを提供している xorg-edgers レポジトリを追加する
$ sudo add-apt-repository ppa:xorg-edgers/ppa -y
$ sudo apt-get update
# apt-getでインストールできるNVIDIAドライバの一覧表示
$ apt-cache search "^nvidia-[0-9]{3}$"
nvidia-352 - Transitional package for nvidia-375
nvidia-367 - Transitional package for nvidia-387
nvidia-375 - Transitional package for nvidia-418
nvidia-384 - NVIDIA binary driver - version 384.183
nvidia-390 - NVIDIA binary driver - version 390.116
nvidia-396 - NVIDIA binary driver - version 396.82
nvidia-410 - NVIDIA binary driver - version 410.104
nvidia-418 - NVIDIA binary driver - version 418.67
nvidia-304 - NVIDIA legacy binary driver - version 304.137
nvidia-331 - Transitional package for nvidia-331
nvidia-340 - NVIDIA binary driver - version 340.107
nvidia-387 - Transitional package for nvidia-390
nvidia-415 - NVIDIA binary driver - version 415.27
nvidia-430 - NVIDIA binary driver - version 430.14
# ドライバ nvidia-396 をインストール
$ sudo apt-get install -y nvidia-396
$ reboot

-CUDA(/usr/local/cuda-***/bin)のPATHチェック

# 出力に"/usr/local/cuda-10.1/bin"が含まれているか?
$ echo $PATH
  • CUDAとNVIDIAドライバ(/usr/lib/nvidia-***)のPATHチェック
# 出力に"/usr/local/cuda-10.1/lib64"と"/usr/lib/nvidia-418"が含まれているか?
$ echo $LD_LIBRARY_PATH  
  • CUDAとnvccコマンドのPATHチェック
# 出力が"/usr/local/cuda-10.1/bin/nvcc"になっているか?
$ which nvcc             
/usr/local/cuda-9.0/bin/nvcc
  • nvidia-smiコマンドのPATHチェック
# 出力が"/usr/bin/nvidia-smi"になっているか?
 $ which nvidia-smi
/usr/bin/nvidia-smi

# GPUの状態が表示されているか?
$ nvidia-smi             
Thu May 16 13:26:12 2019
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 430.14       Driver Version: 430.14       CUDA Version: N/A      |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  GeForce GTX 1080    Off  | 00000000:01:00.0 Off |                  N/A |
| 32%   42C    P5    27W / 200W |      0MiB /  8118MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+

+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
|  No running processes found                                                 |
+-----------------------------------------------------------------------------+

Pythonパッケージ

tensorflow インストール (1.10.0以上だとCUDAに対応していないかも)

# tensorflow インストール (1.10.0以上だとCUDAに対応していないかも)
$ pip3 uninstall tensorflow-gpu
$ pip3 install tensorflow-gpu==1.10.0
$ python3 -c 'import tensorflow as tf; print(tf.__version__)' # version check


参考文献

ARMA Process(自己回帰移動平均過程)

https://s3.amazonaws.com/quantstartmedia/images/qs-tsa-armapq-amzn-cl.png

このポストでは,時系列データに対する基本的なモデル,ARMA過程についてまとめます.

経済・ファイナンスデータの計量時系列分析 (統計ライブラリー)

経済・ファイナンスデータの計量時系列分析 (統計ライブラリー)

MA(q)過程: Moving average process

  • モデル式:MA(q)

y_t = \mu + \epsilon_t + (\theta_1, \cdots \theta_q)
\left( \begin{array}{c} \epsilon_{t-1}  \\ \vdots \\ \epsilon_{t-q} \end{array}\right),
 ~~~  \epsilon_{t} \sim W.N.(\sigma^2)
  • 統計量

\left\{
\begin{array}{c}
\begin{align}
E[y_t] &= \mu \\
V[y_t] &= \gamma_0 = (1 + {\theta_1}^{2} + \cdots + {\theta_q}^{2}) \cdot {\sigma}^{2} 
\end{align}
\end{array}
\right.



\begin{align}
Cov[y_t,y_{t-k}] &= \gamma_k \\
&= \left\{ \begin{array}{c}(\theta_k + \theta_1\theta_{k+1} + \cdots + \theta_{q-k}\theta_{k}) \cdot {\sigma}^{2} ~~~  (1 \leq k \leq q) \\ 0 \hspace{12em} (k \geq q+1)  \end{array} \right. 
\\ \\
\rho_k &= \frac{\gamma_k}{\gamma_0} \\
&= \left\{ \begin{array}{c} {\large \frac{\theta_k + \theta_1\theta_{k+1} + \cdots + \theta_{q-k}\theta_{k}}{1 + {\theta_1}^2 + \cdots + {\theta_q}^2} } ~~~  &(1 \leq k \leq q) \\ 0 \hspace{7em} &(k \geq q+1)  \end{array} \right. 
\end{align}
  • 定常性

    MA(q)モデルでは統計量( E, V, Cov)は,パラメータ \theta_1, \cdots, \theta_qの値に依らず,常に定常となる.


AR(p)過程: Autoregressive process

  • モデル:AR(p)

y_t = c + \epsilon_t + \left( \phi_1, \cdots, \phi_p \right)
\left( \begin{array}{c} y_{t-1}  \\ \vdots \\ y_{t-p} \end{array} \right) , ~~~ \epsilon_{t} \sim W.N.(\sigma^2)
  • 統計量

\\
\begin{array}{c}
\begin{align}
E[y_t] &= \mu \\
&= c + \phi_1 E[y_{t-1}] + \cdots + \phi_p E[y_{t-p}] \\
&= \frac{c}{1 - \phi_1 - \cdots - \phi_p}
\\ \\
V[y_t] &= \gamma_0 \\
&= {\sigma}^{2} + \phi_1^2 V[y_{t-1}] + \cdots + \phi_p^2 V[y_{t-p}] \\
&= \frac{\sigma^2}{(1 - \phi_1^2\rho_1 - \cdots - \phi_p^2 \rho_p)}
\end{align}
\end{array}


 
\begin{align}
\\
Cov[y_t,y_{t-k}] &= \gamma_k = \phi_1 \gamma_{k-1} + \cdots + \phi_p \gamma_{k-p} \hspace{2em}  (1 \leq k)
\\ \\
\rho_k &= \frac{\gamma_k}{\gamma_0} = \phi_1 \rho_{k-1} + \cdots + \phi_p \rho_{k-p} \hspace{2em} (1 \leq k) 
\\ \\ 
\rho_1 &= \frac{\gamma_1}{\gamma_0} = \phi_1
\end{align}
  • 定常性

    AR(p)モデルでは統計量( E,V,Cov)は,パラメータ \phi_1, \cdots, \phi_qの値に対して,特性方程式: $$ 1 - \phi_1 {z}^1 - \cdots - \phi_p {z}^{p} = 0 $$ の複素数 zの絶対値が1よりも大きい時,定常となる.


ARMA(p,q)過程: Autoregressive moving average process

  • モデル:ARMA(p,q)
 
y_t = c + \left( \phi_1, \cdots, \phi_p \right) \left( \begin{array}{c} y_{t-1}  \\ \vdots \\ y_{t-p} \end{array} \right)
+ (\theta_1, \cdots \theta_q) \left( \begin{array}{c} \epsilon_{t-1}  \\ \vdots \\ \epsilon_{t-q} \end{array}\right),
~~~ \epsilon_t \sim W.N.(\sigma^2)
  • 統計量

\begin{array}{c}
\begin{align}
E[y_t] &= \mu \\
&= c + \phi_1 E[y_{t-1}] + \cdots + \phi_p E[y_{t-p}] \\
&= \frac{c}{1 - \phi_1 - \cdots - \phi_p}
\\ \\
V[y_t] &= \gamma_0 \\
&= {\sigma}^{2} + \phi_1^2 V[y_{t-1}] + \cdots + \phi_p^2 V[y_{t-p}] \\
&= \frac{{\sigma}^2}{(1 - \phi_1^2 \rho_1 - \cdots - \phi_p^2 \rho_p)}
\end{align}
\end{array}

\begin{align}
\\
Cov[y_t,y_{t-k}] &= \gamma_k = \phi_1 \gamma_{k-1} + \cdots + \phi_p \gamma_{k-p} \hspace{2em}  (q+1 \leq k)
\\ \\
\rho_k &= \frac{\gamma_k}{\gamma_0} = \phi_1 \rho_{k-1} + \cdots + \phi_p \rho_{k-p} \hspace{2em} (q+1 \leq k) 
\end{align}


参考文献

経済・ファイナンスデータの計量時系列分析 (統計ライブラリー)

経済・ファイナンスデータの計量時系列分析 (統計ライブラリー)

Johnson and Lindenstrauss Lemmaとその構成論的証明

f:id:yumaloop:20190620010600p:plain:w500

ランダム行列理論(Random projection)の基本定理であるJohnson and Lindenstrauss Lemmaについて解説します. JL-補題は「変換前後でサンプル点どうしのユークリッド距離を変えない」ような関数  f の存在を主張しており,これは具体的にランダム行列  A を用いた線形写像として構成できます.

JL-補題

d次元空間 Q \subset {\mathbb{R}}^{d}上にある  n 個のサンプル点を考える.任意の  \epsilon \in (0,1) について,

$$ k \geq \frac{4 \log n}{ {\epsilon}^{2}/2 - {\epsilon}^{3}/{3}} $$

をみたす整数  k に対して,以下をみたす  f: \mathbb{R}^{d} \to \mathbb{R}^{k} が存在する.

$$ \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \forall u,v \in Q \subset {\mathbb{R}}^{d}, \\ (1 - \epsilon)\norm{u - v}^{2} \leq \norm{ f(u) - f(v) }^{2} \leq (1 + \epsilon) \norm{ u - v }^{2} $$

構成論的証明

写像  f: \mathbb{R}^{d} \to \mathbb{R}^{k} として, k \times d のランダム行列  A で定義される線形写像  f_Aを考える.

$$ {f}_{A}(x) = \frac{1}{\sqrt{k}} Ax \\ where~A_{ij} ~ {\scriptsize i.i.d.} \sim \mathcal{N}(0,1) $$

まず,正規分布の線形性・再生性*1より,

$$ \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \begin{eqnarray} A_{ij}(x_{j}) &\sim& \mathcal{N}\left( 0, {x_{j}}^{2} \right) \\ {\{Ax\}}_{j} &\sim& \mathcal{N}\left( 0, \norm{ x }^{2} \right) \end{eqnarray} $$

が成り立つ.正規化して変数 Z_jを定義すれば,これは標準正規分布に従う.

$$ Z_j = \frac{{\{Ax\}}_{j}}{\norm{x}} \sim \mathcal{N}\left( 0, 1 \right) $$

さらに,

$$ \norm{Ax}^{2} = \sum_{j=1}^{k} {\{Ax\}}_{j}^{2} $$

が成り立つことに注意すると,

$$ \frac{\norm{Ax}^{2}}{\norm{x}^{2}} = \sum_{j=1}^{k} \frac{{\{Ax\}}_{j}^{2}}{\norm{x}^{2}} = \sum_{j=1}^{k} {Z_j}^{2} \sim \chi_{k}^{2} $$

となる.すなわち,行列  A による線形変換の前後で,ノルムを考えるとき,これはカイ二乗分布によって評価できる.

$$ \begin{eqnarray} Pr\left( \norm{f_{A}(x)}^{2} \lt (1 + \varepsilon) \norm{x}^{2} \right) &=&Pr\left( \norm{ \frac{1}{\sqrt{k}} Ax }^{2} \lt (1 + \varepsilon) \norm{x}^{2} \right) \\ &=& Pr\left( \norm{ Ax }^{2} \gt (1 + \varepsilon) k \norm{x}^{2} \right) \\ &=& Pr\left( \frac{\norm{ Ax }^{2}}{\norm{x}^{2}} \gt (1 + \varepsilon) k \right) \\ &=& Pr\left( \sum_{j=1}^{k} {Z_j}^{2} \gt (1 + \varepsilon)k \right) \\ &=& Pr\left( \chi_{k}^{2} \geq (1 + \varepsilon)k \right) \end{eqnarray} $$

次に自由度  kカイ二乗分布  \chi_{k}^{2} を表す確率密度関数を考え,上式の右辺を上から抑えたい.

$$ p(\cdot | k) = \frac{1}{{2}^{\frac{k}{2}} \Gamma \left( \frac{k}{2} \right) } {x}^{\frac{k}{2} - 1} {e}^{- \frac{x}{2}} $$

https://upload.wikimedia.org/wikipedia/commons/thumb/3/35/Chi-square_pdf.svg/1200px-Chi-square_pdf.svg.png

ややテクニカルだが,確率密度分布から不等式を整理していく.途中で定数  \lambda \in (0, \frac{1}{2}) を導入している.

$$ \begin{eqnarray} Pr \left( \chi_{k}^{2} \geq (1 + \varepsilon)k \right) & = & Pr \left( \sum_{i=1}^{k} Z_{i}^{2} \gt (1 + \varepsilon)k \right) \\ & = & Pr \left( e^{\sum_{i=1}^{k} Z_{i}^{2}} \gt e^{(1 + \varepsilon)k} \right) \\ & = & Pr \left( e^{\lambda \sum_{i=1}^{k} Z_{i}^{2}} \gt e^{ \lambda (1 + \varepsilon)k} \right) ~~~ (0 \lt \lambda \lt \frac{1}{2}) \\ & \leq & \frac{\mathbb{E}[e^{\lambda \sum_{i=1}^{k} Z_{i}^{2}}] }{e^{(1 + \varepsilon)k \lambda}} \\ & = & \frac{{ \left( \mathbb{E}[ e^{\lambda {Z_{1}^{2}}} ] \right) }^{k}}{e^{(1 + \varepsilon)k \lambda}} \\ & = & e^{-(1 + \varepsilon) k \lambda } {\left( \frac{1}{1 - 2 \lambda} \right)}^{\frac{k}{2}} \end{eqnarray} $$

ここで, \lambda = \frac{\varepsilon}{2(1 + \varepsilon)} を代入すれば,

$$ \begin{eqnarray} Pr \left( \chi_{k}^{2} \geq (1 + \varepsilon)k \right) & = & {\left( (1 + \varepsilon)e^{- \varepsilon} \right) }^{\frac{k}{2}} \\ & \leq & \exp \left( - \frac{k}{4} ( {\varepsilon}^{2} - {\varepsilon}^{3} ) \right) \end{eqnarray} $$

が求められる.ただし.

$$ 1 + \varepsilon \leq \exp \left( \varepsilon - \frac{{\varepsilon}^{2} - {\varepsilon}^{3}}{2} \right) $$

を使った.以上をまとめると,ランダム行列  A を用いて構成される写像

$$ {f}_{A}(x) = \frac{1}{\sqrt{k}} Ax \\ where~A_{ij} ~ {\scriptsize i.i.d.} \sim \mathcal{N}(0,1) $$

に対して,

$$ \begin{eqnarray} Pr\left( \norm{f_{A}(x)}^{2} \geq (1 + \varepsilon) \norm{x}^{2} \right) & \leq & \exp \left( - \frac{k}{4} ( {\varepsilon}^{2} - {\varepsilon}^{3} ) \right) \\ Pr\left( \norm{f_{A}(x)}^{2} \leq (1 + \varepsilon) \norm{x}^{2} \right) & \geq & \exp \left( - \frac{k}{4} ( {\varepsilon}^{2} - {\varepsilon}^{3} ) \right) \end{eqnarray} $$

が成り立つ.よって,JL-補題をみたす写像  f が構成された.


参考文献

機械学習でよく使う評価指標まとめ

f:id:yumaloop:20190528210419p:plain:w600


 このポストでは,機械学習でよく使われる評価指標を,回帰・分類に分けて整理します.また,各評価指標の定義だけではなく,その性質や使用上の注意点などにも言及しました.なお,"網羅性"を過度に追求して,世にある評価指標を片っ端からリストアップすると,ポストとしての目的が分からず,何より煩雑で見づらくなってしまうと思ったので,紹介する評価指標については,重要で汎用度の高いものに絞りました.

 ※ 評価指標については随時,追加・更新していく予定です.このポストの内容には多分に不足/不備が含まれていると思われますが,些細な点でも,コメントなどにてご指摘いただけるととても嬉しいです.

1. 回帰

  • Notation
    •  N - number of data samples
    •  y \in \mathbb{R}^{N} - target vector (data set)
    •  \hat{y} \in \mathbb{R}^{N} - predicted vector (data set)
    •  y_i \in \mathbb{R} - target value (data)
    •  \hat{y}_{i} \in \mathbb{R} - predicted value (data)

1.1. MSE, RMSE, R2

  • MSE (Mean Square Error, 平均二乗誤差)

$$ MSE(\hat{y}) := \frac{1}{N}\sum_{i=1}^{N} { ( y_i - \hat{y}_{i} ) }^{2} $$

  • RMSE (Root Mean Square Error, 二乗平均平方根誤差)

$$ RMSE(\hat{y}) := \sqrt{ \frac{1}{N}\sum_{i=1}^{N} { ( y_i - \hat{y}_{i} ) }^{2} } $$

  • R2 (R-squared, 決定係数)

$$ {R^{2}}( \hat{y} ) := 1 - \frac{ \frac{1}{N} \sum_{i=1}^{N} { ( {y}_i - \hat{y}_{i} ) }^{2} }{ \frac{1}{N} \sum_{i=1}^{N} { ( {y}_i - \bar{y}) }^{2} } = 1 - \frac{M S E(\hat{y})}{Var(y)} $$

  • MSEについて
    • MSEは,回帰における最も基本的な評価指標
    • 予測値 \hat{y}の各要素を定数 \alphaで固定した場合( \hat{y}_i = \alpha),最適な定数  \alpha^{*}_{MSE} は観測データ y の平均値 \bar{y}になる. $$ \alpha^{*}_{MSE} := \bar{y} = \frac{1}{N}\sum_{i=1}^{N} y_i $$
  • MSE, RMSE, R2の相違点
    • 損失関数としての性質
      • モデルの予測値 \hat{y}に対するモデルパラメータ \thetaの最適化を考える.MSE・RMSE・R2はいずれも同じ. $$ \begin{eqnarray} MSE(\hat{y}_{\theta_1}) & > & MSE(\hat{y}_{\theta_2}) \\ \Leftrightarrow RMSE(\hat{y}_{\theta_1}) & > & RMSE(\hat{y}_{\theta_2}) \\ \Leftrightarrow \hspace{1.37em} {R^{2}}(\hat{y}_{\theta_1}) & > & {R^{2}}(\hat{y}_{\theta_2}) \end{eqnarray} $$
      • パラメータの更新に,勾配法を使う場合は注意.
        • RMSEを損失関数にした場合,MSEよりも更新幅が小さくなる. $$ \frac{\partial RMSE}{\partial \hat{y}_{i}} = \frac{1}{2 \sqrt{MSE}} \frac{\partial MSE}{\partial \hat{y}_{i}} $$
    • モデルの絶対評価を行う際は,MSEではなくR2(決定係数)がよく使われる.


1.2. MAE

  • MAE (Mean Absolute Error, 平均絶対誤差)

$$ MAE(\hat{y}) := \frac{1}{N}\sum_{i=1}^{N} \left| y_i - \hat{y}_{i} \right| $$

  • MAEについて

    • 予測値 \hat{y}の各要素を定数  \alpha で固定した場合( \hat{y}_i = \alpha),最適な定数  \alpha^{*}_{MAE}は観測データ yの中央値median(y)になる. $$ \alpha^{*}_{MAE} := median(y) $$
    • 損失関数としての性質
      • MAEを損失関数とする場合,勾配法はあまり使われない
      • 予測値  \hat{y}の各要素を定数 \alphaで固定した場合( \hat{y}_i = \alpha),
        •  \frac{\partial MAE}{\partial \hat{y}_{i}} ~ : ステップ関数 (原点では微分不可能)
        •  \frac{{\partial}^{2} MAE}{\partial {\hat{y}_{i}}^{2}} : 常に0 (原点では微分不可能)
    • MSEよりも,データに対するロバスト性が高い.
      • データに外れ値があった場合,MSEが評価する誤差は,MAEの2倍.
      • データの平均値は外れ値に影響されるが,中央値は外れ値に対して頑健.
    • MSEよりも,指標としての解釈性が高い.
  • Huber損失

    • :MSEとMAEをミックスさせた評価指標として,Huber損失*2がある.ロバスト推定やSVMの損失関数に用いられる. $$ Huber~loss := \frac{1}{N} \sum_{i=1}^{N} {L}_{\delta}(y_i, \hat{y}_{i}) \\ {L}_{\delta}(y_i, \hat{y}_{i}) = \left\{ \begin{array}{c} \frac{1}{2} {( y_{i} - \hat{y}_{i} )}^{2} \hspace{4em} ( |y_{i} - \hat{y}_{i}| \leq \delta ) \\
      \delta \cdot ( |y_{i} - \hat{y}_{i}| - \frac{1}{2}\delta) \hspace{1em} ( |y_{i} - \hat{y}_{i}| \gt \delta )
      \end{array} \right. $$
  • Quantile Regression (分位点回帰)


1.3. (R)MSPEとMAPE

  • MSPE (Mean Square Percentage Error, 平均平方二乗誤差率)

$$ MSPE(\hat{y}) := \frac{100}{N} \sum_{i=1}^{N} { \left( \frac{y_i - \hat{y}_{i} }{y_i} \right) }^{2} $$

  • MSAE (Mean Absolute Percentage Error, 平均絶対誤差率)

$$ MSAE(\hat{y}) := \frac{100}{N} \sum_{i=1}^{N} \left| \frac{y_i - \hat{y}_{i} }{y_i} \right| ~~~~~~~~ $$

  • 相対誤差と絶対誤差*4
    • 絶対誤差 =  y_i - \hat{y}_{i}
    • 相対誤差 =  (y_i - \hat{y}_{i}) ~/~ y_{i}
  • MSPEについて
    • MSEを相対誤差で評価したもの.
    • %表示(百分率)にすることが多い.
    • 例:観測値 y_iと予測値 \hat{y}_{i} N=1)が以下のような場合
      • If  ({y}_{1} = 90, ~~~ \hat{y}_{1} = 100)~~ then,  MSE=100,~~~~~MSPE=1
      • If  ({y}_{2} = 900, ~ \hat{y}_{2} = 1000) then,  MSE=10000,~MSPE=1
    • 損失関数としての性質
      • 予測値 \hat{y}の各要素を定数  \alphaで固定した場合( \hat{y}_{i} = \alpha),最適な定数  \alpha^{*}_{MSPE} は観測データ  y の重み付き平均値  w(\bar{y}) になる.
      • 値が小さいデータに対して過剰にfitしようとする.(バイアス)
  • MAPEについて
    • MAEを相対誤差で評価したもの.
    • %表示(百分率)にすることが多い.
    • 例:観測値 y_iと予測値 \hat{y}_{i} N=1)が以下のような場合
      • If  ( y_1 = 90, ~~~ \hat{y}_1 = 100)~~ then,  MAE=10,~~~MAPE=1
      • If  ( y_2 = 900, ~ \hat{y}_2 = 1000) then,  MAE=100,~MAPE=1
    • 損失関数としての性質
      • 予測値 \hat{y}の各要素を定数 \alphaで固定した場合( \hat{y}_{i} = \alpha),最適な定数  \alpha^{*}_{MAPE} は観測データ yの重み付き中央値  w(med(y))になる.
      • 値が小さいデータに対して過剰にfitしようとする.(バイアス)


1.4. RMSLE

  • RMSLE (Root Mean Square Logarithmic Error, 平均平方二乗対数誤差)

$$ \begin{eqnarray} RMSLE(\hat{y}) &:=& \sqrt{ \frac{1}{N}\sum_{i=1}^{N} { \left\{ \log(y_i + 1) - \log(\hat{y}_{i} + 1) \right\} }^{2} } \\ &=& \sqrt{ MSE(\log(y_i + 1), \log(\hat{y}_{i} + 1) ) } \end{eqnarray} $$

  • RMSLEについて
    • MSEをlogスケールで表現したもの
    • 絶対誤差を,相対誤差(MSPE, MAPE)ではなくlogスケールで表現.
       y_i の大小を考慮して誤差評価
    • 損失関数として用いる場合, \hat{y} に対して凸かつ非対称
      •  \hat{y} > 極小値 → 傾きが小さい
      •  \hat{y} < 極小値 → 傾きが大きい



2. 分類

  • Notation
    •  N - number of data samples
    •  L - number of classes
    •  y_i - ground truth (data)
    •  \hat{y}_{i} - predictions (data)
    •  y_{il} - probability that  i-th sample belongs  l-th label
    •  \hat{y}_{il} - confidence that  i-th sample belongs  l-th label
    •  [ a = b] - indicator factor
  • 混同行列 (Confusion matrix)*5
    • 二値分類(Binary classification)タスクのみに使う.
      • True Positive (TP)
        • Positiveサンプルのうち,正しくPositiveと分類されたもの
      • False Positive (FP)
        • Negativeサンプルのうち,間違ってPositiveと分類されたもの
      • False Negative (FN)
        • Positiveサンプルのうち,間違ってNegativeと分類されたもの
      • True Negative (TN)
        • Negativeサンプルのうち,正しくNegativeと分類されたもの

          f:id:yumaloop:20190601010758p:plain:w500

    • 代表的な評価指標*6
      • 正答率 (Accuracy) = (TP+TN) / (TP+FP+TN+FN)
      • 精度 (Precision) = TP / (TP+FP)
      • 検出率 (Recall) = TP / (TP+FN)
      • F値 (F-Measures) =  \frac{2}{\frac{1}{Recall}+\frac{1}{Precision}}
    • ROC曲線 (Receiver Operating Curve, 受信者操作曲線)
      • しきい値 bを変化させたときの真陽性率 (TP Rate)と偽陽性率 (FP Rate)の関係を曲線でプロットしたもの
        • 真陽性率 (TP Rate) = TP / (TP+FN) = 感度 (Sensitivity) = 検出率 (Recall)
        • 偽陽性率 (FP Rate) = FP / (FP+TN)
        • 偽陰性率 (FN Rate) = FN / (TP+FN)
        • 真陰性率 (TN Rate) = TN / (FP+TN) = 特異度 (Specificity)

参考:Pang-Ning Tan, Introduction to Data Mining (2ndEdition), Chapter 3 "Classification: Basic Concepts and Techniques"


2.1. Accuracy

  • Accuracy (正答率)

$$ Accuracy := \frac{1}{N}\sum_{i=1}^{N} [ y_i = \hat{y}_{i} ] $$

  • Error (誤り率)

$$ Error := \frac{1}{N}\sum_{i=1}^{N} [ y_i \neq \hat{y}_{i} ] $$

  • Soft prediction と Hard prediction
    • soft labels (soft predictions)
      •  f(x) \in \mathbb{R}^{L} - 分類モデル fの出力スコア
    • hard labels (hard predictions)
      •  \underset{i}{\rm argmax} ~ f_{i} (x) - 分類モデル fが最大スコアを出力したラベル
      •  \left[ b \lt f(x) \in \mathbb{R}^{L} \right],b - しきい値
  • Accuracyについて
    • Hard predictionなので,解釈が難しい.
      • 分類モデル fの出力値そのものではなくて, argmaxで評価する.
    • 損失関数として用いると,最適化が難しい.
    • best conts.  \alpha^{*}(x):最も頻度の高いクラスに固定する.
    • 例( N = 100
      • Dataset
        • 10 cats
        • 90 dogs
      •  \alpha^{*}(x) = "dogs"


2.2. LogLoss

  • Binary LogLoss

$$ Losloss := - \frac{1}{N}\sum_{i=1}^{N} \left\{ y_i \log \hat{y}_{i} + (1 - y_i) \log (1 - \hat{y}_i) \right\}, ~~ y_i, \hat{y}_{i} \in \mathbb{R} $$

  • Multiclass LogLoss

$$ Logloss := - \frac{1}{N} \sum_{i=1}^{N} \sum_{l=1}^{L} y_{il} \log \hat{y}_{il}, ~~ y_i, \hat{y}_{i} \in \mathbb{R}^{L} $$

  • LogLoss (Logarithmic loss)について
    • Soft prediction.
    • 損失関数として用いると,最適化が簡単.
    • best conts.  \alpha^{*}_{i}(x):i-th クラスの頻度(経験分布)
    • 例( N = 100
      • Dataset
        • 10 cats
        • 90 dogs
      •  \alpha^{*}(x) = [0.1, 0.9 ]

2.3. AUC (ROC)

  • AUC (Area Under Roc)

 AUC := Area under the ROC Curve

  • AUC (ROC) について
    • AUC*7は,二値分類(Binary classification)タスクのみに使う
    • サンプルに対する識別結果の"順序"にのみ依存,分類モデルの"出力値"には非依存.
    • best consts.  \alpha^{*}_{i}(x):任意の定数に固定してもAUCの値は同じ.
    • AUCの説明
      • ROC(Receiver Operating Curve)曲線の下側面積
        • Wilcoxon-Mann-Whitney検定 (WMW検定)
        • Brunner-Munzel検定
      • サンプルペアの順序
        • 正しい順序に分類されたサンプルペアの割合
        •  AUC := \frac{correctly~orderd~pairs}{total~number~of~pairs}
    • pythonの場合,sklearn.metrics.roc_curve()sklearn.metrics.auc()を使って計算できる.

2.4. Cohen’s Kappa

  • Cohen’s Kappa ( \kappa係数,  \kappa統計量)

$$ Kappa := 1 - \frac{1 - accuracy}{1 - p_{e}} = 1 - \frac{error}{baseline~error} $$ $$ p_{e} := \frac{1}{N^{2}} \sum_{k} n_{k1} n_{k2} $$

     ・  i - 評価者

     ・  k - 識別するクラス

     ・  n_{ki} - 評価者 iがクラス kであると識別したサンプルの数

     ・  N - サンプルの数

     ・  p_{e} - 各サンプルをランダムに識別した場合の平均正答率


  • Weighted Kappa (重み付けカッパ係数)

$$ Weighted~Kappa := 1 - \frac{weighted~error}{weighted~baseline~error} $$ $$ weighted~error := \frac{1}{Z} \sum_{i,j} c_{ij} w_{ij} $$

     ・  c_{ij} - 混同行列 C (i, j)成分

     ・  w_{ij} - 重み行列 W (i, j)成分

     ・  Z - 規格化定数

  • Cohen's Kappa について
    • Jacob Cohenが1960年に発表.
    • 基準となるスコア(baseline)を0に正規化して,任意のモデルの性能を表現.
      • 「Kappa - Accuracy の関係性」は,「R2 - MSE の関係性」に似ている.
  • Weighted Kappaについて
    • Accuracy(Error)に重みづけを行ってKappaを計算.
      •  weighted~error := \frac{1}{Z} \sum_{i,j} c_{ij} w_{ij}
      •  c_{ij}:混同行列 C \in \mathbb{R}^{L \times L} (i, j)成分 ※ L - 識別するクラス数
      •  w_{ij}:重み行列 W \in \mathbb{R}^{L \times L} (i, j)成分 ※ L - 識別するクラス数
    • 混同行列 C
      • TP, FP, FN, FP
    • 重み行列 W
      • "順序つき"クラスラベルの分類に使う.
      • 例:病気のレベルに応じたクラス分類
    • 重み行列 Wの構成法
      • Linear weights: w_{ij} = |i - j|
      • Quadratic weights: w_{ij} = {(i - j)}^{2}
    • Quadratic Weighted Kappaを損失関数に使う場合,典型的には,MSEで近似する*8
    • 例( N = 100
      • Dataset
        • 10 cats
        • 90 dogs
        • 20 tigers

*1:線形回帰モデルにのみ適用可能

*2:Huber, Peter J. (1964). “Robust Estimation of a Location Parameter”. Annals of Statistics 53 (1): 73–101. doi:10.1214/aoms/1177703732. JSTOR 2238020.

*3:"QUANTILE REGRESSION", Roger Koenker, http://www.econ.uiuc.edu/~roger/research/rq/rq.pdf

*4:参考:相対誤差の計算方法と意義

*5:参考:Understanding Confusion Matrix - Towards Data Science

*6:参考:Accuracy, Precision, Recall or F1? - Towards Data Science

*7:奥村先生によるAUC (ROC)の解説ページ:https://oku.edu.mie-u.ac.jp/~okumura/stat/ROC.html

*8:解析的に解く方法もある."On The Direct Maximization of Quadratic Weighted Kappa"

Markdownエディタ "Typora" の紹介とショートカット [macOS Mojave 10.14.4]

Typoraの紹介

Typoraは,高機能&シンプルなMarkdownエディタです.最大の特徴は,Markdownコードを書くと,エディタ上で即座にレンダリングされ,インタラクティブにプレビューが表示されることです.Markdownで表や数式をよく書く場合,この機能は思った以上に有用で,簡単なメモをサクッと書くときに便利です.また,PDFへのエクスポート機能も優秀で,Pandocで煩雑な設定をする必要なくドキュメントを印刷できます.

f:id:yumaloop:20190528120527p:plain:w600



ダウンロード

Typoraのインストーラ(.dmg)は,以下のURLからダウンロードできます.Macにダウンロードする場合は,画面下にある「Download Beta (OS X)」ボタンをクリックすればOKです.

https://typora.io/

f:id:yumaloop:20190528121014p:plain:w600


Typoraの詳しい紹介/解説としては,

qiita.com

qiita.com

などがありますが,Mac OS向けのショートカットがなかったので,このポストに載せておきます.


ショートカット (Mac OS)

macOSで動作するショートカットです.※ Typora OS X版 (β 0.9.9.24.6)

  • カーソル操作
    ショートカット 処理
    Command + / 編集モードを切替
    Command + D 単語を選択
    Command + F 単語を検索
    Command + shift + D 単語を削除
    Command + L 行を選択
    Command + enter 行を追加
    Command + E スコープ/セルを選択
    Command + J 次章にジャンプ
    Command + {↑, ↓} ファイルの最上行/最下行にジャンプ
    Command + {=, -} 見出しレベル(<p>から<h1>まで)を上下
    Command + ^ + {↑, ↓, ←, →} 表のセル内を移動
  • フォーマットの挿入
    ショートカット 処理
    Command + {1~5} 見出しh1~h5を挿入
    Command + {=, -} 見出しレベルをする
    Command + I 斜体**を挿入
    Command + B 太字****を挿入
    Command + U 下線<u></u>を挿入
    Command + K ハイパーリンク[](url)を挿入
    Command + option + L リンク[]: urlを挿入
    Command + option + Q 引用符>を挿入
    Command + option + B 数式ブロックを挿入
    Command + option + C コードブロックを挿入
    Command + option + T 表を挿入
    Command + control + I 画像![]を挿入
    [toc] 目次を挿入
    $$ 数式を挿入
  • ファイル操作
    ショートカット 処理
    Command + N 新しいファイルを開く
    Command + T 新しいタブを開く
    Command + shift + N 新しいウィンドウを開く
    Command + O 既存のファイルを選択して開く
    Command + W 現在のウィンドウを閉じる
    Command + S 現在のファイルを保存する
    Command + shit + L ファイル内のアウトラインを表示
    Command + shift + O ファイル名で検索


ショートカットの表をMarkdownファイルにコピペしたい方のために,生のmarkdownスクリプトを載せておきます!どうぞ.

# Short cut (MacOS)

- カーソル操作

  | ショートカット             | 処理                                      |
  | -------------------------- | ----------------------------------------- |
  | Command + /                | 編集モードを切替                          |
  | Command + D                | 単語を選択                                |
  | Command + F                | 単語を検索                                |
  | Command + shift + D        | 単語を削除                                |
  | Command + L                | 行を選択                                  |
  | Command + enter            | 行を追加                                  |
  | Command + E                | スコープ/セルを選択                       |
  | Command + J                | 次章にジャンプ                            |
  | Command + {↑, ↓}           | ファイルの最上行/最下行にジャンプ         |
  | Command + {=, -}           | 見出しレベル(`<p>`から`<h1>`まで)を上下 |
  | Command + ^ + {↑, ↓, ←, →} | 表のセル内を移動                          |

- フォーマットの挿入

  | ショートカット        | 処理                          |
  | --------------------- | ----------------------------- |
  | Command + {1~5}       | 見出し`h1~h5`を挿入           |
  | Command + {=, -}      | 見出しレベルをする            |
  | Command + I           | 斜体`**`を挿入                |
  | Command + B           | 太字`****`を挿入              |
  | Command + U           | 下線`<u></u>`を挿入           |
  | Command + K           | ハイパーリンク`[](url)`を挿入 |
  | Command + option + L  | リンク`[]: url`を挿入         |
  | Command + option + Q  | 引用符`>`を挿入               |
  | Command + option + B  | 数式ブロックを挿入            |
  | Command + option + C  | コードブロックを挿入          |
  | Command + option + T  | 表を挿入                      |
  | Command + control + I | 画像`![]`を挿入               |
  | [toc]                 | 目次を挿入                    |
  | $$                    | 数式を挿入                    |

- ファイル操作

  | ショートカット      | 処理                           |
  | ------------------- | ------------------------------ |
  | Command + N         | 新しいファイルを開く           |
  | Command + T         | 新しいタブを開く               |
  | Command + shift + N | 新しいウィンドウを開く         |
  | Command + O         | 既存のファイルを選択して開く   |
  | Command + W         | 現在のウィンドウを閉じる       |
  | Command + S         | 現在のファイルを保存する       |
  | Command + shit + L  | ファイル内のアウトラインを表示 |
  | Command + shift + O | ファイル名で検索               |

Donsker-Varadhan representation(DV下限)

定理(DV表現)

連続確率変数  X に対して,確率密度関数  q(x), p(x) が定義されているとき,以下の関係式が成り立ちます.この式を,Donsker-Varadhan representation*1といい,右辺をDV下限と言います.

$$ \mathbb{D}_{KL}(q || p) = \underset{T: X \to \mathbb{R} }{\rm sup} ~ \mathbb{E}_{q} [T(x)] - \log \left( \mathbb{E}_{p} [ {e}^{T(x)} ] \right) $$

この関係式は,任意の実関数  T による近似で,KL情報量に下限を与えられることを保証しており,かつ一致解の存在を示しています.以下で,簡単な証明を記します.

証明

まず,確率密度  q(x) に対して,近似分布  g(x) を考えます. 近似分布  g(x)は,確率密度 p(x) T(x) をエネルギー関数とみたときのギブス分布*2によって導かれます. 関数  T: X \to \mathbb{R} は任意の実関数*3です.

$$ g(x) = \frac{{e}^{T(x)}}{ \mathbb{E}_{p}[{e}^{T(x)}] } \cdot p(x) \\ \\ $$

次に, q(x) に対する, p(x) g(x) の擬距離(KL情報量)を考えます.

$$ \begin{eqnarray} \mathbb{D}_{KL}(q || p) &=& \mathbb{E}_{q} \left[ \log \frac{q(x)}{p(x)} \right] \\ \mathbb{D}_{KL}(q || g) &=& \mathbb{E}_{q} \left[ \log \frac{q(x)}{g(x)} \right] \\ \end{eqnarray} $$

これらの差を計算すると.

$$ \begin{eqnarray} \mathbb{D}_{KL}(q || p) - \mathbb{D}_{KL}(q || g) &=& \mathbb{E}_{q} \left[ \log \frac{g(x)}{p(x)} \right] \\ &=& \mathbb{E}_{q} \left[ \log \frac{\frac{{e}^{T(x)}}{\mathbb{E}_{p}[{e}^{T(x)}]} \cdot p(x)}{p(x)} \right] \\ &=& \mathbb{E}_{q} \left[ \log \frac{{e}^{T(x)}}{\mathbb{E}_{p}[{e}^{T(x)}]} \right] \\ &=& \mathbb{E}_{q} [T(x)] - \log \left( \mathbb{E}_{p} [ {e}^{T(x)} ] \right) &\geq& 0 \end{eqnarray} $$

となり,DV下限が導出されました.つまり,ある関数  Tを用いてDV下限を計算したとき,

$$ \mathbb{D}_{KL}(q || p) = (DV下限) + \mathbb{D}_{KL}(q || g) $$

が成り立つので,誤差項  \mathbb{D}_{KL}(q || g) を考慮すれば,KL情報量  \mathbb{D}_{KL}(q || p) はDV下限で下から計ることができます.

*1:Donsker, M. and Varadhan, S. Asymptotic evaluation of certain markov process expectations for large time, iv. Communications on Pure and Applied Mathematics, 36(2):183?212, 1983.

*2:ボルツマン分布とも呼ばれる. 朱鷺の杜Wiki - "Bolzmann分布"

*3:厳密には,値が発散しないことなどが条件になる.

Numpyでカーネル回帰

f:id:yumaloop:20190426185334p:plain:w500

 カーネル法は,非線形データ解析に対する強力な武器です.ソフトマージンSVMガウス過程・クラスタリングなどのアルゴリズムの基本要素として頻出します.このポストでは,カーネル法を使って回帰問題を解く手続きを,Pythonで再現してみました.

 ※ なお,カーネル法に関する知識は,以下の本を参考にしています.

カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)

カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)


カーネル回帰とは?

カーネル関数とグラム行列

 n 個のデータサンプル  \mathcal{D} = \left\{ x^{(i)}, y^{(i)} \right\} \, (i=1, \cdots n) から,関数  y = f(x)を近似します.回帰モデルはカーネル関数 kとパラメータ {\alpha}_i \, (i=1 \cdots n) を用いて以下の式で表されます.

$$ \hat{y}^{(i)} = \sum_{j=1}^{n} \alpha_j k(x^{(i)}, x^{(j)}) \,\,\, i=1 \cdots n $$

推定値 \hat{y}^{(i)}と真値  y^{(i)} の間の距離を残差(residual)として計算します.データサンプルにモデルをfitさせて,残差の合計(あるいは平均)をモデルの損失関数として導出し,最適なパラメータ  {\alpha}_i \, (i=1 \cdots n) を求めます.

$$ \begin{align} residual(y^{(i)}, \hat{y}^{(i)}) &= y^{(i)} - \hat{y}^{(i)} \\ &= y^{(i)} - \sum_{j=1}^{n} \alpha_j k(x^{(i)}, x^{(j)}) \end{align} $$

$$ \begin{align} L(\alpha) &= \frac{1}{n} \sum_{i=1}^{n} {residual(y^{(i)}, \hat{y}^{(i)}) }^{2} \\ &= \frac{1}{n} \sum_{i=1}^{n} { \left( y^{(i)} - \sum_{j=1}^{n} \alpha_j k(x^{(i)}, x^{(j)}) \right) }^{2} \\ &= {({\bf y} - {\bf K} {\bf \alpha})}^{\mathrm{T}} ({\bf y} - {\bf K} {\bf \alpha}) \end{align} $$

$$ where, \,\,\, {\bf K} = \begin{pmatrix} k(x^{(1)}, x^{(1)}) & \cdots & k(x^{(1)}, x^{(n)}) \\ \vdots & \ddots & \vdots \\ k(x^{(n)}, x^{(1)}) & \cdots & k(x^{(n)}, x^{(n)}) \end{pmatrix} $$

 {\bf K}カーネル関数を与えるとデータサンプルから計算させる行列で,Gram行列と呼びます.

勾配降下法でパラメータ探索

パラメータ {\alpha}_i  \, (i=1 \cdots n) の探索には,ナイーブな勾配降下法を使います.係数  \gamma は学習率です.

$$ \frac{\partial L(\alpha)}{\partial {\bf \alpha}} = -2 \cdot {\bf K}^{\mathrm{T}} ({\bf y} - {\bf K} {\bf \alpha}) \\ {\alpha}_{new} = {\alpha}_{old} + \gamma \cdot \frac{\partial L(\alpha)}{\partial {\bf \alpha}} \mid_{ \alpha = {\alpha}_{old} } $$

カーネル関数としては,RBF kernel(Gaussian kernel)を使う.


    k(x, x') := \exp \left( {\large - \frac{{|| x - x' ||}^2}{2 {\sigma}^{2}} } \right)



カーネル回帰をPythonで実装 (numpy only)

コードは全て下記のリポジトリにあります. github.com

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

# Kernel Function
class RBFkernel():
    def __init__(self, sigma=0.5):
        self.sigma = sigma
        
    def __call__(self, x, y):
        numerator = -1 * np.sum((x - y)**2)
        denominator = 2 * (self.sigma**2)
        return np.exp(numerator / denominator)
    
    def get_params(self):
        return self.sigma
    
    def set_params(self, sigma):
        self.sigma = sigma

# Regression Model
class KernelRegression():
    def __init__(self, kernel):
        self.kernel = kernel
        
    def fit_kernel(self, X, y, lr=0.01, nb_epoch=1000, log_freq=50):
        self.X = X
        self.y = y
        self.n = X.shape[0] # sample size
        self.alpha = np.full(self.n, 1) # param alpha: initialize
        self.gram_matrix = np.zeros((self.n, self.n))
        
        # Gradient Descent Algorithm to optimize alpha
        for epoch in range(nb_epoch):
            
            # Gram Matrix
            for i in range(self.n):
                for j in range(self.n):
                    self.gram_matrix[i][j] = self.kernel(self.X[i], self.X[j])
                    self.loss, self.loss_grad = self.mse(self.X, self.y, self.alpha, self.gram_matrix)
                    self.alpha = self.alpha - lr * self.loss_grad
                    
            if epoch % log_freq == 0:
                print("epoch: {} \t MSE of sample data: {:.4f}".format(epoch, self.loss))
                        
                        
    def mse(self, X, y, alpha, gram_matrix):
        loss = np.dot((y - np.dot(gram_matrix, alpha)), (y - np.dot(gram_matrix, alpha)))
        loss_grad = -2 * np.dot(gram_matrix.T, (y - np.dot(gram_matrix, alpha)))
        return loss, loss_grad
    
    def predict(self, X_new):
        n_new = X_new.shape[0]
        y_new = np.zeros(n_new)
        for i in range(n_new):
            for j in range(self.n):
                y_new[i] += self.alpha[j] * self.kernel(X_new[i], self.X[j])
        return y_new
# Experiment

def actual_function(x):
    return 1.7 * np.sin(2 * x) + np.cos(1.5 * x) + 0.5 * np.cos(0.5 * x) + 0.5 * x  + 0.1

sample_size = 100 # the number of data sample
var_noise = 0.7 # variance of the gaussian noise for samples

# make data sample
x_sample = np.random.rand(sample_size) * 10 - 5
y_sample = actual_function(x_sample) + np.random.normal(0, var_noise, sample_size)

# variables for plot (actual function)
x_plot = np.linspace(-5, 5, 100)
y_plot = actual_function(x_plot)

# plot figure
plt.plot(x_plot, y_plot, color="blue", linestyle="dotted", label="actual function")
plt.scatter(x_sample, y_sample, alpha=0.4, color="blue", label="data sample")
plt.title("Actual function & Data sample (N={})".format(sample_size))
plt.legend(loc="upper left")
plt.xlabel("x")
plt.ylabel("y")
plt.show()
f:id:yumaloop:20190426184220p:plain:w500
# set kernel
sigma=0.2
kernel = RBFkernel(sigma=sigma)

# generate model
model = KernelRegression(kernel)

# fit data sample for the model
model.fit_kernel(x_sample, y_sample, lr=0.01, nb_epoch=1000, log_freq=100)
  epoch: 0      MSE of sample data: 35.2988
  epoch: 100    MSE of sample data: 30.3570
  epoch: 200    MSE of sample data: 29.4241
  epoch: 300    MSE of sample data: 28.8972
  epoch: 400    MSE of sample data: 28.5597
  epoch: 500    MSE of sample data: 28.3322
  epoch: 600    MSE of sample data: 28.1736
  epoch: 700    MSE of sample data: 28.0598
  epoch: 800    MSE of sample data: 27.9759
  epoch: 900    MSE of sample data: 27.9122

# check Gram Matrix of the model
print(model.gram_matrix)
  array([[1.00000000e+000, 3.24082380e-012, 1.86291046e-092, ...,
        3.45570112e-030, 7.50777061e-016, 6.18611768e-129],
       [3.24082380e-012, 1.00000000e+000, 5.11649994e-039, ...,
        1.78993799e-078, 1.05138357e-053, 1.15421467e-063],
       [1.86291046e-092, 5.11649994e-039, 1.00000000e+000, ...,
        6.88153992e-226, 4.47677881e-182, 8.98951607e-004],
       ...,
       [3.45570112e-030, 1.78993799e-078, 6.88153992e-226, ...,
        1.00000000e+000, 4.28581263e-003, 2.58161981e-281],
       [7.50777061e-016, 1.05138357e-053, 4.47677881e-182, ...,
        4.28581263e-003, 1.00000000e+000, 3.95135557e-232],
       [6.18611768e-129, 1.15421467e-063, 8.98951607e-004, ...,
        2.58161981e-281, 3.95135557e-232, 1.00000000e+000]])

# check loss
print(model.loss)
  12.333081499130776

# array for plot (predicted function)
x_new = np.linspace(-5, 5, 100)
y_new = model.predict(x_new)

 plot result
plt.plot(x_plot, y_plot, color="blue", linestyle="dotted", label="actual function")
plt.scatter(x_sample, y_sample, alpha=0.3, color="blue", label="data sample")
plt.plot(x_new, y_new, color="red", label="predicted function")
plt.title("Kernel Regression \n RBF kernel (sigma={}), sample size ={}".format(sigma, sample_size))
plt.legend(loc="upper left")
plt.xlabel("x")
plt.ylabel("y")
plt.show()
f:id:yumaloop:20190426185334p:plain:w500