almost 3 years ago

問題:如果房價與房屋坪數有如下關係~

房屋大小(坪) 房價(百萬)
35 10
20 7
40 13
50 15

我們想預估,房價與房屋大小的關係為何?


數學定義

輸入特徵 (input features) 是指影響結果的變(參)數,
輸出目標 (output targets)也就是我們想估計的東西,
(training sets)一組訓練資料
為機器經關訓練資料的學習後,所產生的假設。之後輸入資料經過機器的假設會輸出推測的結果。概念如下圖,

當目標變數為是連續的,這樣的學習稱之為回歸問題(regression),而當目標為離散的,則是分類問題(classify)

如果我們基於線性假設,即輸出與輸入有線性關係。
$$ h_\theta = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \ldots = \sum_{j = 0} ^{l} \theta_j x_j $$

我們能定義成本函數是每一筆訓練資料與假設函數(hypothesis)之間的平方差之和,
$$ J(\theta) = \frac{1}{2} \sum_i | y^{(i)} - h_\theta (x^i )|^2$$, 其中{i}是輸入的訓練資料(training sets)

現在我們要尋找一組最佳的使得成本函數(cost function)最小化。作法是,先猜測一組然後不斷的沿著此cost function的梯度方向,進行更新迭代,
$$ \theta_j \rightarrow \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta) \tag{1}$$
其中 為learning rate,決定更新的幅度大小。太小則必須迭代多次才能收斂,而太大有可能無法收斂。而梯度函數
$$
\frac{\partial}{\partial \theta_j} J(\theta) = -\sum_{i \rightarrow train}^{All} \left( y^i - h_\theta (x^i)\right) x_j
$$

  • 迭代(1)式時我們必須使用到所有的訓練點(training sets)才能更新下一個,這樣的方式稱之為Batch Gradient Descent。

由於批次迭代(Batch Gradient Descent)把所有的資料算過一遍才會前進一步。可是當資料(訓練)非常多的時候,計算量會變成很大,所以我們會考慮使用mini-batch或隨機迭代(Stochastic Gradient Descent)
概念是把所有的訓練資料分成許多的小量資料(mini-batch),然後先依照這樣的資料更新
$$
\theta_j \rightarrow \theta_j + \sum_{i=1}^{m} \left( y^i - h_\theta (x^i)\right) x_j \tag{2}
$$

  • 式(2)當mini-batch的數量m=1時,即稱為stochastic gradient descent。

算法與概念如圖

利用這樣的算法可以推估

程式碼實做

# my own mini-batch gradient descent 

import random
import math
import numpy as np
import matplotlib.pyplot as plt

class GradientDescent(object):

    def __init__(self,data,theta):
        # theta = [theta0,theta1]

        # data -> [(x1,y1),(x2,y2),...]

    
        x,y = zip(*data)
        self.data = data
        self.x = x
        self.y = y
        self.theta = theta 

    def in_random_order(self):
        '''generator that returns the elements of data in random set'''
        indexes = [i for i,_ in enumerate(self.data)]
        random.shuffle(self.data)
        for i in indexes:
            yield self.data[i]

    def predict(self,mini_batch_size,iter_no,tol,alpha):
        ''' update theta until iter > iter_no or error < tol'''
        error = 1
        iterno = 0

        data_size = len(self.data)
        while iterno <iter_no and error>tol:
            theta_origin = self.theta
            self.in_random_order()
            mini_batches = [self.data[k:k+mini_batch_size] 
                        for k in range(0,data_size,mini_batch_size)]
            for mini_batch in mini_batches:                
                self.update(mini_batch,alpha) # return update theta                

            error = math.sqrt((self.theta[0]-theta_origin[0])**2 + (self.theta[1]-theta_origin[1])**2)            
            print iterno,error
            iterno +=1


    def update(self,mini_batch,alpha):
        x0 =0
        x1 =0                            
        for xi,yi in mini_batch:
            h_theta = self.theta[0] + xi*self.theta[1]
            x0 += alpha*(yi-h_theta)
            x1 += alpha*(yi-h_theta)*xi

        theta_iter0 = self.theta[0] + x0
        theta_iter1 = self.theta[1] + x1
        self.theta = [theta_iter0,theta_iter1]

        
← KNN分類演算法 簡單線性迴歸-Simple Linear Regression →
 
comments powered by Disqus