Kei Minagawa's Blog

皆川圭(@keimina)のブログ、Pythonで試したことを書いていきます

離散化を行うモデルの検討・実装

1 本記事で扱う「離散化」の定義

まず、語弊がないよう、本記事で扱う「離散化」を定義しておきます。まず、本記事では、数直線上のある領域を何分割かにし、点で区切ることを「離散化」と言うこととします。一般的に、数直線上の領域[X1, X2]をN分割するときは、等分割し、分割した領域のそれぞれの長さは (X2 - X1)/N になります。本記事では、このように離散化で領域をN分割する時、領域をN等分に分割するのではなく、分割後のN個の領域がそれぞれ異なる長さを持つように分割する方法について記載します。領域を異なる長さの領域に分割することができると、離散化が絡む問題の最適化を行う時に、離散化の方法を含め最適化できるようになるかもしれません。

2 モデルの概要

以下のような数直線を考えます。

f:id:keimina:20200811235736p:plain

図1: 数直線(1)

これを以下のように分割数N=3でd1,d2,d3の領域に分割することを考えます。

f:id:keimina:20200811235738p:plain

図2: 数直線(2)

すると、以下の式が成立します。

\begin{eqnarray} x1 &=& d1\\[8pt] x2 &=& d1 + d2\\[8pt] x3 &=& d1 + d2 + d3\\[8pt] \end{eqnarray}

これは行列で表すと以下になります。

\begin{eqnarray} \left( \begin{array}{cc} x1\\ x2\\ x3\\ \end{array} \right) = \left(\begin{array}{cc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array} \right) \left( \begin{array}{cc} d1\\ d2\\ d3\\ \end{array} \right) \end{eqnarray}

ここで、行列Tを以下のように定義します。この行列Tは下三角行列となっています。

\begin{eqnarray} T = \left(\begin{array}{cc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array} \right) \\ \end{eqnarray}

また、x1,x2,x3をX, d1,d2,d3をDとして以下のように定義します。

\begin{eqnarray} X = \left( \begin{array}{cc} x1\\ x2\\ x3\\ \end{array} \right)\\[8pt] D = \left( \begin{array}{cc} d1\\ d2\\ d3\\ \end{array} \right) \end{eqnarray}

すると先ほどのx1,x2,x3を表す式は以下のようになります。

\begin{eqnarray} X = T \cdot D \end{eqnarray}

この式の、d1,d2,d3が決まれば、 x1,x2,x3 も決まりますので、d1,d2,d3が学習すべきパラメータになると推測できます。

3 モデルの詳細

モデルの概要 では数直線上の[0,10]をざっくり分割することだけ考えていました。この章では、領域[s(start),e(end)]をN分割することを考えます。

モデルの概要 を参考に新たにモデルを以下のように定義します。

\begin{eqnarray} X = (e - s) T \cdot \frac{D}{\lvert D \rvert} + s \end{eqnarray}

\(\lvert D \rvert\) は \(d1 + d2 + d3 + ... + dN\) です。 \(D\) をこれで割り算することで[0, 1]の範囲の値をとるように正規化しています。それを \(e -s\) でスケール、 \(s\) でシフトして、[s, e]の値をとるようにしています。\(T\) は 下三角行列です。このモデルを使用して、[s, e] をN分割することを考えます。

例えば、 区間[-5,5] を10分割する場合

\begin{eqnarray} \left( \begin{array}{cc} x1\\ x2\\ x3\\ x4\\ x5\\ x6\\ x7\\ x8\\ x9\\ x10\\ \end{array} \right) = 10 \left(\begin{array}{cc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \right) \cdot \left( \begin{array}{cc} \frac{d1}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d2}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d3}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d4}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d5}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d6}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d7}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d8}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d9}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d10}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \end{array} \right) + \left( \begin{array}{cc} -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ \end{array} \right) \\[8pt] \end{eqnarray}

この式の \(x10\) を計算すると 5 となります。これは [s, e] の e ですので、以下になります。

\begin{eqnarray} \left( \begin{array}{cc} x1\\ x2\\ x3\\ x4\\ x5\\ x6\\ x7\\ x8\\ x9\\ e\\ \end{array} \right) = 10 \left(\begin{array}{cc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right) \cdot \left( \begin{array}{cc} \frac{d1}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d2}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d3}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d4}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d5}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d6}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d7}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d8}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d9}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ 1 \end{array} \right) + \left( \begin{array}{cc} -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ -5\\ \end{array} \right) \\[8pt] \end{eqnarray}

e を加えたので s も加えてみましょう。

\begin{eqnarray} \left( \begin{array}{cc} s \\ x1\\ x2\\ x3\\ x4\\ x5\\ x6\\ x7\\ x8\\ x9\\ e\\ \end{array} \right) = 10 \left(\begin{array}{cc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right) \cdot \left( \begin{array}{cc} 0\\ \frac{d1}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d2}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d3}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d4}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d5}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d6}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d7}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d8}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ \frac{d9}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10} \\ 1 \end{array} \right) + \left( \begin{array}{cc} -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ -5 \\ \end{array} \right) \\[8pt] \end{eqnarray}

これは、数直線で表すと以下になります。今回の例では \(s = -5\) 、 \(e = 5\) です。

f:id:keimina:20200811235741p:plain

図3: 数直線(3)

式をみるとパラメータ \(d10\) が分数の分子にはなく、分母に現れているのが興味深いです。 \(x9\) の式は右辺に \(\frac{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9}{d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 + d10}\) を含みます。この式は分母に \(d10\) があるおかげで 1 にならず, \(d10\) のための隙間を残しているように見えます。

結局のところ、左辺が s, e となっている式は学習と関係ありません。それを踏まえると、最終的に [s, e] を N分割する時に、学習に使用する式は以下になります。

\begin{eqnarray} \left( \begin{array}{cc} x_{1}\\ x_{2}\\ x_{3}\\ ... \\ x_{N-1}\\ \end{array} \right) = (e - s) \left( \begin{array}{cc} 1 & 0 & 0 & ... & 0 \\ 1 & 1 & 0 & ... & 0 \\ ... & & & & ... \\ 1 & 1 & 1 & ... & 1\\ \end{array} \right) \cdot \left( \begin{array}{cc} d_{1}\\ d_{2}\\ d_{3}\\ ... \\ d_{N-1}\\ \end{array} \right) \frac{1}{d_{1} + d_{2} + ... + d_{N}} + s \end{eqnarray}

試しに、 N=2 のときこの式がどうなるか見てみましょう。

\begin{eqnarray} \left( \begin{array}{cc} x_{1}\\ \end{array} \right) &=& (e - s) \left( \begin{array}{cc} 1 \end{array} \right) \cdot \left( \begin{array}{cc} d_{1} \end{array} \right) \frac{1}{d_{1} + d_{2}} + s \\[8pt] x_{1} &=& \frac{(e - s)d1}{d_{1} + d_{2}} + s \\[8pt] x_{1} &=& \frac{e \cdot d1 - s \cdot d1}{d_{1} + d_{2}} + s \\[8pt] x_{1} &=& \frac{e \cdot d1 - s \cdot d1}{d_{1} + d_{2}} + \frac{s \cdot d1 + s \cdot d2}{d_{1} + d_{2}} \\[8pt] x_{1} &=& \frac{e \cdot d1 + s \cdot d2}{d_{1} + d_{2}} \\[8pt] x_{1} &=& \frac{s \cdot d2 + e \cdot d1}{d_{1} + d_{2}} \\[8pt] \end{eqnarray}

これは、区間[s, e]をd1:d2に内分する数学の公式と同じになっています。そのため、問題ないことがわかります。(もしかすると本モデルは内分の公式を拡張したものになっているのかもしれません)

4 モデルまとめ

[s, e]をN分割する作成したモデルをもう一度以下に記載します。

\begin{eqnarray} \left( \begin{array}{cc} x_{1}\\ x_{2}\\ x_{3}\\ ... \\ x_{N-1}\\ \end{array} \right) = (e - s) \left( \begin{array}{cc} 1 & 0 & 0 & ... & 0 \\ 1 & 1 & 0 & ... & 0 \\ ... & & & & ... \\ 1 & 1 & 1 & ... & 1\\ \end{array} \right) \cdot \left( \begin{array}{cc} d_{1}\\ d_{2}\\ d_{3}\\ ... \\ d_{N-1}\\ \end{array} \right) \frac{1}{d_{1} + d_{2} + ... + d_{N}} + s \end{eqnarray}

これは、以下のように領域[s,e]をN分割します。

f:id:keimina:20200811235744p:plain

図4: パラメータと数直線の関係

5 使ってみる

このモデルを使用して、[-5, 5] の区間を N=10 で均等に分割することを考えます。 d1, d2, …, d10 はランダムに初期化し、均等に分割した場合との差分(MSE)を損失関数として定義し、それを最小化します。ソースコードは以下のようになります。

5.1 ソースコード

import numpy as np
import torch

N = 10
s, e = -5, 5

# モデル
D = torch.rand((N,), requires_grad=True)
T = torch.tensor(np.tri(N-1).astype(np.float32))

# 教師データ
t = torch.tensor(np.linspace(s, e, N+1, dtype=np.float32)).view(-1, 1)[1:N]

# 学習準備
optimizer = torch.optim.Adam([D])
lossfn = torch.nn.MSELoss()

# 学習
for i in range(10000):
    optimizer.zero_grad()
    X = (e - s) * torch.matmul(T, D.view(-1, 1)[:N-1])/D.sum() + s
    if i==0:
        print("Before Training X:")
        print(X)
    loss = lossfn(X, t)
    loss.backward()
    optimizer.step()

print("After Training X:")
print(X)

5.2 出力結果

Before Training X:
tensor([[-4.8648],
        [-2.8749],
        [-0.9789],
        [-0.2264],
        [ 0.0264],
        [ 1.9179],
        [ 1.9651],
        [ 2.0050],
        [ 3.6523]], grad_fn=<AddBackward0>)

After Training X:
tensor([[-4.],
        [-3.],
        [-2.],
        [-1.],
        [ 0.],
        [ 1.],
        [ 2.],
        [ 3.],
        [ 4.]], grad_fn=<AddBackward0>)

f:id:keimina:20200812000011g:plain

図5: 出力結果

6 考察

出力結果 を見ると問題なく機能していることが確認できました。使ってみる の問題設定が非現実的ですが、実際は、本記事で定義したモデルで離散化を行い、それを何らかのモデルとつなぐことで、離散化を含めた最適化が行えるのではないかと思っています。

7 まとめ

離散化を行うモデルの検討・実装を行いました。

おやすみなさい。