16.3. Phân rã Ma trận

Phân rã ma trận (Matrix Factorization) [Koren et al., 2009] là một trong những thuật toán lâu đời trong các tài liệu về hệ thống đề xuất. Phiên bản đầu tiên của mô hình phân rã ma trận được đề xuất bởi Simon Funk trong một bài blog nổi tiếng, trong đó anh đã mô tả ý tưởng phân rã ma trận tương tác thành các nhân tử. Phân rã ma trận sau đó trở nên phổ biến nhờ cuộc thi Netflix tổ chức năm 2006. Tại thời điểm đó, Netflix, một công ty truyền thông đa phương tiện và cho thuê phim, công bố một cuộc thi nhằm cải thiện hiệu năng hệ thống đề xuất của họ. Đội xuất sắc nhất giúp cải thiện Netflix ở mức cơ sở (baseline) như thuật toán Cinematch lên 10 phần trăm sẽ đoạt giải thưởng là một triệu USD. Do đó, cuộc thi này thu hút rất nhiều sự chú ý trong ngành nghiên cứu hệ thống đề xuất. Cuối cùng, giải thưởng chung cuộc đã thuộc về đội Pragmatic Chaos của BellKor, là đội đã kết hợp của BellKor, Pragmatic Theory và BigChaos (hiện tại bạn chưa cần phải quan tâm đến các thuật toán này). Dù kết quả cuối cùng là một giải pháp kết hợp (tức phối hợp nhiều thuật toán với nhau), thuật toán phân rã ma trận đóng vai trò chủ đạo trong thuật toán kết hợp cuối cùng. Báo cáo kỹ thuật của Giải thưởng Netflix [Toscher et al., 2009] cung cấp giới thiệu chi tiết về mô hình được chấp thuận. Trong phần này, ta sẽ đi sâu vào chi tiết mô hình phân rã ma trận và cách lập trình nó.

16.3.1. Mô hình Phân rã Ma trận

Phân rã ma trận là một lớp trong các mô hình lọc cộng tác. Cụ thể, mô hình này phân tích ma trận tương tác giữa người dùng - sản phẩm (ví dụ như ma trận đánh giá) thành tích hai ma trận có hạng thấp hơn, nhằm nắm bắt cấu trúc hạng thấp trong tương tác người dùng - sản phẩm.

Gọi \(\mathbf{R} \in \mathbb{R}^{m \times n}\) ký hiệu ma trận tương tác với \(m\) người dùng và \(n\) sản phẩm, và các giá trị \(\mathbf{R}\) biểu diễn đánh giá trực tiếp. Tương tác người dùng - sản phẩm được phân tích thành ma trận người dùng tiềm ẩn \(\mathbf{P} \in \mathbb{R}^{m \times k}\) và ma trận sản phẩm tiềm ẩn \(\mathbf{Q} \in \mathbb{R}^{n \times k}\), trong đó \(k \ll m, n\), là kích thước nhân tố tiềm ẩn. Gọi \(\mathbf{p}_u\) ký hiệu hàng thứ \(u\) và của \(\mathbf{P}\)\(\mathbf{q}_i\) ký hiệu hàng thứ \(i\) của \(\mathbf{Q}\). Với một sản phẩm \(i\) cho trước, các phần tử trong \(\mathbf{q}_i\) đo lường mức độ mà sản phẩm đó sở hữu các đặc trưng, ví dụ như thể loại hay ngôn ngữ của một bộ phim. Với một người dùng \(u\) cho trước, các phần tử trong \(\mathbf{p}_u\) đo mức độ ưa thích của người dùng này đối với các đặc trưng tương ứng của các sản phẩm. Các nhân tố tiềm ẩn này có thể là các đặc trưng rõ ràng như đã đề cập trong các ví dụ trên, hoặc hoàn toàn không thể giải thích được. Đánh giá dự đoán có thể được ước lượng như sau

(16.3.1)\[\hat{\mathbf{R}} = \mathbf{PQ}^\top\]

trong đó \(\hat{\mathbf{R}}\in \mathbb{R}^{m \times n}\) là ma trận đánh giá dự đoán và có cùng kích thước với \(\mathbf{R}\). Một vấn đề lớn của cách dự đoán này là độ chệch (bias) của người dùng/sản phẩm không được mô hình hóa. Ví dụ, một số người dùng có thiên hướng đánh giá cao hơn, hoặc một số sản phẩm luôn bị đánh giá thấp hơn bởi chất lượng kém. Các độ chệch này là rất phổ biến trong những ứng dụng thực tế. Để thu được các độ chệch này, số hạng độ chệch riêng biệt cho từng người dùng và sản phẩm được sử dụng. Cụ thể, đánh giá dự đoán của người dùng \(u\) cho sản phẩm \(i\) được tính theo công thức

(16.3.2)\[\hat{\mathbf{R}}_{ui} = \mathbf{p}_u\mathbf{q}^\top_i + b_u + b_i\]

Sau đó, ta huấn luyện mô hình phân rã ma trận bằng cách cực tiểu hóa trung bình bình phương sai số giữa đánh giá dự đoán và đánh giá thực. Hàm mục tiêu được định nghĩa như sau:

(16.3.3)\[\underset{\mathbf{P}, \mathbf{Q}, b}{\mathrm{argmin}} \sum_{(u, i) \in \mathcal{K}} \| \mathbf{R}_{ui} - \hat{\mathbf{R}}_{ui} \|^2 + \lambda (\| \mathbf{P} \|^2_F + \| \mathbf{Q} \|^2_F + b_u^2 + b_i^2 )\]

trong đó \(\lambda\) là tỷ lệ điều chuẩn. Số hạng điều chuẩn \(\lambda (\| \mathbf{P} \|^2_F + \| \mathbf{Q}\|^2_F + b_u^2 + b_i^2 )\) được sử dụng để tránh hiện tượng quá khớp bằng cách phạt độ lớn của các tham số. Cặp \((u, i)\) với \(\mathbf{R}_{ui}\) đã biết được lưu trong tập \(\mathcal{K}=\{(u, i) \mid \mathbf{R}_{ui} \text{đã biết}\}\). Các tham số mô hình có thể được học thông qua một thuật toán tối ưu, ví dụ như hạ gradient ngẫu nhiên hay Adam.

Ảnh minh họa trực quan cho mô hình phân rã ma trận được đưa ra như hình dưới:

../_images/rec-mf.svg

Fig. 16.3.1 Minh họa mô hình phân rã ma trận

Trong phần còn lại, chúng tôi sẽ giải thích cách lập trình cho phân rã ma trận và huấn luyện mô hình trên tập dữ liệu MovieLens.

from d2l import mxnet as d2l
from mxnet import autograd, gluon, np, npx
from mxnet.gluon import nn
import mxnet as mx
npx.set_np()

16.3.2. Cách lập trình Mô hình

Đầu tiên, ta lập trình mô hình phân rã ma trận như mô tả trên. Các nhân tố tiềm ẩn của người dùng và sản phẩm được tạo bằng nn.Embedding. Tham số input_dim là số sản phẩm/người dùng và output_dim là kích thước nhân tố tiềm ẩn (\(k\)). Ta cũng có thể sử dụng nn.Embedding để tạo độ chệch cho người dùng/sản phẩm bằng cách gán output_dim bằng một. Trong hàm forward, id người dùng và sản phẩm được sử dụng để truy vấn tới embedding tương ứng.

class MF(nn.Block):
    def __init__(self, num_factors, num_users, num_items, **kwargs):
        super(MF, self).__init__(**kwargs)
        self.P = nn.Embedding(input_dim=num_users, output_dim=num_factors)
        self.Q = nn.Embedding(input_dim=num_items, output_dim=num_factors)
        self.user_bias = nn.Embedding(num_users, 1)
        self.item_bias = nn.Embedding(num_items, 1)

    def forward(self, user_id, item_id):
        P_u = self.P(user_id)
        Q_i = self.Q(item_id)
        b_u = self.user_bias(user_id)
        b_i = self.item_bias(item_id)
        outputs = (P_u * Q_i).sum(axis=1) + np.squeeze(b_u) + np.squeeze(b_i)
        return outputs.flatten()

16.3.3. Phương pháp Đánh giá

Tiếp theo, ta lập trình phép đo RMSE (root-mean-square error - căn bậc hai trung bình bình phương sai số), phương pháp này được sử dụng rộng rãi nhằm đo lường sự khác nhau giữa giá trị đánh giá dự đoán và giá trị đánh giá thực tế (nhãn gốc) [Gunawardana & Shani, 2015]. RMSE được định nghĩa như sau:

(16.3.4)\[\mathrm{RMSE} = \sqrt{\frac{1}{|\mathcal{T}|}\sum_{(u, i) \in \mathcal{T}}(\mathbf{R}_{ui} -\hat{\mathbf{R}}_{ui})^2}\]

trong đó \(\mathcal{T}\) là tập bao gồm các cặp người dùng và sản phẩm mà ta sử dụng để đánh giá. \(|\mathcal{T}|\) là kích thước tập này. Ta có thể sử dụng hàm RMSE được cung cấp sẵn trong mx.metric.

def evaluator(net, test_iter, devices):
    rmse = mx.metric.RMSE()  # Get the RMSE
    rmse_list = []
    for idx, (users, items, ratings) in enumerate(test_iter):
        u = gluon.utils.split_and_load(users, devices, even_split=False)
        i = gluon.utils.split_and_load(items, devices, even_split=False)
        r_ui = gluon.utils.split_and_load(ratings, devices, even_split=False)
        r_hat = [net(u, i) for u, i in zip(u, i)]
        rmse.update(labels=r_ui, preds=r_hat)
        rmse_list.append(rmse.get()[1])
    return float(np.mean(np.array(rmse_list)))

16.3.4. Huấn luyện và Đánh giá Mô hình

Trong hàm huấn luyện, ta áp dụng mất mát \(L_2\) với suy giảm trọng số. Phương thức suy giảm trọng số có tác dụng giống như điều chuẩn \(L_2\).

#@save
def train_recsys_rating(net, train_iter, test_iter, loss, trainer, num_epochs,
                        devices=d2l.try_all_gpus(), evaluator=None,
                        **kwargs):
    timer = d2l.Timer()
    animator = d2l.Animator(xlabel='epoch', xlim=[1, num_epochs], ylim=[0, 2],
                            legend=['train loss', 'test RMSE'])
    for epoch in range(num_epochs):
        metric, l = d2l.Accumulator(3), 0.
        for i, values in enumerate(train_iter):
            timer.start()
            input_data = []
            values = values if isinstance(values, list) else [values]
            for v in values:
                input_data.append(gluon.utils.split_and_load(v, devices))
            train_feat = input_data[0:-1] if len(values) > 1 else input_data
            train_label = input_data[-1]
            with autograd.record():
                preds = [net(*t) for t in zip(*train_feat)]
                ls = [loss(p, s) for p, s in zip(preds, train_label)]
            [l.backward() for l in ls]
            l += sum([l.asnumpy() for l in ls]).mean() / len(devices)
            trainer.step(values[0].shape[0])
            metric.add(l, values[0].shape[0], values[0].size)
            timer.stop()
        if len(kwargs) > 0:  # It will be used in section AutoRec
            test_rmse = evaluator(net, test_iter, kwargs['inter_mat'],
                                  devices)
        else:
            test_rmse = evaluator(net, test_iter, devices)
        train_l = l / (i + 1)
        animator.add(epoch + 1, (train_l, test_rmse))
    print(f'train loss {metric[0] / metric[1]:.3f}, '
          f'test RMSE {test_rmse:.3f}')
    print(f'{metric[2] * num_epochs / timer.sum():.1f} examples/sec '
          f'on {str(devices)}')

Cuối cùng, hãy kết hợp tất cả với nhau và huấn luyện mô hình. Trường hợp này, ta đặt kích thước nhân tố tiềm ẩn bằng 30.

devices = d2l.try_all_gpus()
num_users, num_items, train_iter, test_iter = d2l.split_and_load_ml100k(
    test_ratio=0.1, batch_size=512)
net = MF(30, num_users, num_items)
net.initialize(ctx=devices, force_reinit=True, init=mx.init.Normal(0.01))
lr, num_epochs, wd, optimizer = 0.002, 20, 1e-5, 'adam'
loss = gluon.loss.L2Loss()
trainer = gluon.Trainer(net.collect_params(), optimizer,
                        {"learning_rate": lr, 'wd': wd})
train_recsys_rating(net, train_iter, test_iter, loss, trainer, num_epochs,
                    devices, evaluator)
train loss 0.066, test RMSE 1.052
297302.5 examples/sec on [gpu(0)]
../_images/output_mf_vn_425199_9_1.svg

Ở dưới, ta sử dụng mô hình đã được huấn luyện để dự đoán đánh giá mà một người dùng (ID 20) có thể gán cho một sản phẩm (ID 30).

scores = net(np.array([20], dtype='int', ctx=devices[0]),
             np.array([30], dtype='int', ctx=devices[0]))
scores
array([3.024855], ctx=gpu(0))

16.3.5. Tóm tắt

  • Mô hình phân rã ma trận được sử dụng rộng rãi trong hệ thống đề xuất. Nó có thể được sử dụng để dự đoán đánh giá của một người dùng cho một sản phẩm.
  • Ta có thể lập trình và huấn luyện mô hình phân rã ma trận cho hệ thống đề xuất.

16.3.6. Bài tập

  • Thay đổi kích thước của nhân tố tiềm ẩn. Kích thước của nhân tố tiềm ẩn ảnh hướng thế nào đến hiệu năng của mô hình?
  • Thử các bộ tối ưu, tốc độ học và tốc độ suy giảm trọng số khác nhau.
  • Kiểm tra giá trị đánh giá dự đoán của những người dùng khác cho một bộ phim cụ thể.

16.3.7. Thảo luận

16.3.8. 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
  • Nguyễn Văn Cường
  • Nguyễn Lê Quang Nhật
  • Lê Khắc Hồng Phúc

Cập nhật lần cuối: 06/10/2020. (Cập nhật lần cuối từ nội dung gốc: 12/09/2020)