Danh mục nội dung
Tìm kiếm KNN
Thuật toán K-hàng xóm gần nhất, còn được gọi là KNN hoặc k-NN, là một thuật toán học máy có giám sát, không có tham số, được dùng trong phân loại dữ liệu. Thuật toán này sử dụng khoảng cách để phân loại hoặc dự đoán về một nhóm điểm dữ liệu, dựa trên giả định rằng các điểm dữ liệu tương tự sẽ gần nhau về khoảng cách.
Ngày nay, tìm kiếm hàng xóm gần nhất đã trở thành một chủ đề nghiên cứu nóng bởi tính ứng dụng thực tiễn của nó, nhằm giúp người dùng có thể dễ dàng tìm thấy thông tin họ đang tìm kiếm trong thời gian hợp lý. Thuật toán k-NN là một trong những kỹ thuật giúp tìm chính xác các hàng xóm gần nhất, bởi nó so sánh khoảng cách của mỗi điểm dữ liệu với mọi điểm dữ liệu khác, vì vậy nó yêu cầu thời gian truy vấn tuyến tính (kích thước tập dữ liệu). Nhưng thật không may, hầu hết các ứng dụng hiện đại ngày nay đều có tập dữ liệu khổng lồ (hàng triệu) với chiều cao (hàng trăm hoặc hàng nghìn), vì vậy mà tìm kiếm tuyến tính sẽ tốn kém thời gian. Hãy thử tưởng tượng một thị trường C2C trong thế giới thực với hàng triệu sản phẩm có trong cơ sở dữ liệu và có thể có hàng nghìn sản phẩm mới được tải lên mỗi ngày. So sánh từng sản phẩm với tất cả hàng triệu sản phẩm là lãng phí và mất quá nhiều thời gian, có thể nói giải pháp này là không thể mở rộng. Ngoài ra, các ứng dụng hiện đại còn có nhiều ràng buộc bổ sung khác như mức tiêu thụ bộ nhớ hợp lý và/hoặc độ trễ thấp.
Điều quan trọng cần lưu ý là mặc dù đã có rất nhiều tiến bộ gần đây về chủ đề này, nhưng k-NN vẫn là phương pháp khả dụng duy nhất để đảm bảo truy xuất chính xác hàng xóm gần nhất.
Tìm kiếm ANN
Để giải quyết những vấn đề của k-NN, một lớp các thuật toán mới ra đời có tên là ANN (Approximate Nearest Neighbors). Các thuật toán ANN đánh đổi độ chính xác để mang lại hiệu quả tìm kiếm nhanh chóng, trong thời gian chấp nhận được. Trong một thị trường C2C thực tế, nơi mà số lượng hàng xóm thực tế cao hơn K hàng xóm gần nhất cần tìm kiếm rất nhiều, ANN có thể cho phép đạt được độ chính xác đáng kể khi so sánh với KNN, trong một thời gian ngắn.
Trong các ứng dụng hiện đại, sai số nhỏ về độ chính xác đổi lại với độ trễ thấp mang lại nhiều lợi ích cho người dùng. Hai ví dụ dưới đây cho thấy điều đó:
- Tìm kiếm trực quan – Là một người dùng, nếu tôi đang muốn tìm kiếm một bức ảnh về chiếc giày yêu thích, tôi sẽ không bận tâm đến thứ tự xuất hiện của các kết quả trả về, tôi có thể thỏa mãn nhu cầu tìm kiếm của mình nếu như một số ít kết quả mong muốn được hiển thị gần nhất trong khung nhìn của mình.
- Các hệ gợi ý – Tương tự như trên, tôi cũng không bận tâm quá nhiều đến thứ tự ưu tiên của các kết quả gần nhất khi mà tôi chỉ cần khoảng 8 đến 10 kết quả tương tự hiển thị trong khung nhìn của mình.
Các kỹ thuật ANN tăng tốc độ tìm kiếm bằng cách tiền xử lý dữ liệu thành một chỉ mục hiệu quả và thường được xử lý qua các giai đoạn sau:
- Vector Transformation – được áp dụng trên các véc-tơ trước khi chúng được lập chỉ mục, ví dụ như giảm chiều dữ liệu.
- Vector Encoding – được áp dụng trên các véc-tơ để xây dựng chỉ mục thực sự cho tìm kiếm; một số kỹ thuật dựa trên cấu trúc dữ liệu được áp dụng như: Cây, LSH, và lượng tử hóa – một kỹ thuật để mã hóa véc-tơ thành dạng nén, nhỏ gọn hơn nhiều.
- Thành phần loại bỏ tìm kiếm toàn bộ – được áp dụng trên các véc-tơ để tránh tìm kiếm toàn bộ như k-NN diễn ra, sử dụng các kỹ thuật như: Các tệp đảo ngược, các đồ thị hàng xóm lân cận,…
Vì sự hữu ích cũng như ứng dụng thực tiễn mà ANN mang lại, nên hiện nay đã có một số thuật toán ANN được triển khai nguồn mở và được sử dụng phổ biến, như: Annoy của Spotify [1], ScaNN của Google [2], Faiss của Facebook [3], và Hnsw [4].
Tuy nhiên, các kỹ thuật ANN cũng tồn tại nhược điểm, một trong số đó là tài nguyên điện toán, cụ thể là RAM, các kỹ thuật này phải tải toàn bộ các véc-tơ vào RAM để có thể truy xuất các hàng xóm gần nhất.
Tài liệu tham khảo
[1] ANNOY library, https://github.com/spotify/annoy
[2] ScaNN library, https://github.com/google-research/google-research/tree/master/scann
[3] Faiss library, https://github.com/facebookresearch/faiss
[4] Hnsw library, https://github.com/nmslib/hnswlib
Author
Ha Huu Linh