デジタル・デザイン・ラボラトリーな日々

アラフィフプログラマーが数学と物理と英語を基礎からやり直す。https://qiita.com/yaju

サポートベクターマシーン(SVM)を理解してみる

はじめに

ディープラーニング(深層学習)の理解もまだ進んでいないわけですが、今回は勝手に古い技術と思い込み何も理解しようとすらしていなかった サポートベクターマシン(Support Vector MachineSVM)に着目してみます。

サポートベクターマシンとは

サポートベクターマシン(Support Vector MachineSVM)は、1995年頃にAT&TV.Vapnik(ウラジミール・ヴァプニーク(Vladimir Vapnik;1936-))が発表したパターン識別用の教師あり機械学習方法であり、局所解収束の問題が無い長所がある。「マージン最大化」というアイデア等で汎化能力も高め、現在知られている方法としては、最も優秀なパターン識別能力を持つとされている。
参照:サポートベクターマシン(SVM)

機械学習には大きく分けて「識別関数」「識別モデル」「生成モデル」の3つの種類があります。このなかで識別関数が確率を使わないので初心者が入門するのに最適です。

識別問題には線形分離可能と線形分離不可能がある。
f:id:Yaju3D:20180901022342p:plain

パーセプトロンという基礎的な識別関数の学習手法は、誤差関数の勾配を利用してどんどん誤差関数を小さくしていくというものであるが、この手法には下記の2点の課題がある。

  • モデルの汎化能力が保証されない。
  • 線形分離可能な問題で利用できない。

SVMは2クラスの分類を行うための機械学習の手法で、大雑把に言うとパーセプトロンという基礎的な識別関数に「マージン最大化」と「カーネル関数」という考え方を導入して上記の課題に対応したものである。

マージン最大化

学習データの中で最も他クラス と近い位置にいるもの(サポー トベクタ)を基準として、その ユークリッド距離が最大になる ように識別面を決める。

汎化能力とは学習時に与えられた訓練データだけに対してだけでなく、未知の新たなデータに対するクラスラベルや関数値も正しく予測できる能力のことを指す。 そもそも、単純パーセプトロンのような機械学習を利用する目的は、スパムメールの例であれば、学習では使っていないメールでも上手くスパムかどうかを分類することである。 決して、以前にきたことのあるメールだけを分類すればいいというわけではない。

qiita.com

カーネルトリック

カーネルトリックとは、元々のデータ空間から高次元空間にデータを写像し、その高次元空間上で線形データ解析を行うことを指す。

ソフトマージンで線形分離不可能な場合でも、分離超平面を決定することができますが、 所詮線形分離なので、性能には限界があります。 カーネルトリックはその限界を取り払い、SVMが注目されるきっかけを作った手法です。

SVMの利点・欠点

参照:SVMってなに?

利点

  • データの特徴の次元が大きくなっても識別精度が良い
  • 最適化すべきパラメータが少ない
  • パラメータの算出が容易

欠点

  • 学習データが増えると計算量が膨大になる (「次元の呪い」の影響が顕著)
  • 基本的には2クラスの分類にしか使えない

線形SVN

線形SVNは「ハードマージン」と「ソフトマージン」に分けられます。

ハードマージン

SVMパターン認識手法の一種です。 ハードマージンSVMはその中でも一番基本となるものです。

shogo82148.github.io

ソフトマージン

線形分離不可能(直線では分けられない場合)にはうまく行きません。 それを解決するのがソフトマージンSVMです。
ソフトマージンSVMは、データにノイズが混じっている場合にもある程度強いという特徴があります。

shogo82148.github.io

参照

d.hatena.ne.jp d.hatena.ne.jp d.hatena.ne.jp

Google Colaboratory上でmatplotlibのアニメーションを再生する

はじめに

最近は、Anacodaを使わずにGoogle Colaboratoryを使用しています。
Google ChromでGoogle Colaboratory にアクセスすれば、すぐにPythonが使えますからね。

下記サイトでは勾配降下法 (Gradient Descent)のグラフをアニメーション化しており、かっこいいです。
sinhrks.hatenablog.com

Google Colaboratory でPython 3に変更して動かして見たのですが、アニメーションは動きませんでした。

アニメーション

下記サイトを参考に Jupyter notebookと同じようにmatplotlibのnbagg を有効にしてみたりしたのですが、駄目でした。 qiita.com

ネットの検索条件「Google Colaboratory animation」と英語化して、見つけたのが下記サイトとなります。 medium.com

技術的なことは、下記サイトが参考になります。
「JupiterにMatplotlibアニメーションをインタラクティブJavaScriptウィジェットとして埋め込む」
louistiao.me

下記プログラムをGoogle Colaboratoryに貼り付けると、アニメーションが表示されます。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import animation, rc
from IPython.display import HTML
# animate over some set of x, y
x = np.linspace(-4, 4, 100)
y = np.sin(x)
# First set up the figure, the axes, and the plot element
fig, ax = plt.subplots()
plt.close()
ax.set_xlim(( -4, 4))
ax.set_ylim((-2, 2))
line1, = ax.plot([], [], lw=2)
line2, = ax.plot([], [], lw=2)
# initialization function: plot the background of each frame
def init():
    line1.set_data(x, y)      
    return (line1,)
# animation function: this is called sequentially
def animate(i):
  at_x = x[i]
  
  # gradient_line will have the form m*x + b
  m = np.cos(at_x)
  b = np.sin(at_x) - np.cos(at_x)*at_x
  gradient_line = m*x + b
  
  line2.set_data(x, gradient_line)
  return (line2,)
anim = animation.FuncAnimation(fig, animate, init_func=init, frames=100, interval=100, blit=True)
rc('animation', html='jshtml')
anim

f:id:Yaju3D:20180731234424g:plain

アニメーションの保存

下記サイトを見つけました。 qiita.com

Google Colaboratory上ではどうすれば出来るのかを検討したところ、mp4形式なら出来ることが分かりました。 参照:Sum approximation

準備として、ffmpeg をインストールする必要があります。

# To make an animation, we need ffmpeg
!apt-get update && apt-get install ffmpeg

先程のプログラムの下側にあるコードを変更します。

anim = animation.FuncAnimation(fig, animate, init_func=init, frames=100, interval=100, blit=True)

# add code
plt.rcParams['animation.ffmpeg_path'] = '/usr/bin/ffmpeg' # For google colab
HTML(ani.to_html5_video())

#rc('animation', html='jshtml')
#anim

表示された動画にある「︙」をクリックすれば、ダウンロード出来ます。
※下図はキャプチャした静止画です。
f:id:Yaju3D:20180812130117p:plain

Twitterは動画形式のmp4対応しているので、ツイートする分には問題ありません。
どうしてもgifにしたい場合には、オンライン上でmp4からgifに変換できます。
www.aconvert.com

gif保存には調査が必要

上記方法より先にgif形式を試したのですが、PillowWriterでインポートエラーになりました。
もしかしたら出来る方法があるかも知れませんが、追求はやめました。

from matplotlib.animation import PillowWriter

anim = animation.FuncAnimation(fig, animate, init_func=init, frames=100, interval=100, blit=True)
anim.save("gradientline.gif", writer=PillowWriter(fps=60))

#ImportError: cannot import name 'PillowWriter'

最後に

後で、勾配降下法 (Gradient Descent)のグラフをアニメーション化して公開する予定です。
今回は紹介まで。

【2018/05/01】アニメーション化しました。 qiita.com

Google ColaboratoryでGitHubのCSVデータをpandasに読み込む

はじめに

最近は、Anacodaを使わずにGoogle Colaboratoryを使用しています。
Google ChromでGoogle Colaboratory にアクセスすれば、すぐにPythonが使えますからね。

機械学習を学ぶ上では、サクッと使えるデータが必要です。

Google Colaboratoryでファイルの入出力

Google Colaboratoryでファイルの入出力については、ローカルファイルへアップロードしたり、google driveを使用する方法があります。
それらについては下記サイトを参考にするといいでしょう。 web.archive.org qiita.com

Web上からCSVデータの読み込み

ローカルファイルへアップロードしたり、google driveを使用することすら面倒くさいと思っていて、既にWeb上に置いてあるデータをそのまま使えれば楽ちんだよね。
下記サイトを参考にしたら、統計表一覧 政府統計の総合窓口 GL08020103 のcsvデータが読めました。 blog.neko-ni-naritai.com

import pandas as pd
import urllib.request
from io import StringIO

url = "http://www.e-stat.go.jp/SG1/estat/Csvdl.do?sinfid=000012460662"

#csvを読み込む関数
def read_csv(url):
    print(url)
    res = urllib.request.urlopen(url)
    res = res.read().decode('shift_jisx0213')
    df = pd.read_csv(StringIO( res) )
    return df

#実行
read_csv(url)

f:id:Yaju3D:20180630115212p:plain

では、誰かがあげてあるGitHubのデータも使えるんじゃないかと、機械学習の初心者が学ぶ際に使用する有名なデータのアヤメ(iris)を検索して一番最初に出てきたのを使用しました。
https://github.com/pandas-dev/pandas/blob/master/pandas/tests/data/iris.csv

先程のプログラムのURLを書き換えただけだと、「ParserError: Error tokenizing data. 」となりました。

url = "https://github.com/pandas-dev/pandas/blob/master/pandas/tests/data/iris.csv"

下記記事は、R言語ですがPyhtonでも似たようなものだろうと、Raw つまり データだけが表示されるページにアクセスすればいいようです。 web.archive.org

先程のgithubのサイトに「Raw」ボタンがあったので、そこをクリックした際のURLに書き換えます。また、デコードをSJISからUTF-8に変更します。

import pandas as pd
import urllib.request
from io import StringIO

url = "https://raw.githubusercontent.com/pandas-dev/pandas/master/pandas/tests/data/iris.csv"

#csvを読み込む関数
def read_csv(url):
    print(url)
    res = urllib.request.urlopen(url)
    res = res.read().decode("utf-8")
    df = pd.read_csv(StringIO( res) )
    return df

#実行
read_csv(url)

f:id:Yaju3D:20180630121137p:plain

最後に

自分は面倒くさがり屋です、この「面倒くさがり屋」とはプログラマの三大美徳である「怠惰」「短気」「傲慢」の「怠惰」に匹敵する言葉だったりします。
機械学習を学ぶ上で少しでも敷居を下げれればと思います。

ディープラーニング(深層学習)を理解してみる(識別問題 その2)

はじめに

3月の問題が解決しないまま2ヶ月が経ってしまい、4月分はうっかり記事を飛ばしてしまった。
このままだと5月分の記事も飛ばしてしまうので、あとで埋めるために5月分の記事を立てた。

しばしお待ち下さい。

ディープラーニング(深層学習)を理解してみる(識別問題)

はじめに

前々回の「対数logを理解してみる」と前回の「自然対数の底(ネイピア数) e を理解してみる」では、人工知能に使用する基礎的な数学知識が足りなかったのでシリーズとは脱線して書いてみました。 また、このシリーズで書いていきます。

ニューラルネットワークは、回帰問題と分類問題があります。
これまでやってきたリンゴとミカンの値段を予測するというのが回帰問題で、今回やるのは分類問題(識別問題)となります。

以前フレームワークのTensorFlowを使用してやりましたが、今回はフレームワークを使用しないでやってみます。
yaju3d.hatenablog.jp

識別問題とは

入力データから判断して分類させる問題。今回の例では買えるのか買えないのかを判断させる。 識別分類器としてロジスティック回帰を使う。

ロジスティック回帰とは

ロジスティック回帰は、発生確率を予測する手法です。 基本的な考え方は線形回帰分析と同じなのですが、予測結果が 0 から 1 の間を取るように数式やその前提に改良が加えられています。 今回のように購入有無(買える or 買えない)の2値しかとりえない値を従属変数の実績値として用い、説明変数を用いてその発生確率を説明するという構造になっています。

例題

たかしくんは八百屋へ財布を預かってお使いに行きました。
しかし、たかしくんはお金を 数えられません。

気まぐれおやじ曰く、
リンゴ2個+ミカン3個、リンゴ0個+ミカン16個 なら買えるが、リンゴ3個+ミカン1個、 リンゴ2個+ミカン8個は買えないとのこと。

リンゴ1個+ミカン11個は買えますか? → 識別問題 f:id:Yaju3D:20160421011949p:plain

式で表そうとしてみる…
f:id:Yaju3D:20160421012015p:plain f:id:Yaju3D:20160421012037p:plain

シグモイド曲線

f:id:Yaju3D:20160421012100p:plain
※シグモイド曲線とは、入力した値を0から1の間に収めてくれる関数の1つ
 多くの自然界に存在する事柄は、このようなS字曲線を取る。
 生物の神経細胞、細胞の生存率曲線などなど

予測式(モデル)が作れた!
f:id:Yaju3D:20160421012204p:plain

ロジスティック回帰
f:id:Yaju3D:20160421012219p:plain

プログラム

import numpy as np
import pandas as pd

def p_y_given_x(x, w, b):
    # x, w, b から y の予測値 (yhat) を計算
    def sigmoid(a):
        return 1.0 / (1.0 + np.exp(-a))
    return sigmoid(np.dot(x, w) + b)

def grad(x, y, w, b):
    # 現予測値から勾配を計算
    error = y - p_y_given_x(x, w, b)
    w_grad = -np.mean(x.T * error, axis=1)
    b_grad = -np.mean(error)
    return w_grad, b_grad
  
def gd(x, y, w, b, eta=0.1, num=1000):
    for i in range(1, num):
        # 入力をまとめて処理
        w_grad, b_grad = grad(x, y, w, b)
        w -= eta * w_grad
        b -= eta * b_grad
        e = np.mean(np.abs(y - p_y_given_x(x, w, b)))
        yield i, w, b, e

x = np.array([[2., 3.], [0., 16.], [3., 1.], [2., 8.]])
y = np.array([1., 1., 0., 0.])

# w, b の初期値を作成
w = [-10,-10]
b = 200
gen = gd(x, y, w, b)

for i, w, b, e in gen:
  if (i+1) % 100 == 0:
    print(i+1,b,w,e);

実行結果

100 196.2993226598431 [-22.375      -12.28583744] 0.6420233463035018
200 192.7195561228789 [-34.875      -12.06210203] 0.6420233463023709
300 189.1722948623358 [-47.25687076 -11.79079916] 0.48881302062549137
400 186.7724229463934 [-55.05210822 -11.5078109 ] 0.2665264782982885
500 185.57859640809747 [-58.91482296 -11.29546188] 0.02159297746827703
600 185.4754835638496 [-59.25851476 -11.22680836] 0.007859710540613895
700 185.42589243161035 [-59.4240343  -11.19266882] 0.004766951474845803
800 185.39307584996868 [-59.53360836 -11.16986379] 0.003414942999345553
900 185.36853902132037 [-59.61555193 -11.15273521] 0.002658633400582877
1000 185.34894411228476 [-59.68099871 -11.13901984] 0.002175879579138274

TensorFlowで実行した結果とほぼ同じになっています。
f:id:Yaju3D:20160421012400p:plain

予測結果

0.95848435 ≒ 0.96 f:id:Yaju3D:20160424232047p:plain

自然対数の底(ネイピア数) e を理解してみる

はじめに

前回、対数を理解してみました。 yaju3d.hatenablog.jp

今回は機械学習を学ぶ上で出てくる自然対数の底(ネイピア数 e)とは何かを理解していきます。
間違える人は結構多いですが、e は「自然対数」ではありません。「ネイピア数」あるいは「自然対数の底」と呼ばれる定数です。

自然対数の底とは

対数の底には、10進法を使う常用対数とネイピア数と呼ばれる数学定数を使う自然対数があります。
記号として通常は e が用いられ、その値は、e = 2.71828 18284 59045 23536 02874 71352\cdots と続く無理数超越数となっています。 とても不思議な値ですよね。
不思議な値といえば円周率 \pi = 3.14159265359\cdots も同様に無理数超越数となっています。

qiita.com

最後に

今回はQiitaの方に書いてしまったので、リンクするだけにします。

対数logを理解してみる

はじめに

機械学習を学んでいると対数logがでてくる。基礎的なことから対数を理解してみたい。
指数はイメージし易いが、対数は分かりにくいと思われている。指数と対数はペアの関係にあり、かけ算とわり算のように逆関係にある。 先ずは、指数の大きさを視覚的にイメージするために、アメリカ・ワシントンにある航空宇宙博物館で公開されていた9分半の映画「パワーズ・オブ・テン」を紹介する。

9分半の映画

パワーズ・オブ・テンです、10の冪(10^{n})の違いを視覚でご覧ください。


Powers of Ten with Japanese translation

対数とは

例えば、2を3回かけ算すると 2 \times 2 \times 2 = 8 になります。これを「2を3乗したら8になる」と言い、以下のように書きます。

  2 ^ 3 = 8

このとき、2 の右上に乗っている 3 のことを「指数」と言います。指数は「1つの数を何回掛けるか」を表しています。
一方、「◯を何乗すれば△になるか」を表す数のことを「対数」と言います。 例えば「2を何乗すれば8になるか」を表す数は以下のように表記され、これを「2を底とする8の対数」と言います。

  log_{2}8 = 3

2 を底をする 8 の対数は 3 ということになります。
もう少し身近な値としてみます。1000 は、10 の 3乗 で「10を底とする1000の対数」は以下のようになります。

  log_{10}1000 = 3

計算の簡略化

対数には大きな桁数でも簡単に計算できるようになるというメリットがある。
それには指数法則と対数法則を知っておく必要がある。

指数法則①

a^{p} \times a^{q} = a^{(p+q)}

3^{4} \times 3^{5} について考える。3^{4} \times 3^{5} を指数を使わない形で表現すると(3 \times 3 \times 3  \times 3)(3 \times 3 \times 3  \times 3 \times 3) となる。 3 を繰り返しかけ算する回数は、  4 + 5 = 9 回である。
よって、3^{4} \times 3^{5} = 3^{(4+5)} となる。

指数法則②

(a^{p})^{q} = a^{(p \times q)}

(5^{3})^{4} について考える。(5^{3})^{4} は、5^{3} を4回繰り返しかけ合わせるので、(5^{3})^{4} = 5^{3} \times 5^{3} \times 5^{3} \times 5^{3} である。指数の部分の合計は、3乗が4回、つまり (3 \times 4) によって計算できる。
よって、 (5^{3})^{4} = 5^{3 \times 4} となる。

指数法則③

(a \times b)^{p} = a^{p} \times b^{p}

(3 \times 7)^{5} について考える。(3 \times 7)^{5} は、(3 \times 7) を5回繰り返しかけ合わせるので、 (3 \times 7)^{5} = (3 \times 7) \times (3 \times 7) \times (3 \times 7) \times (3 \times 7) \times (3 \times 7)
 = (3 \times 3 \times 3 \times 3  \times 3) \times (7 \times 7 \times 7 \times 7  \times 7) 、つまり = 3^{5} \times 7^{5} によって計算できる。
よって、 (3 \times 7)^{5} = 3^{5} \times 7^{5} となる。

対数法則①

かけ算を足し算に変換

log_{a}(M \times N) = log_{a}M + log_{a}N

log_{2}(8 \times 4) = log_{2}32 = 5 = 3 + 2 = log_{2}8 + log_{2}4
注目すべきは、M \times N というかけ算が、log_{a}M + log_{a}N という足し算に変換されているということである。このことが対数を利用してかけ算を足し算へ簡略化して計算する際に生かされる。

対数法則②

わり算を引き算に変換

log_{a}(M \div N) = log_{a}M - log_{a}N

log_{2}(8 \div 4) = log_{2}2 = 1 = 3 - 2 = log_{2}8 - log_{2}4
今回は、M \div N というわり算が、log_{a}M - log_{a}N という引き算の形に変換される。

対数法則③

累乗を簡単なかけ算に変換

log_{a}M^{k} = k \times log_{a}M

log_{2}8^{3} = log_{2}512 = 9 = 3 \times 3 = 3log_{2}8
例えば、2^{29} のような大きな計算も、この対数法則③を使えば一瞬にして近似値を求められる。

底の変換公式

底も自由に変えられるようになります。
\displaystyle \log_{a}b = \frac{(\log_{c}b)}{(\log_{c}a)} = 対数

\displaystyle \log_{2}8 = \frac{(\log_{10}8)}{(\log_{10}2)}
\displaystyle = \frac{0.903089987}{0.301029995} = 3

C# 数学10 「常用対数、ネイピア数e-基本1、自然対数-基本1」e log ln exp

対数の起源

対数を考え出したのはジョン・ネイピアです。
対数(logarithm)の名前の由来は、logos (比、神の言葉)とギリシャ語のarithmos (数) を合わせて logarithms(ロガリズム) という造語でネイピアが考案しました。

ジョン・ネイピア

1550年、宗教戦争が続くスコットランドにネイピアは生まれました。時代はヨーロッパ列強諸国が覇権を争う大航海時代のまっただ中。ネイピアはマーキストン城の城主として官の仕事の他、領民のために農業土木、軍事技術など多くの発明を行うエンジニアとして活躍しました。(中略) 遠洋航海に必要な天文学(船の測位)を支える数学が球面三角法です。数学者でも天文学者でもないネイピアは現実の切実な問題解決を目標としていました。それが天文学的計算の克服です。三角関数の計算の中に現れる大きい数の計算は天文学者を苦しめました。大航海時代は計算との闘いでもあったのです。天文学者は直面する天文学的計算を克服する手立てを見つけることができませんでした。彼らの計算を助けるために、ネイピアはついに新しい計算法を見つけ出す決心をします。時にネイピア44歳、1594年。その20年後の1614年、ついに人類は青天の霹靂として「対数」を手にします。第5回 ジョン・ネイピア対数誕生物語

また、日々私たちが使っている小数点(.)を使う表記はネイピアの発明です。小数点はネイピアが対数を生み出す過程で考え出した副産物だったのです。第6回 ジョン・ネイピア小数点「・」誕生物語
※小数の考え方はネイピア(1550〜1617)とほぼ同時期のシモン・ステヴィン(1548-1620) ですが19.178と表す小数を「19⓪1①7②8」のように表記していた。ステヴィンの本は1585年に出版、これはネイピアが対数表の計算を開始する1594年の9年前のことです。ネイピアはステヴィンの小数は使いづらいと判断し、もっと機能的で使いやすい小数の表記法を求め続けたのです。

発明を行うエンジニア

ネイピアはマーキストン城の城主であり、困った人を助けるために自分の才能を使う、優秀なエンジニアだったのです。
自分の領地の収穫を増やすために肥料や揚水機の研究をしたり、スペインの.侵攻を恐れて潜水艦や戦車などの兵器も数多く開発しています。これも領地内の人民を安心させるためだったのでしょう。
また、対数の計算を効率化するためにネイピアの骨と呼ばれる、かけ算や割り算などを簡単に行うための計算器具を発明しています。これは1617年(ネイピアが亡くなる年)に論文「小さな棒による計算術」としてエディンバラで発表されました。

対数表

対数表には、指定した数を底とする対数(例 底=2)、常用対数(底=10)、自然対数(底e=2.718281828…)があります。試験などで底を省略した対数表が出た場合は常用対数となります。

ネイピアが作成した対数表は不思議な底(0.9999999)だったため、使いやすい底を10にした常用対数表をネイピアの意思をついだブリッグスが作成しました。1617年に1000まで計算して出版し、1624年には1から20000までと90000から100000まで、小数点以下14桁まで計算した対数表を出版しました。1628年にブリッグスの対数表で抜けていた20,000~90,000の対数表をオランダのアドリアン・ブラックが完成させました。ただ、ブラックの対数表は10桁のものでしたが実際に利用するには十分な桁数でした。対数の発見

qiita.com

対数をとるメリット

対数のメリットは、極めてケタ数の大きい数の面倒なかけ算や割り算を、易しい足し算や引き算に直してくれることにあります。但し、求めた値はあくまで近似値であり、正確な値ではありません。
電卓や計算機のなかった昔の時代において非常に便利な計算方法でした。ピエール・シモン・ラプラスからは「天文学者の寿命を2倍にした(天文学者が一生にこなせる計算量を2倍にした)」と絶賛されるようになりました。

対数表を使った計算

131 \times 219 \times 563 \times 608 を計算する場合

10進数を底とする対数で表すと、log_{10}(131 \times 219 \times 563 \times 608) となる。
log_{10}( (1.31 \times 10^{2}) \times (2.19 \times 10^{2}) \times (5.63 \times 10^{2}) \times (6.08 \times 10^{2}) )
= log_{10}((1.31 \times 2.19 \times 5.63 \times 6.08) \times 10^{8})
ここから、かけ算が足し算になります。
= log_{10}1.31 + log_{10}2.19 + log_{10}5.63 + log_{10}6.08 + log_{10}10^{8}
= log_{10}1.31 + log_{10}2.19 + log_{10}5.63 + log_{10}6.08 + 8

ここで、  log_{10}1.31 、log_{10}2.19 、log_{10}5.63 、log_{10}6.08 の値を対数表から読み取る。
log_{10}(131 \times 219 \times 563 \times 608) \fallingdotseq 0.1173 + 0.3404 + 0.7505 + 0.7839 + 8 = 1.9921 + 8  =  0.9921 + 9 ここで、0.9921 に近い値を対数表から読み取ると、0.9921 \fallingdotseq log_{10}9.82 となる。
log_{10}(131 \times 219 \times 563 \times 608) \fallingdotseq log_{10}9.82 + 9 = log_{10}9.82 + log_{10}10^{9} = log_{10}(9.82 \times 10^{9})
こうして得られた log_{10}(131 \times 219 \times 563 \times 608) \fallingdotseq log_{10}(9.82 \times 10^{9}) の両辺を見比べると
131 \times 219 \times 563 \times 608 \fallingdotseq 9.82 \times 10^{9} = 9820000000 (実際の値は、 9820359456)

2^{29} を計算する場合

対数法則③を使います。
2^{29}は、10を底とする対数で表すと log_{10}2^{29} = 29 \times log_{10}2 となる。
log_{10}2 の値は、常用対数表から 0.3010 である。よって、log_{10}2^{29} = 29 \times 0.3010 = 8.7290 = 0.7290 + 8
常用対数の値が、0.7290 に近い真数の値を表から読み取ると、0.7290 \fallingdotseq log_{10}5.36 となる。
log_{10}2^{29} \fallingdotseq log_{10}5.36 + 8 \times log_{10}10 = log_{10}5.36 + log_{10}10^{8} = log_{10}(5.36 + 10^{8})
よって、2^{29}は、約 5.36 \times 10^{8} = 536000000 と計算できる。(実際の値は、536870912)

基本情報技術者試験の問題

ソートの計算量

計算量は一般に、O記法(オー記法、もしくはビッグオー記法と呼ぶ)を使って表します。O記法では計算量を、O(n)O(n^{2}) のような形で記述します。
性能が良い : O(1) \lt O(\log n) \lt O(n) \lt O(n\log n) \lt O(n^{2}) \lt O(n^{3}) : 性能が悪い

  • O(1)
    データ数nにかかわらず一定なので、nが2倍、3倍、10倍となっても計算量は等しいままです。
  • O(\log n)
    計算量を求める場合は底を2として考えます。
    nが2倍、3倍と増えても、計算量は1、2と増える程度なのでデータ量が多い場合に有用です。
  • O(n)
    比例なので、nが2倍、3倍と増えると、計算量も同様に2倍、3倍となります。
  • O(n \log n)
    先述のO(\log n) にnの計算量がかけられたものです。
    例えば、nが2倍になると計算量は約2.5倍、nが10倍になると計算量は約20倍、nが100倍になると計算量は約300倍になります。
  • O(n^{2})
    n個の要素を用いた総当りの組み合わせを求める場合がこのパターンに当てはまります。
    二次関数なので、nが2倍、3倍と増えると、計算量は4倍、9倍と増えます。

O記法にはいくつかのルールがある。

  • 中身は一番大きな規模だけ残す(最大次数の項以外を除く) 例 2+n+2n^{2}→2n^{2}
  • 係数は除く 例 2n^{2}→n^{2}
  • 係数は1にする

例 1 ~ Nまでの整数の総和を求めよ

  • 普通に計算する → N-1回足し算 → O(N-1) → O(N)  
  • 公式 \displaystyle S=\frac{(n+1)n}{2} を使う → 足し算と掛け算と割り算 → O(3) → O(1)

その中で対数が使われるのが下記となります。

O記法 概要 使用例
O(logN) <対数時間>
処理をひとつ行うたびに処理対象を何割か減らせるようなアルゴリズム。データ量が増えても計算時間がほとんど増えない。多くの場合、これ以上の改善はする必要はない。
ソート済み配列の二分探索
O(NlogN) <準線形、線形対数時間>
ちょっと重いO(N)程度。マージソートのように二分木でデータを分割し、かつそれらをリニアサーチするようなアルゴリズムの計算量。二分木のオーダー(logN)×リニアサーチのオーダー(N)をかけあわせてNlogNになる。
クイックソート、マージソート、ヒープソート

二分探索の計算量

ソートされている前提で、中央の値より小さい(左側)か大きい(右側)が分かるので、次からは半分は探索する必要はなくなる。
これを2の指数で表した場合、指数の数が1つずつ減ることになるので対数にすると、O(\log n) になる。
f:id:Yaju3D:20180122012235p:plain

クイックソートの計算量

分割統治法に基づくアルゴリズムです。
f:id:Yaju3D:20180122013630p:plain
毎回半分ずつにデータが分かれたと仮定すると、平均計算量は n個 \times \log_{2} n 段 → O(n\log n) となる。
f:id:Yaju3D:20180122213121p:plain

n進数での最大値

14けたの16進数の最大値は、10進数で表すと何けたか。ここで、 log_{10}2 = 0.301 とする。

log_{10}(16^{14})
= 14 \times log_{10}(16)
= 14 \times log_{10}(2^{4})
= 14 \times 4 \times log_{10}(2)
= 14 \times 4 \times 0.301 = 16.856

繰り上げて答えは17桁になります。

身近な問題

地震の大きさや音階や星の等数や化石の年代測定や複利計算にも対数が使用します。他にも電気通信や音の単位に用いられるデシベル、音の大きさを表すホンでも使用されます。

地震のエネルギーの大きさ

地震のエネルギーの大きさを表す言葉として「マグネチュード」と言います。

マグニチュードと震度の違いは?
「マグニチュード」は、地震そのものの大きさ(規模)を表すものさしです。一方「震度」は、ある大きさの地震が起きた時のわたしたちが生活している場所での揺れの強さのことを表します。

マグネチュードを M、地震が発生するエネルギーを E (単位モジュール)とすると、logE =  4.8 + 1.5M という関係式があります。
この式より、E = 10^{4.8 + 1.5M} = 10^{4.8}10^{1.5M} となります。
したがって、 M が1増えるとエネルギーは10^{1.5}倍(およそ32倍)、 M が2増えるとエネルギーは10^{3}倍(およそ1000倍) になります。また、M が0.2増えるとエネルギーは10^{0.3}倍(およそ2倍) になります。

マグネチュードが2違うと1000倍で1違うと32倍って差が分かりにくいですが、x \times x = 1000 とすると x^{2} = 1000 = x = \sqrt{1000} = 31.6227  \fallingdotseq 32 となるわけです。

音階の違い

ピタゴラスの定理などで有名な古代ギリシャの数学者ピタゴラスが音階「ドレミファソラシド」を作りました。ピタゴラスが発見した音階は弦の長さで決められたものでしたが、我々が通常聞いている音階は振動数の比で決められています。

平均律音階は、1オクターブ高い音は振動数が2倍であり、その1オクターブを12音階に均等に分けたものである。
f:id:Yaju3D:20180128121348p:plain

音階 ド# レ# ファ ファ# ソ# ラ#
周波数比 2^{0}=1 2^{\frac{1}{12}} 2^{\frac{2}{12}} 2^{\frac{3}{12}} 2^{\frac{4}{12}} 2^{\frac{5}{12}} 2^{\frac{6}{12}} 2^{\frac{7}{12}} 2^{\frac{8}{12}} 2^{\frac{9}{12}} 2^{\frac{10}{12}} 2^{\frac{11}{12}} 2^{\frac{12}{12}}=2
周波数 fr fr^{1} fr^{2} fr^{3} fr^{4} fr^{5} fr^{6} fr^{7} fr^{8} fr^{9} fr^{10} fr^{11} fr^{12}
近似値 262 277 294 311 330 349 370 392 415 440 466 494 523

※周波数 f=262

r^{12} = 2 で、これを満たす r を求めると 1.06^{12} \fallingdotseq 2 となります。半音上がることに振動数を 1.06倍されている。
\displaystyle r = \sqrt[12]{2} = 2^{\frac{1}{12}} = 1.0594631 \fallingdotseq 1.06

つまり、音階も対数変換(底1.06)ととらえることができる。\log_{1.06}(周波数)=音階

星の等数

歴史上で星の明るさをランクづけしたのは、古代ギリシアの天文学者ヒッパルコスです。彼は、肉眼で見えるもっとも明るい星を1等星、かろうじて見える星を6等星として、1等星~6等星までの6段階に分けました。月日が経ち、1856年にイギリスの天文学者のノーマン・ロバート・ポグソンは、ジョン・ハーシェルの研究結果を元にし1 等星の明るさは 6 等星の 100 倍であり、1 等級ごとの明るさの違いは 100^{\frac{1}{5}} 倍であると定義しました。

f:id:Yaju3D:20180128204643p:plain

\displaystyle r = \sqrt[5]{100} = 100^{\frac{1}{5}} = 2.51188643151 \fallingdotseq 2.51

つまり、星の等数は対数(底2.51)となります。

化石の年代測定

化石の年代測定ってどうやっているのか不思議でした。
これは「放射性炭素年代測定法」というのが1974年にアメリカのリビーという人が発見した方法で、炭素14の性質を利用しています。
炭素14は放射性炭素ともいわれ、電子を放出して窒素14に変わる。この崩壊によって炭素14の数が半分になるまでの期間を半減期といい5730年となっている。
生きている生物(動物、植物)はこの炭素14を体内に取り込むので、体内の炭素14の割合は大気中の割合と同じとなる。また生物が死ぬと炭素14の供給がなくなり崩壊だけが続くので発見した資料の炭素14の割合を調べることで、その資料が死んでからの年数が推定できる。

ある木管に炭素14の割合を調べたら、75%に減っていた。
この場合、炭素14が1年で r 倍に現象するとして、この木簡が x 年前のものだとすると、
r^{x}=0.75 また r^{5730}=0.5

x\log r=\log 0.75 、② 5730\log r=\log 0.5
① と ② より
\displaystyle x=\frac{\log0.75}{\log r} = \frac{5730}{\log 0.5} \times \log 0.75
\displaystyle =\frac{5730(\log3 - 2\log2)}{- \log 2}
 = 5730 \times 0.4150 = 2378 年前

複利計算

サラリーローンで、1万円を1日1割の複利で2ヶ月借りる場合、
<複利計算>元利合計  = 元金 \times (1 + 利率)^{期間の数} の式となります。
1 \times (1+0.1)^{60} \fallingdotseq 305 なんと、約305万円にもなります。

これを対数で計算してみます。電卓がない状態で1.1を60回かけるんなんてうんざりですが、その場合は対数表を使えばいい。
\log_{10}x = \log_{10}1.1^{60}
対数の法則を使う
\log_{10}x = 60\log_{10}1.1
対数表では\log_{10}1.1 = 0.0414 となります。
\log_{10}x = 60 \times 0.414 = 2.484
このうち、小数部の 0.484 を対数表で見ると、3.05 です。
\log_{10}x = 2.484 = 2 + 0.484
= \log_{10}10^{2} + \log_{10}3.05
= \log_{10}100 \times 3.05
= \log_{10}305
 x = 305

自然対数

自然対数は、2.71828182845\cdots という無理数を底にした対数となります。一方、常用対数は底を10にした対数となります。
常用対数は電卓やコンピューターの登場により使用されることがなくなりましたが、自然対数はコンピューターで使用する上で標準と底となっています。これは次記事に書きます。 yaju3d.hatenablog.jp

機械学習での役割

  • かけ算を足し算または割り算を引き算にすることで計算を楽にさせる。
    \displaystyle \prod_{n=1}^{N} f(n) = \sum_{n=1}^{N}\log f(n)\prodは、かけ算を繰り返す記号
  • 機械学習では非常に大きな数を扱います。プログラムでこのような数を扱うと、オーバーフローを起こしてしまうときがあります。そのような数は、対数 をとって扱うことで、オーバーフローを防ぐことができます。例えば、100000000 = 10^{8}0.000000001 = 10^{-8} となります。
  • 機械学習では確率を使いますが、同時確率の場合には 1 以下の数の掛け算の連続になります。多い場合にはアンダーフローを起こしてしまうときがあります。そのような数は、対数 をとって扱うことで、アンダーフローを防ぐことができます。
    例としてサイコロを2回投げた場合、1回目に1の目が出て2回目に2の目が出る確率は、下記の計算となる。
    \displaystyle \frac{1}{6} \times \frac{1}{6} = \frac{1}{36}
  • 対数は単調増加関数であるため、ある関数 f(x) があって f(x) を最小にする値を求めた場合、対数をとった \log f(x) でも最小の値は同じになります。また、最大値を求める場合でも同じです。
    f(x)=(x-1)^{2}+2は、x=1の時、最小値をとる
    \log f(x)=\log ((x-1)^{2}+2) も、x=1の時、最小値をとる

単調増加関数

単調増加な関数は、任意な値  x1 と x2 があったとき 、 x1 \lt x2 ならば  f(x1) \lt f(x2) となるような関数  f(x) であるいうことです。
例えば、  x1=3、x2 = 5 x1 \lt x2 が成り立ちます。この関係性は対数に直しても  \log x1 \lt \log x2 が成り立ちます。

スポンサーリンク