Divide and Conquer

ความรู้จาก Law of Large Number และ Central Limit Theorem บอกว่าถ้ามีข้อมูลจำนวนมากพอ ข้อมูลนั้นควรมีการแจกแจงแบบ Normal Distribution หรือ Gaussian [1][2][3] และการแบ่งข้อมูลออกเป็นส่วนย่อย แต่ละส่วนย่อยก็ควรจะมีการแจกแจงแบบ Normal  Distribution ด้วยเช่นกัน โดยมีข้อแม้ว่าข้อมูลต้องมาจากประชากร (Population) เดียวกัน

มองมุมกลับหากเราไม่สามารถจัดเก็บข้อจำนวนมากในคราวเดียวได้ การทยอยเก็บข้อมูลเข้ามาประมวลผลที่ละส่วนแล้วเก็บไว้ ก็น่าจะสามารถทำได้โดยที่สาระในข้อมูลจะเปลี่ยนไปไม่มากนักเมื่อเทียบกับการเก็บข้อมูลจำนวนมากมาในคราวเดียว

การ merge หรือรวมกลุ่มตัวอย่างสองกลุ่มที่ต่างก็มี \( \large \bar{x},\sigma^2\) ของตัวเอง จะทำให้ได้ค่าของ \( \large \bar{x},\sigma^2\) ใหม่ขึ้นมา โดยที่จำนวนตัวอย่างจะเพิ่มขึ้น เราสามารถทำแบบนี้เรื่อย ๆ

\( \large \bar{x}_{new} = \frac{n_1\bar{x_1} + n_2\bar{x_2}}{n_1+n_2} \dashrightarrow(1) \)

\( \large \sigma_{new}^2 = \frac{n_1(\sigma_1^2+\bar{x_{1}}^2-\bar{x_3}^2)+n_2(\sigma_2^2+\bar{x_{2}}^2-\bar{x_3}^2)}{n_1+n_2} \dashrightarrow(2)\)

แทนที่ \( \bar{x_3}\) ด้วย (1)

import math

class Gaussian():
    def __init__(self,mean,var,size):
        '''
        Reference :
        https://en.m.wikipedia.org/wiki/Mixture_model
        https://math.stackexchange.com/questions/1112866/product-of-two-gaussian-pdfs-is-a-gaussain-pdf-but-product-of-two-gaussan-varia
        https://ccrma.stanford.edu/~jos/sasp/Product_Two_Gaussian_PDFs.html
        '''
        self._mean = mean
        self._var = var
        self._size = size

    def __add__(self,g):
        # g is another Gaussian with mean, varience
        # Gaussian + Gaussian 
        # mu = mu1 + mu2
        # var = var1 + var2
        m = self.mean() + g.mean()
        v = self.var() + g.var()
        return Gaussian(m,v)
    
    def __mul__(self,g):
        # Gaussian x Gaussian
        # mu = (var1*mu2 + var2*mu1)/(var1+var2)
        # var = (var1*var2)/(var1+var2)
        var2 = g.var()
        var1 = self.var() + 0.00000000001 # to avoid devided by zero
        mu1 = self.mean()
        mu2 = g.mean()
        mu = (var1*mu2 + var2*mu1)/(var1+var2)
        var = (var1*var2)/(var1+var2)
        return Gaussian(mu,var)
    
    def var(self):
        return self._var
    
    def std(self):
        return np.sqrt(self.var())
    
    def mean(self):
        return self._mean
    
    def size(self):
        return self._size
    
    
def combine(g1,g2):
    # to mix 2 samples together to get new one
    new_mean = (g1.mean()*g1.size() + g2.mean()*g2.size())/(g1.size()+g2.size()) #---(1)
    t1 = g1.size()*(g1.var()+math.pow(g1.mean(),2)- math.pow(new_mean,2)) # --- (2)
    t2 = g2.size()*(g2.var()+math.pow(g2.mean(),2)- math.pow(new_mean,2)) # --- (3)
    new_var = (t1+t2)/(g1.size()+g2.size())
    new_size=g1.size()+g2.size()
    
    return Gaussian(new_mean,new_var,new_size)
    

เอกสารอ้างอิง[1] https://en.wikipedia.org/wiki/Law_of_large_numbers#Borel's_law_of_large_numbers
[2] https://en.wikipedia.org/wiki/Central_limit_theorem
[3] https://en.wikipedia.org/wiki/Normal_distribution