{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"colab_type": "text",
"id": "view-in-github"
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "W7cNmbENdx0R"
},
"source": [
"# 最適化問題の基礎\n",
"\n",
"\n",
"[この章の目的]\n",
"最適化問題のイメージを掴み、一次元の単峰的な関数の最小値を探索できるようになる。"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "r244nZzmtIZ0"
},
"source": [
"\n",
"最適化問題とは、大雑把に言えば「ある量の最小値/最大値とそれを与える変数/パラメータの値を知ること」と言い換えられる. \n",
"種々のデータ解析や学術的分野での計算をはじめ世の中の多くの問題は**最適化問題**に帰着される.例えば、\n",
"- 商品の売り上げを最大化するための広告戦略を考える\n",
"- ある製品の製造コストを最小化するための製造工程を設計する\n",
"- 配達員の配達ルートを最適化(≒時間や燃料の消費を最小化)する\n",
"- 機械学習のモデルのパラメータを調整し、予測精度を最大化する\n",
"\n",
"などなど。「人生も、何らかの目的関数$f(x)$(一般に$x$は多次元),たとえば幸福感(不幸感)を最大化(最小化)すること、という意味では最適化問題を考えていることに相当する」というと少し大げさでしょうか。\n",
"\n",
"\n",
"この章では、最適化の基礎について説明する。 \n",
"授業では実際に最適化で必要な数学的な操作をするコードを作ったりする訳ではないが、「ライブラリに入れてポンッ」ではなく、背後にあるモチベーションや概念を理解しておくことは自分が興味のある問題を最適化問題に帰着させて解くためには不可欠になる。\n",
"\n",
"※高校で微分をあまり勉強していないという方に向けて末尾に数学的準備の項を設けてあるのでチェックしてください.(よく知っているという方もさっと目を通してみてください) \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "loZUoKQD9uYU"
},
"source": [
"## 考えたい問題のイメージ"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "L1wUnmJn9xoF"
},
"source": [
"以下で考えたい問題のポンチ絵\n",
"\n",
"
\n",
"\n",
"> あなたは変数$x$のある特定の点$t$での関数値$f(t)$を観測して知っている。 \n",
"> また、図中に**緑の線で示したような$f(x)$の振る舞いを予め知ることはできず \n",
"> 都度$x$を変えて調べることで初めて対応する$y$の値が分かる**状況を考えよう。 \n",
"> (そのことを点線で表現しています) \n",
"> このとき、$x$を変えながら$f(x)$が最小となる点を探すには一般にどうすればよいだろうか?\n",
"\n",
"\n",
"変数が2次元(やそれ以上)の場合も、\n",
"\n",
"
\n",
"\n",
"(実際上の難しさが違うとはいえ)基本的なアイデアは同様なので、以下では1次元の場合のみ扱うことにする.\n",
"\n",
"\n",
"---\n",
"\n",
"さて、1次元の場合に話を戻して...(図を再掲)\n",
"\n",
"
\n",
"\n",
"\n",
"$x$の値を$t$から更新していく方法として、色んな方法が考えられる。たとえば...\n",
"\n",
"1. ランダムに探索する(例:サイコロを振って、目が1-3なら$x$を適当な値だけ減らし出目が4-6なら$x$を増やしていく)\n",
"2. xを適当な区間に分割(10等分,100等分, etc.)その点で値を調べる\n",
"\n",
"などが考えられる。\n",
"\n",
"ただし$x$が薬品の濃度で$f(x)$が薬品の副作用だとしたとき(※)には、$x$を変えて$f(x)$の値を調べる(測定する)と言っても限界がある。\n",
"\n",
"※「1変数の関数であるはずがない」ことは一旦忘れることにして、イメージしやすいようこの例にした\n",
"\n",
"1.の方法では、**同じところを何度か行き来するので明らかに無駄が多い**し、 \n",
"2.の方法では**分割が少なすぎると十分な精度で最適解が見つからない** \n",
"**かといって分割が多すぎるとコストがかさむ**。\n",
"\n",
"したがって、**できるだけ少ない試行回数で最適な値を見つける効率のよい探索方法**が必要となる。 \n",
"そこで重要なのが、$x$を変えたときに関数$f(x)$がどのように変化するか、つまり微分(勾配)の情報である。\n",
"\n",
"**注意** \n",
"そもそも$f(x)$の式の形がわかっていて$f'(x)=0$となる(つまり極値を持つ)$x$の値が計算できるのなら、わざわざ$x$を更新するなどという手続きは必要ない。 \n",
"一般の問題では、関数やその勾配がそもそも書き下せなかったり極値を与える$x$($f'(x)=0$の解)を解析的に解けなかったりする。\n",
"そんなときは以下で考えるような、$x$を更新していくような探索が必要となる。\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "P1xRaNCVtMju"
},
"source": [
"## 最も基本的な最適化手法: 勾配法\n",
"\n",
"*以下では、微分の値のことを指して勾配と呼ぶことにする."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "B-PHr6IztBRE"
},
"source": [
"さて、上の一次元の例をもっと簡略化することにして、単峰的(つまり1つしか谷が無い)場合を考えてみよう。\n",
"\n",
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "hsMxEg_frbpf"
},
"source": [
"この様な場合、斜面の傾きに沿ってパラメータを更新していけばいずれ$f(x)$の最小値が見つかりそうだ。 \n",
"点$x=t$での勾配は(あえて)偏微分で書くと$\\frac{\\partial f(x)}{\\partial x}|_{x=t}$となる。\n",
"\n",
"$x$の値を更新する際に、更新前の値を$x_{old}$,更新後の値を$x_{new}$と書くことにすると、 \n",
"$x_{new} = x_{old} -\\eta \\frac{\\partial f(x)}{\\partial x}|_{x=x_{old}}$ と更新する。\n",
"\n",
">注) $\\frac{\\partial f}{\\partial x}|_{x=t}$という表記に慣れていない方は、$f'(x=t)$のことと思って頂いて結構です\n",
"\n",
"\n",
"\n",
"微分(傾き)が正の場合は、$x$を正に増やすと$f(x)$の値が増える \n",
"微分(傾き)が負の場合は、$x$を正に増やすと$f(x)$の値が減る \n",
"ことから、微分の値の前にマイナスがついている理由も納得できるかと思います。\n",
"\n",
"最小化でなく最大化を考える場合はマイナス符号は不要で`+`となる。(上と同じように考えてみよう)\n",
"\n",
"上では、$\\eta$という係数(正の値)を導入したが、これは**傾いてる方向にどれくらいのスケールで$x$を更新するか**をコントロールするパラメータで、機械学習などの分野で学習率と呼ばれるものに対応している。 \n",
"今の単峰的な関数の場合、学習率$\\eta$は適当な値をひとつ選べば十分である。"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "uIAvrbNCx0c1"
},
"source": [
"ただし、上の$\\eta$が大きすぎたり小さすぎたりすると、なかなか効率的に$f(x)$の最適解を見つけられないことがある。\n",
"\n",
"$\\eta$が大きすぎると、$x$の更新幅が大きすぎて谷を跨いでしまい、なかなか谷の底に落ち込まない、といったことが起こりえる."
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "jVRqeo3Hxbvx"
},
"source": [
"
\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "ETitsG3AyLI_"
},
"source": [
"一方で$\\eta$が小さすぎると、なかなか更新が進まず、これまた効率の悪い探索となってしまう。\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "xiFm1Ew9q5jk"
},
"source": [
"これ以外にも、最初の図のように多峰的(山あり谷あり)な関数だと、 \n",
"$\\eta$が小さいと局所的な谷に捕まってしまってなかなか大局的な谷にたどり着けない、 \n",
"かといって$\\eta$が大きすぎるとあらぬ方向に飛んでいってしまう、といったことが起こりえる。\n",
"\n",
"その様な場合にはもう少し\"賢い\"最適化の手法を応用したり、更新の幅を徐々に減衰させるなどの工夫が必要になる。"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "cl4tMpwvU2OS"
},
"source": [
"### $\\clubsuit$その他の最適化手法\n",
"\n",
"勾配法の他にもたくさん問題に応じて最適化手法が用いられる。 \n",
"\n",
"最適化問題自体、非常に話題が豊富なので、15コマ程度ましてや1コマで扱い切れるようなトピックではない。\n",
"\n",
"興味がある方は下記のキーワードなどで調べてみよう。\n",
"\n",
"たとえば機械学習では、勾配の情報だけでなくそれまでの更新の履歴を活用した各種の最適化手法がよく用いられる。→ AdaGrad, Adam, etc.\n",
"\n",
"また、物理学から着想を得た最適化手法もよく用いられる → 焼きなまし法(Simulated Annealing)\n",
"\n",
"最適化の手法自体に(広義の)機械学習の手法を使うこともある → ベイズ最適化 (おまけのノートブックもある)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "cxTy2daMOgO5"
},
"source": [
"### $\\clubsuit$目的関数の選択\n",
"\n",
"最適化問題を解く場合に最小化/最大化したい関数のことを目的関数と呼ぶ。\n",
"\n",
"データ分析をする上で最もよく出てくる目的関数はカイ自乗(chi-square)で、回帰の場合、予測$y_i$と観測値$f(x_i)$との間の二乗誤差$\\chi^2 = \\sum_i (y_i-f(x_i))^2$といったように定義される。 \n",
"(データの数で割ったり平方根を取った値、平均二乗誤差を採用することも多い)\n",
"\n",
"機械学習の文脈では「予測の誤差(損失)を最小化したい」というモチベーションがあり、目的関数を損失関数/Loss functionなどと言ったりもする。\n",
"\n",
"目的関数の選び方は問題によってまちまちで、その選び方によって\"最適なモデル\"も変わり得る、ということに注意しておこう。\n",
"\n",
"たとえば、二乗誤差を考える際「正解が10のところを20と予測した場合」と「正解が1000のところを1010と予測した場合」とで二乗誤差の値自体は同じだが、 \n",
"データの数値に対する誤差が占める割合に着目すれば、前者は2倍(100%)ずれていて、後者は1%しかずれていない。\n",
"\n",
"このようにスケールの異なる量が出てくる状況下では、目的関数の定義で対数を取ったりする場合もある。\n",
"\n",
"一般に目的関数の選択は、複数の量のバランス(トレードオフ)を考える必要があり、その選び方が問題の解釈や性能にも大きく影響する。"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "6r7qWIUQ27li"
},
"source": [
"### 簡単な例でのプログラム\n",
"\n",
"下に凸な二次関数の最小値を、勾配降下法で求めてみよう. もちろん二次関数の場合は、極値を与える$x$の値は、 \n",
"プログラムを書くまでもなく平方完成で求められるが、目的は数値計算になれるためなので気にしないことにする。\n",
"\n",
"$f(x)=5x^2 -4x + 3$とでもしましょう。 \n",
"$x$についての微分はもちろん$\\frac{df(x)}{dx}=10x -4$になる。"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"id": "vQmG-t4Y3PAY"
},
"outputs": [],
"source": [
"def f(x):\n",
" return 5.0 * x**2 - 4.0 * x + 3.0\n",
"def dfdx(x):\n",
" return 10.0 * x -4.0"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "--DHmqJp3f0E"
},
"source": [
"はじめに$x=3.0$にいるとして、$\\eta=0.2,0.05,0.01,0.001$の4通りについて \n",
"勾配降下法でパラメータを100回更新してみる。\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"id": "vgoJsFe73raV"
},
"outputs": [],
"source": [
"step = 100\n",
"etas = [0.2, 5.e-2, 1.e-2, 1.e-3]\n",
"x_and_f = [ [] for i in range(len(etas))]\n",
"for i in range(len(etas)): \n",
" x = 3.0 #初期値\n",
" x_and_f[i] += [ [ x, f(x) ] ] #結果をリストに格納\n",
" for tstep in range(step): # step回だけ更新を繰り返す\n",
" x = x - etas[i] * dfdx(x) # xnew = xold - eta * dfdx(at xold)になっている\n",
" x_and_f[i] += [ [ x, f(x) ] ] #結果をリストに格納"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "P-v28tFN9uAj"
},
"source": [
"アニメーションで見てみると... (少し実行に時間がかかります)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 456
},
"id": "NEu9t-eoCAhx",
"outputId": "0cebb7be-d68a-46cd-8a63-1df1e5ae431f"
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"