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

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

対数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 が成り立ちます。