mlp – Parsa H. Rafsanjani

<font face="XB Zar" size=5>
    <font color=#0000FF size=6>

پیاده‌سازی MLP از پایه

متن گزارش در محیط ژوپیتر محلی (local) به درستی نمایش داده می‌شود، ولی روی گوگل کولب مشکل دارد.
در ابتدا پیاده‌سازی الگوریتم مرتب‌سازی توپولوژیکی (Topological Sort) را قرار داده‌ایم چراکه در تعریف کلاس Variable به آن نیاز خواهیم داشت. متغیر var که نماینده‌ی آخرین رأس گراف محاسباتی است به این الگوریتم داده شده و در نتیجه‌ی آن لیستی مرتب شده از رئوس گراف محاسباتی با فراخوانی متد top_sort خروجی داده می‌شود.
الگوریتم اصلی در متد بازگشتی topsort_helper آمده است. این تابع یک رأس از گراف محاسباتی را دریافت کرده و بررسی می‌کند که آیا قبلاً آن را بازدید کرده است یا خیر. چنانچه آن را بازدید نکرده باشد، در ادامه آن را بازدید کرده (یعنی به لیست مربوط به رئوس بازدید شده اضافه‌اش می‌کند) و اگر این رأس یکی از برگ‌های گراف باشد، آن را به لیست نهایی اضافه می‌کند. در غیر این صورت به طور بازگشتی والدهای این رأس را مرتب‌سازی کرده و در نهایت خود رأس را هم به لیست نهایی اضافه می‌کند.
در اینجا از کلمه‌ی والد به جای فرزندان یک رأس استفاده می‌کنیم، چراکه در ساختار گراف محاسباتی که در ادامه آن را مورد بررسی قرار خواهیم داد، هر رأس غیر برگ از دو رأس دیگر ایجاد می‌شود و رأس ایجاد شده نشانگرهایی به رئوس والد خواهد داشت، نه رئوس والد به رأس ایجاد شده.

class TopSort:
    def __init__(self, var):
        self.var = var

    def topsort_helper(self, var):
        if var not in self.seen:
            self.seen.add(var)
            if var.is_leaf():
                self.sorted_variables.append(var)
            else:
                for parent in var.parents:
                    self.topsort_helper(parent)
                self.sorted_variables.append(var)

    def top_sort(self):
        self.seen = set()
        self.sorted_variables = []
        self.topsort_helper(self.var)
        return self.sorted_variables

<font face="XB Zar" size=5>
    <p></p>
    در ادامه کلاس <code>Variable</code> را تعریف خواهیم کرد که نماینده‌ی رئوس گراف محاسباتی است.
    هر شئ از این کلاس مقدار متغیر (<code>value</code>)، والدین متغیر (<code>parents</code>) و مشتق متغیری که روی آن متد <code>backward</code> فراخوانده می‌شود نسبت به خود این متغیر (<code>grad</code>) را در خود نگهداری می‌کند که مقدار اولیه‌ی آن هم برابر $0$ است و در هر بار محاسبه‌ی گرادیان باید مجدداً تنظیم شود.
    <br>
    متد <code>add_parent</code> در زمان ایجاد یک رأس جدید برای اینکه بتوانیم یال‌های گراف محاسباتی را تشکیل دهیم استفاده شده و در واقع والدهای رأس جدید را به لیست والدهای آن اضافه می‌کند.
    <br>
    چهار عملگر ضرب، جمع، تفریق و به توان رساندن برای این کلاس بازنویسی شده و در هر کدام رأس جدیدی که در خود نشانگرهایی به والد(های) خود دارند ایجاد می‌شود.
    در روابط زیر $v_1$ متناظر با <code>self</code>، $v_2$ متناظر با <code>other</code> و $v_3$ متناظر با <code>new_variable</code> است و در نتیجه <code>v1.grad</code> مقدار $\frac{\partial v}{\partial v_1}$، <code>v2.grad</code> مقدار $\frac{\partial v}{\partial v_2}$ و <code>v3.grad</code> $\frac{\partial v}{\partial v_3}$ را در خود ذخیره می‌کند که $v$ همان متغیری است که متد <code>backward</code> روی آن فراخوانی شده و می‌خواهیم گرادیانش را محاسبه کنیم.
    <br>
    در ضرب، متغیر جدید $v_3$ از ضرب دو متغیر قبلی $v_1$ و $v_2$ ایجاد می‌شود.
    پس کلید <code>backward_</code> طبق رابطه‌ی زیر پیاده‌سازی شده است:
    $$
    \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 v_2)}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} (v_2)
    $$
    و به طور مشابه:
    $$
    \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_2} \\
    \Rightarrow \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 v_2)}{\partial v_2} \\
    \Rightarrow \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} (v_1)
    $$
    <br>
    در جمع، متغیر جدید $v_3$ از جمع دو متغیر قبلی $v_1$ و $v_2$ ایجاد می‌شود و
    لذا کلید <code>backward_</code> طبق رابطه‌ی زیر پیاده‌سازی شده است:
    $$
    \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 + v_2)}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} (1)
    $$
    و به طور مشابه:
    $$
    \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_2} \\
    \Rightarrow \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 + v_2)}{\partial v_2} \\
    \Rightarrow \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} (1)
    $$
    در تفریق، متغیر جدید $v_3$ از تفریق دو متغیر قبلی $v_1$ و $v_2$ ایجاد می‌شود و
    بنابراین کلید <code>backward_</code> طبق رابطه‌ی زیر پیاده‌سازی شده است:
    $$
    \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 - v_2)}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} (1)
    $$
    و به طور مشابه:
    $$
    \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_2} \\
    \Rightarrow \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 - v_2)}{\partial v_2} \\
    \Rightarrow \frac{\partial v}{\partial v_2} = \frac{\partial v}{\partial v_3} (-1)
    $$
    در توان رساندن، متغیر جدید $v_3$ از به توان رساندن متغیر قبلی $v_1$ به توان عددی مثل $p$ ایجاد می‌شود و
    لذا کلید <code>backward_</code> طبق رابطه‌ی زیر پیاده‌سازی شده است:
    $$
    \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial v_3}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} \frac{\partial (v_1 ^ p)}{\partial v_1} \\
    \Rightarrow \frac{\partial v}{\partial v_1} = \frac{\partial v}{\partial v_3} (p v_1 ^ {p - 1})
    $$
    متد <code>is_leaf</code> در صورتی که متغیر (در واقع رأس گراف محاسباتی) برگ باشد <code>True</code> و در غیر این صورت <code>False</code> برمی‌گرداند.
    <br>
    متد <code>backward</code> گرادیان متغیر ورودی را نسبت به تمامی متغیرها یا همان رئوس گراف محاسباتی به دست می‌آورد. به این صورت که ابتدا گرادیان خود متغیر را تنظیم می‌کند و آن را برابر $1$ قرار می‌دهد، چراکه $\frac{\partial v}{\partial v} = 1$.
    در ادامه یک بار مرتب‌سازی توپولوژیکی را با شروع از خود متغیر انجام داده و لیست خروجی را برعکس کرده و با پیمایش روی متغیرهای داخل لیست خروجی مرتب‌سازی شده، کلید <code>backward_</code> هر متغیر را صدا می‌زند.
    <br>
    چون از مسیرهای متفاوت می‌توان به یک رأس گراف رسید، در کلیدهای <code>backward_</code> داخل هر عملیات مشتق محاسبه شده را با مشتق قبلی جمع می‌کنیم.
</font>

class Variable:
    def __init__(self, value):
        self.value = value
        self.parents = []
        self.grad = 0
        self._backward = lambda : None

    def add_parent(self, other_variable):
        self.parents.append(other_variable)

    def __mul__(self, other):
        other = other if isinstance(other, Variable) else Variable(other)

        new_variable = Variable(self.value * other.value)
        new_variable.add_parent(self)
        new_variable.add_parent(other)

        def backward():
            self.grad += new_variable.grad * other.value
            other.grad += new_variable.grad * self.value

        new_variable._backward = backward

        return new_variable

    def __add__(self, other):
        other = other if isinstance(other, Variable) else Variable(other)

        new_variable = Variable(self.value + other.value)
        new_variable.add_parent(self)
        new_variable.add_parent(other)

        def backward():
            self.grad += new_variable.grad * 1
            other.grad += new_variable.grad * 1

        new_variable._backward = backward

        return new_variable

    # this is added for `sum` function to work properly
    def __radd__(self, other):
        return self.__add__(other)

    def __sub__(self, other):
        other = other if isinstance(other, Variable) else Variable(other)

        new_variable = Variable(self.value - other.value)
        new_variable.add_parent(self)
        new_variable.add_parent(other)

        def backward():
            self.grad += new_variable.grad * 1
            other.grad += new_variable.grad * (-1)

        new_variable._backward = backward

        return new_variable

    def __pow__(self, power):
        new_variable = Variable(self.value ** power)
        new_variable.add_parent(self)

        def backward():
            self.grad += new_variable.grad * power * (self.value ** (power - 1))

        new_variable._backward = backward

        return new_variable

    def is_leaf(self):
        return not self.parents

    def backward(self):
        self.grad = 1
        topsort = TopSort(self)
        reverse_sorted_variables = topsort.top_sort()[::-1]
        for var in reverse_sorted_variables:
            var._backward()

<font face="XB Zar" size=5>
    <p></p>
    در ادامه دو کلاس قبلی را مطابق <a href="https://w3.cs.jmu.edu/spragunr/CS445_S23/lectures/autodiff/autodiff.pdf">این جزوه</a> بررسی کرده‌ایم.
    <br>
    در اینجا ابتدا متغیرها را تشکیل می‌دهیم:
</font>

w = Variable(1)
x = Variable(2)
y = Variable(3)
l0 = w * x
l1 = l0 - y
l2 = l1 ** 2
l3 = w ** 2
l4 = l2 + l3

<font face="XB Zar" size=5>
    <p></p>
    حال الگوریتم مرتب‌سازی توپولوژیکی را فراخوانی کرده و مقدار هر متغیر را چاپ می‌کنیم که همان طور که مشاهده می‌شود مطابق ترتیبی است که در جزوه‌ی مذکور آمده است.
</font>

topsort = TopSort(l4)
for var in topsort.top_sort():
    print(var.value)

<font face="XB Zar" size=5>
    <p></p>
    حال متد <code>backward</code> را روی متغیر <code>l4</code> فراخوانی کرده و مشتقات جزئی هر متغیر را چاپ می‌کنیم که همگی صحیح و مطابق آنچه که در جزوه آمده است می‌باشد.
</font>

l4.backward()

print(f'dl4/l4 = {l4.grad}')
print(f'dl4/l3 = {l3.grad}')
print(f'dl4/l2 = {l2.grad}')
print(f'dl4/l1 = {l1.grad}')
print(f'dl4/l0 = {l0.grad}')
print(f'dl4/dw = {w.grad}')
print(f'dl4/dx = {x.grad}')
print(f'dl4/dy = {y.grad}')

dl4/l4 = 1
dl4/l3 = 1
dl4/l2 = 1
dl4/l1 = -2
dl4/l0 = -2
dl4/dw = -2
dl4/dx = -2
dl4/dy = 2

<font face="XB Zar" size=5>
    <p></p>
    در ادامه کلاس <code>Neuron</code> که نماینده‌ی نورون‌های شبکه‌ی عصبی است را پیاده‌سازی کرده‌ایم.
    این کلاس وزن‌ها و بایاس خود را به صورت پارامتر دریافت می‌کند و خروجی را به صورت زیر محاسبه می‌کند:
    $$
    z = \sigma(w_0 + w_1 x_1 + w_2 x_n + ... + w_n x_n) = w_0 + w_1 x_1 + w_2 x_n + ... + w_n x_n
    $$
    که $w_0$ بایاس، $w_i$ها $(1 \leq i \leq n)$ وزن‌ها و $x_i$ها ورودی‌های نورون از لایه‌ی قبلی بوده و تابع فعال‌ساز هم خطی در نظر گرفته شده است.
</font>

class Neuron:
    def __init__(self, weights):
        self.weights = weights

    def forward(self, inputs):
        z = Variable(self.weights[0].value)
        for input_var, weight in zip(inputs, self.weights[1:]):
            z += weight * input_var
        return z

    def __call__(self, x):
        return self.forward(x)

<font face="XB Zar" size=5>
    <p></p>
    در ادامه کلاس <code>Layer</code> که همان لایه‌های شبکه‌ی عصبی ما را تشکیل می‌دهد پیاده‌سازی شده است.
    این کلاس با دریافت تعداد ورودی‌های لایه‌ی قبلی یعنی <code>input_size</code> و اندازه‌ی لایه که همان تعداد نورون‌های داخل لایه است (یعنی <code>layer_size</code>)، وزن‌ها و بایاس داخل هر نورون را با مقداردهی اولیه‌ی رندوم از بازه‌ی $(-1, 1)$ تشکیل داده و قادر است خروجی لایه را به صورت لیستی از خروجی‌های هر نورون لایه بازگرداند.
    با این حال اگر خروجی تک متغیره بود، آن را به صورت یک متغیر و نه لیستی از یک متغیر بازمی‌گرداند.
</font>

import random

class Layer:
    def __init__(self, input_size, layer_size):
        self.neurons = []
        for _ in range(layer_size):
            weights = [Variable(random.uniform(-1, 1)) for _ in range(input_size + 1)]

            self.neurons.append(Neuron(weights))

    def forward(self, inputs):
        outputs = [neuron(inputs) for neuron in self.neurons]
        return outputs[0] if len(outputs) == 1 else outputs

    def __call__(self, x):
        return self.forward(x)

<font face="XB Zar" size=5>
    <p></p>
    کلاس <code>MLP</code> ورودی‌های شبکه و لیستی از تعداد نورون‌های هر لایه را دریافت کرده و شبکه را با وزن‌ها و بایاس اولیه تشکیل می‌دهد.
    <br>
    متد <code>parameters</code> با پیمایش روی کل لایه‌های شبکه و همچنین پیمایش روی نورون‌های هر لایه، وزن‌ها و بایاس هر نورون را به یک لیست اضافه کرده و در نهایت لیست نهایی را خروجی می‌دهد.
</font>

class MLP:
    def __init__(self, input_size, layer_sizes):
        self.layers = []
        # ip_size = input_size
        for layer_size in layer_sizes:
            self.layers.append(Layer(input_size, layer_size))
            input_size = layer_size

    def forward(self, x):
        # outputs = None
        # inputs = x
        # for layer in self.layers:
            # outputs = layer.get_outputs(inputs)
            # inputs = outputs
        # return outputs
        for layer in self.layers:
            x = layer(x)
        return x

    def __call__(self, x):
        return self.forward(x)

    def parameters(self):
        weights = []
        for layer in self.layers:
            for neuron in layer.neurons:
                for weight in neuron.weights:
                    weights.append(weight)
        return weights

<font face="XB Zar" size=5>
    <p></p>
    کلاس <code>Optimizer</code> پارامترهای مدل، یعنی تمام وزن‌ها و بایاس‌های آن را به همراه نرخ یادگیری <code>lr</code> یا همان learning rate دریافت کرده و از این طریق پارامترهای مدل را متناسباً بروزرسانی می‌کند.
    <br>
    متد <code>zero_grad</code> مشتق همه‌ی متغیرها را صفر کرده تا در هر ایپاک (epoch) مشتقات قبلی روی مشتقات جدید تأثیر نگذارند.
    <br>
    همچنین متد <code>step</code> به ازای هر پارامتر $w_i (0 \leq i \leq n)$ مقدار جدید را به صورت زیر به دست می‌آورد:
    $$
    w_i = w_i - \eta \frac{\partial loss}{\partial w_i}
    $$
    که $\eta$ همان نرخ یادگیری و $loss$ تابع خطا می‌باشد.
</font>

class Optimizer:
    def __init__(self, parameters, lr):
        self.parameters = parameters
        self.lr = lr

    def zero_grad(self):
        for parameter in self.parameters:
            parameter.grad = 0

    def step(self):
        for parameter in self.parameters:
            parameter.value -= self.lr * parameter.grad

<font face="XB Zar" size=5>
    <p></p>
    دیتاست فرضی را مطابق آنچه که در ویدیوی کارگاه گفته شد به صورت زیر تعریف می‌کنیم:
</font>

X = [
    [2.0, 3.0, -1.0],
    [3.0, -1.0, 0.5],
    [0.5, 1.0, 1.0],
    [1.0, 1.0, -1.0]
]

y = [1.0, -1.0, -1.0, 1.0]

<font face="XB Zar" size=5>
    <p></p>
    در ادامه مدلی فرضی مطابق ساختاری که در راهنما خواسته شده به صورت زیر ایجاد می‌کنیم:
</font>

input_size = 3
layer_sizes = [2, 3, 1]
model = MLP(input_size, layer_sizes)

<font face="XB Zar" size=5>
    <p></p>
    یک <code>Optimizer</code> با نرخ یادگیری $0.01$ مطابق ویدیوی کارگاه ایجاد می‌کنیم:
</font>

optim = Optimizer(model.parameters(), 0.01)

<font face="XB Zar" size=5>
    <p></p>
    تابع <code>criterion</code> با دریافت دو بردار $\hat{y}$ و $y$، تابع خطای MSE را به صورت زیر حساب کرده و به شکل یک <code>Variable</code> خروجی می‌دهد.
    $$
    loss = \sum_{i=1}^n (\hat{y_i} - y_i) ^ 2
    $$
    این تابع مطابق با ویدیوی کارگاه آورده شده است.
    واضح است تقسیم بر $n$ تأثیر چندانی در کلیت الگوریتم ندارد، چرا که به صورت یک ثابت در رابطه ظاهر می‌شود.
</font>

def criterion(y_hats, y):
    return sum([(y_hat - _y) ** 2 for y_hat, _y in zip(y_hats, y)])

<font face="XB Zar" size=5>
    <p></p>
    در پایان الگوریتم یادگیری را به صورت زیر مطابق راهنما و ویدیوی کارگاه پیاده‌سازی کرده و مشاهده می‌کنیم که در هر گام مقدار تابع خطا کوچکتر می‌شود.
</font>

n_epochs = 20

for epoch in range(n_epochs):
    # y_hats = []
    # for x in X:
    #     y_hats.append(model(x))
    y_hats = [model(x) for x in X]

    # loss = Variable(0)
    # n = len(X)
    # for j in range(n):
    #     loss += (y_hats[j] - y[j]) ** 2
    loss = criterion(y_hats, y)

    optim.zero_grad()

    loss.backward()

    optim.step()

    print(f'epoch: {epoch + 1}, loss: {loss.value}')

epoch: 1, loss: 4.552400449787093
epoch: 2, loss: 3.4763025697606276
epoch: 3, loss: 3.3217630691270528
epoch: 4, loss: 3.1686015470939055
epoch: 5, loss: 2.993653949789069
epoch: 6, loss: 2.796027000052853
epoch: 7, loss: 2.578528681901156
epoch: 8, loss: 2.3472344739181805
epoch: 9, loss: 2.111613145444208
epoch: 10, loss: 1.8837361175374663
epoch: 11, loss: 1.6762144484308275
epoch: 12, loss: 1.499217768987232
epoch: 13, loss: 1.3577814466979965
epoch: 14, loss: 1.2508725665547584
epoch: 15, loss: 1.1727662279565987
epoch: 16, loss: 1.1157832027348333
epoch: 17, loss: 1.0727709336227516
epoch: 18, loss: 1.038360951710682
epoch: 19, loss: 1.0090841751648687
epoch: 20, loss: 0.9829228588113506