Implementing_a_Decomposition_Method with the Cholesky Decomposition Method

#!/usr/bin/env python3

---

Using the Cholesky Decomposition Method

---

Linear Regression은 $A \cdot x=y$을 사용합니다. 

Cholesky decomposition은 matrix $A$를 lower triangular matrix $L$과 $L^{T}$로 분해합니다.

차원을 같게 하기 위해 matrix $A$ 앞에 $A^{T}$를 곱하여 square matrix로 만듭니다.

따라서 아래와 같은 식이 성립합니다.

$A^{T} \cdot A=L^{T} \cdot L$

Linear Regression을 적용하면 아래와 같이 사용할 수 있습니다.

$A\cdot X=Y$

$(A^{T} \cdot A) \cdot X = A^{T} \cdot Y$

$(L^{T} \cdot L) \cdot X = A^{T} \cdot Y$

$L^{T} \cdot Z = A^{T} \cdot Y$,     $L \cdot X = Z$

Cholesky decomposition을 Linear Regression에 적용하기 위해서는 다음과 같은 step이 필요합니다.

1. $A^{T} \cdot A = L^{T} \cdot L$에서 $L$을 구합니다.

2. $L^{T} \cdot Z = A^{T} \cdot Y$에서 $Z$를 구합니다.

3. $L \cdot X = Z$에서 $X$를 구합니다.

$X$는 우리가 구하고자 하는 slope와 intercept가 있는 matrix입니다.

이 과정을 간단한 데이터를 만들어 구현해 보겠습니다.

import tensorflow as tf

import numpy as np

x_vals = np.linspace(0, 10, 100).reshape(-1, 1)

print(x_vals[:6])

# [[0.        ]

#  [0.1010101 ]

#  [0.2020202 ]

#  [0.3030303 ]

#  [0.4040404 ]

#  [0.50505051]]

y_vals = x_vals + np.random.normal(0, 1, size=100).reshape(-1, 1)

print(y_vals[:6])

# [[-1.34770577]

#  [-0.4146378 ]

#  [-0.14096172]

#  [ 0.23305495]

#  [ 1.66821972]

#  [-0.35141322]]

ones = np.ones(100).reshape(-1, 1)

print(ones[:6])

# [[1.]

#  [1.]

#  [1.]

#  [1.]

#  [1.]

#  [1.]]

A = np.c_[x_vals, ones]

print(A[:6])

# [[0.         1.        ]

#  [0.1010101  1.        ]

#  [0.2020202  1.        ]

#  [0.3030303  1.        ]

#  [0.4040404  1.        ]

#  [0.50505051 1.        ]]

A_tsr = tf.constant(A, dtype=tf.float32)

y_tsr = tf.convert_to_tensor(y_vals, dtype=tf.float32)

with tf.Session() as sess:

    tA_A = tf.matmul(tf.transpose(A_tsr), A_tsr)

    L = tf.cholesky(tA_A)

    

    # solve $L\cdot Z=A^{T}  \cdot Y$, for $Z$

    tA_y = tf.matmul(tf.transpose(A_tsr), y_tsr)

    sol1 = tf.matrix_solve(L, tA_y)

    

    # solve $L^{T} \cdot X= Z$,  $Z$=sol1,  for $X$

    sol2 = tf.matrix_solve(tf.transpose(L), sol1)

    solution = sol2.eval()

slope = solution[0][0]

print('slope: {:3f}'.format(slope))

# slope: 0.988516

cept = solution[1][0]

print('intercept: {:.3f}'.format(cept))

# intercept: 0.163

시각화는 다음코드로 구현할 수 있습니다.

import matplotlib.pyplot as plt

reg_params = []

for i in x_vals.ravel():

    poly = i*slope + cept

    reg_params.append(poly)

    

plt.scatter(x_vals, y_vals, label='data')

plt.plot(x_vals, reg_params, c='red', label='best fit line')

plt.xlabel('feature 0', size=15)

plt.ylabel('feature 1', size=15)

plt.legend(loc='upper center', bbox_to_anchor=[0.1, 1.1], fancybox=True)

plt.show()

Cholesky 분해로 분석한 LinearRegression

---

참고 자료: 

[1]TensorFlow Machine Learning Cookbook, Nick McClure

[2]https://github.com/nfmcclure/tensorflow_cookbook