FACTORIZATION MACHINES and THEIR APPLICATION on HUGE DATASETS
Table of Contents
Giới thiệu tổng quát về Factorization Machines và ứng dụng của nó trên tập dữ liệu lớn Dựa trên bài báo Introductory Guide – Factorization Machines & their application on huge datasets (with codes in Python), tác giả: Ankit Choudhary
Phần mở đầu
Khi chúng ta làm việc với các bài toán liên quan tới Click Prediction Problem hay Recommendation Systems. Chúng ta thường xuyên đối mặt với vấn đề là tập dữ liệu quá lớn. Việc dự đoán trong tập dữ liệu lớn là một khó khăn, thách thức với một nguồn tài nguyên máy tính hiện có. Hơn nữa đối với các tập dữ liệu thưa (sparse) là tập dữ liệu mà trong đó có tồn tại dữ liệu không có giá trị và trong tập dữ liệu đó có những dữ liệu có những đặc trưng quan trọng tác động tới việc dự đoán và cả những đặc trưng không quan trọng. Vậy thì việc dự đoán càng trở nên khó khăn hơn. Để giải quyết các vấn đề trên, tác giả giới thiệu về Factorization Machines để xác định trong tập dữ liệu đó có những đặc trưng nào quan trọng trong việc dự doán.
Mục tiêu
Đưa ra những vấn đề gặp phải khi làm việc trên tập dữ liệu lớn, từ đó tác giả giới thiệu về Factorization Machines để khắc phục các vấn đề gặp phải.
- Để hiểu được Factorization Machines, tác giả giới thiệu cơ sở lý thuyết về mô hình phân rã ma trận (Matrix Factorization) và các thuật toán học liên quan.
- Sau đó tác giả giới thiệu và đánh giá lần lược các mô hình để tối ưu là: Linear < Poly2 < FMs < FFMs
Cấu trúc trình bày
- Phần 1: Giới thiệu một số kiến thức liên quan.
- Phần 2: Giới thiệu về Factorization Machines.
- Phần 3: Tổng kết.
Một số kiến thức liên quan
- Gradient Descent là thuật toán tìm giá trị nhỏ nhất của hàm số f(x) dựa trên đạo hàm.
Việc chọn hệ số learning_rate cực kì quan trọng, có 3 trường hợp:
- Nếu learning_rate nhỏ: Mỗi lần hàm số giảm rất ít nên cần rất nhiều lần thực hiện bước 2 để hàm số đạt giá trị nhỏ nhất.
- Nếu learning_rate hợp lý: Sau một số lần lặp bước 2 vừa phải thì hàm sẽ đạt giá trị đủ nhỏ.
- Nếu learning_rate quá lớn: Sẽ gây hiện tượng overshoot và không bao giờ đạt được giá trị nhỏ nhất của hàm
- Regularization (kỹ thuật chính quy hóa)
Overfitting là hiện tượng mô hình tìm được quá khớp với dữ liệu huấn luyện (training). Việc quá khớp này có thể dẫn đến việc dự đoán nhầm nhiễu, và chất lượng mô hình không còn tốt trên dữ liệu test nữa.
Model: Underfit: degree 1, Goodfit: degree 3, Overfit: degree 15
Chính quy hoá (regularization) là một kỹ thuật giúp giảm lỗi quá khớp (Overfitting) trong khi vẫn giữ được tính tổng quát của nó (tính tổng quát là tính mô tả được nhiều dữ liệu, trong cả tập training và test) bằng cách thêm một phần chính quy hoá vào hàm lỗi như sau:
E_x (θ) là hàm lỗi ban đầu và cụm λE_θ (θ) mới thêm vào là số hạng chính quy hoá đóng vai trò như một biện pháp kiểm soát lỗi.
Phương pháp chính quy hoá này còn có tên là cắt trọng số (Weight Decay) vì nó làm cho các trọng số (tham số θ) bị tiêu biến dần về 0 trong khi học. Còn trong thống kê, phương pháp này có tên là co tham số (Parameter Shrinkage) vì nó làm co lại các giá trị tham số dần về 0.
- Matrix Factorization
Chúng ta có thể nhận ra có một vài đánh giá bị thiếu và vấn đề đặt ra ở đây là chúng ta muốn xây dựng một phương thức để dự đoán các xếp hạng bị thiếu.
Giả định rằng chúng ta sử dụng Matrix Factorization để giải quyết vấn đề trên là nên có một vài đặc trưng ẩn mà nó xác định được cách mà người dùng xếp hạng một bộ phim. Chẳng hạn người dùng A và B sẽ xếp hạng cao các bộ phim của diễn viên AI Pacino nếu họ là người hâm mộ của diễn viên đó. Ở đây sự hâm mộ đối với một diễn viên cụ thể nào đó là một đặc trưng ẩn vì nó không thể hiện rõ ràng trong ma trận trên
Ý tưởng là chúng ta phân rã ma trận ánh xạ người dùng và bộ phim sang một không gian có hướng f mà ở đó các yếu tố đặc trưng ẩn có thể kết hợp được với nhau, nghĩa là tương quan người dùng và bộ phim được mô hình thành tích vô hướng bên trong không gian đó.
Giới thiệu về Factorization Machines
- Click Through Rate:
Click Through Rate (CTR) là gì? CTR là tỷ lệ thể hiện tần suất những người thấy quảng cáo của bạn kết thúc bằng cách nhấp vào quảng cáo đó. Tỷ lệ nhấp (CTR) có thể được sử dụng để đánh giá hiệu suất của từ khóa và quảng cáo của bạn
CTR = Số nhấp chuột ÷ số lần hiển thị. (VD: Nếu chúng ta đã có 5 lần nhấp chuột và 100 lần hiển thị. CTR bằng 5%.)
- Mô hình trong dự đoán CTR
Dự đoán tỉ lệ nhấp đóng một vai trò quan trọng trong tính toán quảng cáo (Computational Advertising). Một số mô hình được dùng phổ biến trong việc tối ưu CTR là: Poly2 và Factorization machines (FMs). Trong thời gian gần đây một biến thể của FMs là FFMs đã thực hiện tốt việc dự đoán trong cuộc thi dự đoán CTR toàn cầu và FFMs cho thấy rất có hiệu quả trong việc phân lớp với tập dữ liệu lớn và thưa thớt.
Để hiểu được FMs và FFMs. Việc đầu tiên chúng ta cẩn phải hiểu về mô hình hồi quy tuyến tính (Linear Regression) và hồi quy đa thức (Poly2 Regression) Chúng ta cùng xét tập dữ liệu trong ví dụ sau đây với mong muốn là dự đoán kết quả nhấp thông qua các đặc trưng như nhà xuất bản (Publisher), nhà quảng cáo (Advertiser) và giới tính (Gender)
Tổng kết
Qua bài báo này, chúng ta đã tìm hiểu về Factorization Machines, thông qua các cơ sở lý thuyết về mô hình phân rã ma trận (Matrix Factorization) và các thuật toán học liên quan song song với đó chúng ta đã so sánh và đánh giá lần lược các mô hình để tối ưu như Linear < Poly2 < FMs < FFMs.
FFMs được sử dụng và đã giành giải nhất trong ba cuộc thi về CTR do Criteo, Avazu, Outbrain tổ chức và giành giải ba trong cuộc thi RecSys Challenge 2015
