.. raw:: html
Máy Phân rã ma trận
===================
.. raw:: html
Máy phân rã ma trận (*Factorization machines - FM*)
:cite:`Rendle.2010`, được đề xuất bởi Steffen Rendle vào năm 2010, là
một thuật toán học có giám sát, có thể sử dụng trong các tác vụ phân
loại, hồi quy và xếp hạng. Nó nhanh chóng nhận được sự chú ý và trở
thành một phương pháp phổ biến và có ảnh hưởng lớn trong tác vụ dự đoán
và đề xuất. Cụ thể, đây là sự tổng quát hóa của hồi quy tuyến tính và
phân rã ma trận, hơn nữa còn gợi nhớ đến máy vector hỗ trợ với hạt nhân
đa thức. Điểm mạnh của máy phân rã ma trận so với hồi quy tuyến tính và
phân ra mã trận là: (1) Nó có thể mô hình hóa tương tác biến
:math:`\chi` chiều, với :math:`\chi` là bậc của đa thức và thường được
đặt bằng hai. (2) Một thuật toán tối ưu tốc độ cao đi kèm với máy phân
rã ma trận có thể giảm độ phức tạp tính toán từ đa thức về còn tuyến
tính, hiệu quả đặc biệt cao với đầu vào thưa nhiều chiều. Với các lý do
trên, máy phân rã được áp dụng rộng rãi trong ngành quảng cáo hiện đại
và đề xuất sản phẩm. Chi tiết kỹ thuật cũng như cách lập trình được mô
tả dưới đây.
.. raw:: html
Máy Phân rã 2 Chiều.
--------------------
.. raw:: html
Gọi :math:`x \in \mathbb{R}^d` là vector đặc trưng của một mẫu, và
:math:`y` là nhãn tương ứng, nhãn này có thể mang giá trị thực hoặc là
nhãn lớp như lớp nhị phân “nhấp chuột/chưa nhấp chuột”. Mô hình của máy
phân rã ma trận bậc hai được định nghĩa như sau:
.. math::
\hat{y}(x) = \mathbf{w}_0 + \sum_{i=1}^d \mathbf{w}_i x_i + \sum_{i=1}^d\sum_{j=i+1}^d \langle\mathbf{v}_i, \mathbf{v}_j\rangle x_i x_j
.. raw:: html
trong đó :math:`\mathbf{w}_0 \in \mathbb{R}` là hệ số điều chỉnh toàn
cục; :math:`\mathbf{w} \in \mathbb{R}^d` là trọng số của biến thứ
:math:`i`; :math:`\mathbf{V} \in \mathbb{R}^{d\times k}` là embedding
đặc trưng; :math:`\mathbf{v}_i` biểu diễn hàng thứ :math:`i` của
:math:`\mathbf{V}`; :math:`k` là số chiều của nhân tố tiềm ẩn;
:math:`\langle\cdot, \cdot \rangle` là tích vô hướng của hai vector.
:math:`\langle \mathbf{v}_i, \mathbf{v}_j \rangle` mô hình hóa sự tương
tác giữa đặc trưng thứ :math:`i` và thứ :math:`j`. Một số tương tác đặc
trưng có thể dễ dàng hiểu được cho nên chúng có thể được thiết kế bởi
các chuyên gia. Tuy nhiên, đa số các tương tác đặc trưng khác thường ẩn
trong dữ liệu và khó có thể nhận biết. Do đó việc tự động mô hình hóa
tương tác đặc trưng có thể giảm đáng kể công sức thiết kế đặc trưng
(*feature engineering*). Ta có thể thấy rõ rằng hai số hạng đầu tiên
tương ứng với mô hình hồi quy tuyến tính và số hạng cuối cùng là dạng mở
rộng của mô hình phân rã ma trận. Nếu đặc trưng :math:`i` biểu diễn một
sản phẩm và đặc trưng :math:`j` biểu diễn một người dùng, số hạng thứ ba
chính là tích vô hướng giữa embedding người dùng và sản phẩm. Đáng chú ý
là FM cũng có thể khái quát hóa với bậc cao hơn (bậc > 2). Tuy vậy, tính
ổn định số học khi tính toán có thể cản trở khả năng khái quát hóa.
.. raw:: html
Tiêu chuẩn Tối ưu Hiệu quả
--------------------------
.. raw:: html
Tối ưu máy phân rã ma trận theo cách thức trực tiếp dẫn đến độ phức tạp
:math:`\mathcal{O}(kd^2)` do ta phải tính toán toàn bộ các cặp tương
tác. Để giải quyết vấn đề này, ta có thể biến đổi lại số hạng thứ ba của
FM để giảm đáng kể chi phí tính toán xuống còn tuyến tính
(:math:`\mathcal{O}(kd)`). Công thức biến đổi của số hạng tương tác theo
cặp như sau:
.. math::
\begin{aligned}
&\sum_{i=1}^d \sum_{j=i+1}^d \langle\mathbf{v}_i, \mathbf{v}_j\rangle x_i x_j \\
&= \frac{1}{2} \sum_{i=1}^d \sum_{j=1}^d\langle\mathbf{v}_i, \mathbf{v}_j\rangle x_i x_j - \frac{1}{2}\sum_{i=1}^d \langle\mathbf{v}_i, \mathbf{v}_i\rangle x_i x_i \\
&= \frac{1}{2} \big (\sum_{i=1}^d \sum_{j=1}^d \sum_{l=1}^k\mathbf{v}_{i, l} \mathbf{v}_{j, l} x_i x_j - \sum_{i=1}^d \sum_{l=1}^k \mathbf{v}_{i, l} \mathbf{v}_{i, l} x_i x_i \big)\\
&= \frac{1}{2} \sum_{l=1}^k \big ((\sum_{i=1}^d \mathbf{v}_{i, l} x_i) (\sum_{j=1}^d \mathbf{v}_{j, l}x_j) - \sum_{i=1}^d \mathbf{v}_{i, l}^2 x_i^2 \big ) \\
&= \frac{1}{2} \sum_{l=1}^k \big ((\sum_{i=1}^d \mathbf{v}_{i, l} x_i)^2 - \sum_{i=1}^d \mathbf{v}_{i, l}^2 x_i^2)
\end{aligned}
.. raw:: html
Với biến đổi này, độ phức tạp của mô hình giảm đi đáng kể. Hơn nữa, với
đặc trưng thưa, chỉ các phần tử khác 0 cần phải tính toán nên độ phức
tạp toàn phần là tuyến tính với số đặc trưng khác 0.
.. raw:: html
Để học mô hình FM, ta có thể sử dụng mất mát MSE cho tác vụ hồi quy, mất
mát entropy chéo với tác vụ phân loại, và mất mát BPR với tác vụ xếp
hạng. Các bộ tối ưu chuẩn như SGD và Adam đều khả thi cho việc tối ưu.
.. code:: python
from d2l import mxnet as d2l
from mxnet import init, gluon, np, npx
from mxnet.gluon import nn
import os
import sys
npx.set_np()
.. raw:: html
Cách lập trình Mô hình
----------------------
.. raw:: html
Đoạn mã sau đây lập trình mô hình máy phân rã ma trận. Ta có thể thấy rõ
rằng FM bao gồm một khối hồi quy tuyến tính và một khối tương tác đặc
trưng có hiệu suất cao. Ta áp dụng hàm sigmoid lên kết quả cuối cùng do
ta coi dự đoán CTR như một tác vụ phân loại.
.. code:: python
class FM(nn.Block):
def __init__(self, field_dims, num_factors):
super(FM, self).__init__()
num_inputs = int(sum(field_dims))
self.embedding = nn.Embedding(num_inputs, num_factors)
self.fc = nn.Embedding(num_inputs, 1)
self.linear_layer = nn.Dense(1, use_bias=True)
def forward(self, x):
square_of_sum = np.sum(self.embedding(x), axis=1) ** 2
sum_of_square = np.sum(self.embedding(x) ** 2, axis=1)
x = self.linear_layer(self.fc(x).sum(1)) \
+ 0.5 * (square_of_sum - sum_of_square).sum(1, keepdims=True)
x = npx.sigmoid(x)
return x
.. raw:: html
Nạp Tập dữ liệu Quảng cáo
-------------------------
.. raw:: html
Ta sử dụng lớp wrapper dữ liệu CTR từ phần trước để nạp tập dữ liệu
quảng cáo trực tuyến.
.. code:: python
batch_size = 2048
data_dir = d2l.download_extract('ctr')
train_data = d2l.CTRDataset(os.path.join(data_dir, 'train.csv'))
test_data = d2l.CTRDataset(os.path.join(data_dir, 'test.csv'),
feat_mapper=train_data.feat_mapper,
defaults=train_data.defaults)
train_iter = gluon.data.DataLoader(
train_data, shuffle=True, last_batch='rollover', batch_size=batch_size,
num_workers=d2l.get_dataloader_workers())
test_iter = gluon.data.DataLoader(
test_data, shuffle=False, last_batch='rollover', batch_size=batch_size,
num_workers=d2l.get_dataloader_workers())
.. raw:: html
Huấn luyện mô hình
------------------
.. raw:: html
Cuối cùng, ta tiến hành huấn luyện mô hình. Tốc độ học được đặt bằng
0.02 và kích thước embedding mặc định bằng 20. Ta sử dụng bộ tối ưu
``Adam`` và mất mát ``SigmoidBinaryCrossEntropyLoss`` để huấn luyện mô
hình.
.. code:: python
devices = d2l.try_all_gpus()
net = FM(train_data.field_dims, num_factors=20)
net.initialize(init.Xavier(), ctx=devices)
lr, num_epochs, optimizer = 0.02, 30, 'adam'
trainer = gluon.Trainer(net.collect_params(), optimizer,
{'learning_rate': lr})
loss = gluon.loss.SigmoidBinaryCrossEntropyLoss()
d2l.train_ch13(net, train_iter, test_iter, loss, trainer, num_epochs, devices)
.. parsed-literal::
:class: output
loss 0.505, train acc 0.273, test acc 0.269
617939.8 examples/sec on [gpu(0)]
.. figure:: output_fm_vn_07a0f4_7_1.svg
Tóm tắt
-------
.. raw:: html
- FM là một framework tổng quát có thể áp dụng cho nhiều tác vụ khác
nhau như hồi quy, phân loại hay xếp hạng.
- Tương tác/tương giao đặc trưng (*feature interaction/crossing*) rất
quan trọng trong tác vụ dự đoán. Tương tác hai chiều có thể được mô
hình hóa một cách hiệu quả với FM.
Bài tập
-------
.. raw:: html
- Thử FM trên một tập dữ liệu khác như Avazu, MovieLens, and Criteo.
- Thay đổi kích thước embedding để kiểm tra ảnh hưởng của nó lên hiệu
năng, so sánh với khi thay đổi kích thước embedding của phân rã ma
trận.
Thảo luận
---------
- Tiếng Anh: `MXNet `__
- Tiếng Việt: `Diễn đàn Machine Learning Cơ
Bản `__
Những người thực hiện
---------------------
Bản dịch trong trang này được thực hiện bởi:
- Đoàn Võ Duy Thanh
- Đỗ Trường Giang
- Phạm Hồng Vinh
- Lê Khắc Hồng Phúc
- Nguyễn Văn Cường
*Cập nhật lần cuối: 05/10/2020. (Cập nhật lần cuối từ nội dung gốc:
21/07/2020)*