You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Trong bài trước chúng ta đã tìm hiểu về matrix calculus với denominator layout. Các bạn có thể xem lại tại đây. Thực tế rằng việc lấy đạo hàm của hàm phức hợp theo cách biểu diễn này thường khá phức tạp, không tự nhiên vì khi biến đổi cần phải lấy transpose. Trong mạng NN đi từ layer này qua layer khác phải trải qua nhiều bước, tạm gọi là nhiều "hàm" và việc lấy đạo hàm theo cách này mình cảm thấy khá phức tạp và không tường minh. Do đó trong bài này chúng ta sẽ quay trở lại với numerator layout. Mình có tìm hiểu một số tài liệu thì thấy đạo hàm theo vector hay matrix thường được diễn giải theo cách này, rất tường minh và tự nhiên khi có hàm phức hợp.
Chia sẻ một chút, mình mất một thời gian để tìm hiểu về matrix calculus. Thực tế có hai quy ước về lấy đạo hàm là numerator layout (Jacobian formulation) và denominator layout (Hessian formulation), nhiều tài liệu không ghi rõ và khi đọc nhiều tài liệu sẽ gây nhầm lẫn.
Trong bài này chúng ta sẽ dùng theo quy ước numerator layout và tìm hiểu về backpropagation trong mạng NN.
Chúng ta có vector $\mathbf{x}$ có kích thước $n \times 1$:
Chúng ta có thể suy ra công thức này từ các công thức trên như sau. Từ công thức (1) gradient của $\mathbf{f}$ theo vector $\mathbf{x}$ là một vector hàng.
$$\frac{\partial \mathbf{f}}{\partial \mathbf{x}} = \left [ \frac{\partial \mathbf{f}}{\partial x_1} ~~\frac{\partial \mathbf{f}}{\partial x_2} \dots \frac{\partial \mathbf{f}}{\partial x_n} \right ] ~~~~~ (4) $$
Đạo hàm của một vector theo một số vô hướng là vector cột như sau.
Thay công thức trên vào công thức (4) chúng ta sẽ nhận được (3). Không phức tạp quá phải không nào?
Ở đây chúng ta cũng có khái niệm Jacobian của $\mathbf{f}(\mathbf{x}): \mathbb{R}^n \rightarrow \mathbb{R}^m$ là ma trận các đạo hàm riêng bậc một có kích thước $m \times n$.
Trường hợp đặc biệt $m=1$ chúng ta có Jacobian của $f(\mathbf{x})$ là một vector hàng (ma trận với kích thước $1 \times n$) như công thức (1).
Ví dụ:
Một số ví dụ
Ví dụ 1
Cho hàm số $\mathbf{f}(\mathbf{x}) = \mathbf{a}^T\mathbf{x}$. Khi đó dễ dàng nhận thấy $\nabla_\mathbf{x} (\mathbf{a}^T\mathbf{x}) = \mathbf{a}^T $, tương tự cũng có $\nabla_\mathbf{x} (\mathbf{x}^T\mathbf{a}) = \mathbf{a}^T $
Ví dụ s
Cho hàm số $\mathbf{f}(\mathbf{x}) = \mathbf{A}\mathbf{x}$, trong đó $\mathbf{f}(\mathbf{x}) \in \mathbb{R}^m$, $\mathbf{A} \in \mathbb{R}^{m \times n}$, $\mathbf{x} \in \mathbb{R}^n$. Xác định gradient $\nabla_\mathbf{x} \mathbf{f} = d\mathbf{f} / d\mathbf{x}$
Chú ý: ở đây khi ghi $\mathbb{R}^n$ chúng ta hiểu mặc định đó là vector có $n$ chiều, vector cột hay matrix có kích thước $\mathbb{R}^{n \times 1}$.
Bởi vì $\mathbf{f}(\mathbf{x}): \mathbb{R}^n \rightarrow \mathbb{R}^m$ nên theo công thức (3), $\nabla_\mathbf{x} \mathbf{f}$ sẽ có kích thước là $\mathbb{R}^{m \times n}$.
Theo đề bài chúng ta sẽ có $f_i(\mathbf{x}) = \sum_{j=1}^{n}A_{ij}x_j \Rightarrow \frac{\partial f_i}{\partial x_j} = A_{ij}$
Chain rule trong numerator layout thật tự nhiên phải không nào. Công thức này nhìn hơi khác một chút do với công thức chúng ta thường thấy trong các khóa học ML. Lý do bởi vì trong các khóa ML sử dụng denominator layout. Như định nghĩa bên trên chúng ta có $\frac{\partial L}{\partial \mathbf{w}}$ là một vector hàng giống với những gì nhận được bên vế phải. Tuy nhiên trong NN hay để dạng vector cột nên kết quả cuối cùng được chuyển về vector cột. Có thể viết lại thành:
Để đơn giản đặt $y = f(x)$ và viết $\frac{\partial y}{\partial x}$ cho đạo hàm của $y$ theo $x$. Kí hiệu $\frac{\partial y}{\partial x}$ cũng đã nhấn mạnh tốc độ thay đổi của $y$ theo $x$. Nếu $x$ thay đổi một lượng $\varepsilon = \Delta x$ thì $y$ sẽ thay đổi một lượng $\varepsilon \frac{\partial y}{\partial x}$. CHúng ta có thể ghi lại như sau:
$$
x \rightarrow x + \Delta x \Rightarrow y \rightarrow \approx y + \frac{\partial y}{\partial x} \Delta x
$$
Chain rule cho phép chúng ta tính đạo hàm của hàm phức hợp (kết hợp nhiều hàm với nhau). Ví dụ $f, g: \mathbb{R} \rightarrow \mathbb{R}$ và $y=f(x)$, $z = g(y)$. Chúng ta có thể ghi lại $z = (g \circ f)(x)$ và vẽ computational graph như sau:
$$ x \overset{f}{\rightarrow} y \overset{g}{\rightarrow} z$$
$$
x \rightarrow x + \Delta x \Rightarrow y \rightarrow \approx y + \frac{\partial y}{\partial x} \Delta x
$$
$$
y \rightarrow y + \Delta y \Rightarrow z \rightarrow \approx z + \frac{\partial z}{\partial y} \Delta y
$$
Kết hợp 2 điều này chúng ta có thể tính được ảnh hưởng của $x$ lên $z$. Nếu $x$ thay đổi $\Delta x$ thì $y$ sẽ thay đổi $\frac{\partial y}{\partial x} \Delta x$ và chúng ta có $\Delta y = \frac{\partial y}{\partial x} \Delta x$. Nếu $y$ thay đổi thì $z$ sẽ thay đổi một lượng $\frac{\partial z}{\partial y} \Delta y = \frac{\partial z}{\partial y} \frac{\partial y}{\partial x} \Delta x $$
Gradient: vector in, scalar out
Đầu vào là một vector, đầu ra là một số vô hướng.
Cho hàm số $f(\mathbf{x}): \mathbb{R}^n \rightarrow \mathbb{R}$. Đạo hàm của $f$ tạo điểm $\mathbf{x} \in \mathbb{R}^n$ được gọi là gradient và được xác định như sau:
Gradient $\nabla_\mathbf{x} f(\mathbf{x}) \in \mathbb{R}^n$ cũng là một vector. Đặt $y = f(\mathbf{x})$ chúng ta sẽ có:
$$
\mathbf{x} \rightarrow \mathbf{x} + \Delta \mathbf{x} \Rightarrow y \rightarrow \approx y + \frac{\partial y}{\partial \mathbf{x}} \Delta \mathbf{x}
$$
Ở đây $\frac{\partial y}{\partial \mathbf{x}} \in \mathbb{R}^n $ là một vector hàng. $\frac{\partial y}{\partial \mathbf{x}} \Delta \mathbf{x}$ ở đây là dot product để nhận được số vô hướng.
Nếu tưởng tượng $\Delta \mathbf{x}$ là $i^{th}$ basis vector, điều này tương đương với tọa độ $i^{th}$ của $\varepsilon = \Delta \mathbf{x}$ là 1, các tọa còn lại bằng 0. Dot product $\frac{\partial y}{\partial \mathbf{x}} \Delta \mathbf{x}$ đơn giản là tọa độ $i^{th}$ của $\frac{\partial y}{\partial \mathbf{x}}$. Do đó tọa độ $i^{th}$ của$\frac{\partial y}{\partial \mathbf{x}}$ sẽ cho chúng ta biết lượng $y$ thay đổi nếu chúng ta dịch chuyển $\mathbf{x}$ theo trục tọa độ $i^{th}$.
Ma trận $\frac{\partial \mathbf{y}}{\partial \mathbf{x}}$ là ma trận $m \times n$, $\Delta \mathbf{x}$ là vector có $n$ phân tử, do đó dot product$\frac{\partial \mathbf{y}}{\partial \mathbf{x}} \Delta \mathbf{x}$ là tích ma trận với vector ta nhận được vector có $m$ phần tử.
Chain rule có thể mở rộng cho trường hợp vector bằng cách sử dụng Jacobian. Giả sử $\mathbf{f}: \mathbb{R}^n \rightarrow \mathbb{R}^m$ và $\mathbf{g}: \mathbb{R}^m \rightarrow \mathbb{R}^k$. $\mathbf{x} \in \mathbb{R}^n$, $\mathbf{y} \in \mathbb{R}^m$ và $\mathbf{z} \in \mathbb{R}^k$ với $\mathbf{y} = \mathbf{f}(\mathbf{x})$ và $\mathbf{z} = \mathbf{g}(\mathbf{y}$. Chúng ta cũng có computational graph như sau:
Mỗi thành phần bây giờ là ma trận. $\frac{\partial \mathbf{z}}{\partial \mathbf{y}}$ có kích thước $k \times m$, $\frac{\partial \mathbf{y}}{\partial \mathbf{x}}$ có kích thước $m \times n$, $\frac{\partial \mathbf{z}}{\partial \mathbf{x}}$ có kích thước $k \times n$. Vế phải là matrix multiplication.
Generalized Jacobian: tensor in, tensor out
Nhiều phép toán trong DL nhận vào tensor và trả về tensor. Ví dụ ảnh thường được biểu diễn dưới dạng tensor 3 chiều, do đó chúng ta sẽ đi phét triển đạo hàm để tương thích với các phép tính trên tensor.
Giả sử có hàm $f: \mathbb{R}^{n_1 \times \dots \times n_{d_x}} \rightarrow \mathbb{R}^{m_1 \times \dots \times m_{d_y}}$. Input của hàm $f$ là $d_x$ - dimensional tensor có shape $n_1 \times \dots \times n_{d_x}$, output là $d_y$ - dimensional tensor có shape $m_1 \times \dots \times m_{d_y}$. Đặt $y=f(x)$, khi đó $\frac{\partial y}{\partial x}$ là generalized Jacobian và nó có shape là:
Chú ý: Ở đây do tensor nhiều chiều nên kí hiệu chúng là $y=f(x)$ không có in đậm ở đây. Tuy nhiên khi lấy đạo hàm cần phải để ý đến bản chất của hàm và của biến được lấy đạo hàm là vector, matrix, tensor hay scalar để thực hiện chính xác.
Chúng ta tách chiều của $\frac{\partial y}{\partial x}$ thành 2 nhóm:
nhóm 1 khớp với chiếu của $y$
nhóm 2 khớp với chiếu của $x$
Với việc nhóm chiều như này chúng ta có thể nghĩ generalized Jacobian là ma trân với "row" có shape giống với $y$ và "column" có shape giống $x$.
Giả sử $i \in \mathbb{Z}^{d_y}$ và $j \in \mathbb{Z}^{d_x}$ là các vector chỉ số, khi đó có thể ghi:
Ở đây $y_i$ và $x_j$ là các số vô hướng ($y_i$ giống như lấy giá trị cảu $y$ theo ở vị trí i - vector các chỉ số). Do đó $\frac{\partial y_i}{\partial x_j}$ là số vô hướng. Giống như Jacobian tiêu chuẩn, generalized Jacobian cho chúng ta biết tốc độ thay đổi giữa tất cả thành phần của $x$ và các thành phần của $y$.
$$
x \rightarrow x + \Delta x \Rightarrow y \rightarrow \approx y + \frac{\partial y}{\partial x} \Delta x
$$
$\Delta x$ bây giờ là tensor với shape $n_1 \times \dots \times n_{d_x}$ và $\frac{\partial y}{\partial x}$ là generalized matrix với shape $ (m_1 \times \dots \times m_{d_y}) \times (n_1 \times \dots \times n_{d_x})$. Product $\frac{\partial y}{\partial x} \Delta x$ là generalized matrix-vector multiply, cái này sẽ dẫn đến tensor có shape $(m_1 \times \dots \times m_{d_y})$.
Generalized matrix-vector multiply tuân thủ theo các quy luật giống với phép nhân ma trận - vector truyền thống.
Chú ý ở đây $i$ và $j$ không phải số vô hướng mà là vectors các chỉ số. Trong công thức trên $\left ( \frac{\partial y}{\partial x} \right )_{j,:}$ là $j^{th}$ "row" của generalized matrix $\left ( \frac{\partial y}{\partial x} \right )$ - đây là tensor có shape giống với $x$. Ở đây cũng sử dụng quy ước dot product của hai tensors có cùng shape là element-wise product theo sau là lấy tổng (tương tự dot product giữa hai vectors).
Chain rule cho trường hợp tensor-valued function cũng tương tự như vậy. Giả sử $y=f(x)$ và $z=g(y)$, $x$ và $y$ có chiều giống như trên và $z$ có shape là $k_1 \times \dots \times k_{d_z}$.
Sự khác biệt ở đây: $\frac{\partial z}{\partial y}$ là generalized matrix có shape là $ (k_1 \times \dots \times k_{d_z}) \times (m_1 \times \dots \times m_{d_y})$, $\frac{\partial y}{\partial x}$ là generalized matrix có shape là $ (m_1 \times \dots \times m_{d_y}) \times (n_1 \times \dots \times n_{d_x})$. Product $\frac{\partial z}{\partial y} \frac{\partial y}{\partial x}$ là generalized matrix-matrix multiply, tạo ra object có shape là $ (k_1 \times \dots \times k_{d_z}) \times (n_1 \times \dots \times n_{d_x})$. Giống như generalized matrix-vector multiply như trên, generalized matrix-matrix multiply tuân theo các quy luật đại số giống phép trên matrix-matrix truyền thống.
trong đó $i, j, k$ là các vectors chỉ số, $\left ( \frac{\partial z}{\partial y} \right ){i,:}$ là $i^{th}$ "row" của $\left ( \frac{\partial z}{\partial y} \right )$ , $\left ( \frac{\partial z}{\partial y} \right ){:,j}$ là $j^{th}$ "column" của $\left ( \frac{\partial y}{\partial x} \right )$.
Backpropagation with tensors
Khi nói về NN, layer $f$ thường là hàm của inputs $x$ (tensor) và weights $w$, tensor output của layer $y = f(x, w)$. Layer $f$ thường được đưa vào mạng NN lớn với scalar loss $L$.
Trong backpropagation, giả sử chúng ta đã có $\frac{\partial L}{\partial y}$, mục tiêu của chúng ta là tính $\frac{\partial L}{\partial y}$ và $\frac{\partial L}{\partial w}$. Theo chain rule chúng ta có:
Chúng ta sẽ đi tìm generalized Jacobian $\frac{\partial y}{\partial x}$, $\frac{\partial y}{\partial w}$ và sử dụng generalized matrix multiplication để tính $\frac{\partial L}{\partial x}$, $\frac{\partial L}{\partial w}$. Tuy nhiên ở đây có một vấn đề là Jacobian matrices $\frac{\partial y}{\partial x}$ và $\frac{\partial y}{\partial w}$ thường quá lớn để phù hợp với bộ nhớ.
Lấy ví dụ giả sử rằng $f$ là linear layer nhận vào input là minibatch với $n$ vectors, mỗi vector có dimension $d$ và tạo ra output là minibatch $n$ vectors, mỗi vector có dimension $m$. $x$ là ma trận có kích thước $n \times d$, $w$ là weights có kích thước $d \times m$ và hàm số $y = f(x, w) = xw$ là ma trận có kích thước $n \times m$. Cách biểu diễn này giống với một số thư viện làm như Tensorflow. Một số tài liệu có cách biểu diễn khác.
Chú ý: Dễ nhận thấy trong cách biểu diễn này example được coi như một hàng (số cột tương ứng với các features). Cách biểu diễn này ngược với cách biểu diễn trong khóa học DL của Andrew Ng. Không quan trọng cách nào miễn là chúng ta có thể giả quyết vấn đề một cách nhanh gọn.
Khi đó Jacobian $\frac{\partial y}{\partial x}$ có shape là $(n \times m) \times (n \times d)$. Ví dụ trong mạng NN ta có $n=64$, $m=d=4096$ lúc này $\frac{\partial y}{\partial x}$ chứa $64 \cdot 4096 \cdot 64 \cdot 4096 $ giá trị vô hướng, khoảng hơn 68 tỉ số. Nếu sử dụng 32-bit floating point, Jacobian này chiếm khoảng 256 GB memory. Việc lưu trữ và thao tác trên Jacobian này gần như là không thể.
Tuy nhiên trong các mạng NN thông thường chúng ta có thể dẫn ra công thức có thể tính $\frac{\partial L}{\partial y} \frac{\partial y}{\partial x}$ mà không cần tạo Jacobian matrix $\frac{\partial y}{\partial x}$. Trong nhiều trường hợp chúng ta sẽ làm với trường hợp đơn giản sau đó có thể tổng quát hóa lên được.
Ví dụ linear layer $y = f(x,w) = xw$. Đặt $n=1$, $d=2$, $m=3$. Khi đó
Như đã nói ở trên ở đây có 1 example và $y$ được biểu diễn theo hàng.
Trong backpropagation giả sử chúng ta đã có $\frac{\partial L}{\partial y}$ có shape là $(1) \times (n \times m)$. Để thuận tiện cho việc ghi chú chúng ta có thể nghĩ nó là ma trận có shape là $n \times m$. Chúng ta có thể ghi thành:
Chúng ta biết rằng $\frac{\partial L}{\partial x}$ có shape là $(1) \times (n \times d)$, để biểu dễn gradient hay để $\frac{\partial L}{\partial x}$ như ma trận có shape $n \times d$.
Xác định cho từng phần tử chúng ta có:
$$
\frac{\partial L}{\partial x_{1,1}} = \frac{\partial L}{\partial y} \frac{\partial y}{\partial x_{1,1}} ~~~~~~~~ \frac{\partial L}{\partial x_{1,2}} = \frac{\partial L}{\partial y} \frac{\partial y}{\partial x_{1,2}}
$$
Xem các đạo hàm dưới dạng generalized matrices, $\frac{\partial L}{\partial y}$ có shape là $(1) \times (n \times m)$, $\frac{\partial y}{\partial x_{1,1}}$ có shape là $(n \times m) \times 1$ do đó product $\frac{\partial y}{\partial x_{1,1}}$ có shape là $(1) \times (1)$. Nếu chúng ta xem $\frac{\partial L}{\partial y}$ và $\frac{\partial y}{\partial x_{1,1}}$ như các ma trận có kích thước $n \times m$ thì generalized matrix product đơn giản là dot product $\frac{\partial L}{\partial y} \cdot \frac{\partial y}{\partial x_{1,1}} $.