Phát hiện trùng lặp tương tự bằng độ tương đồng Jaccard và MinHash

 (blog.nelhage.com)
1 điểm bởi GN⁺ 2024-07-06 | 1 bình luận | Chia sẻ qua WhatsApp
  • Trong các bộ sưu tập tài liệu quy mô lớn, khi crawl web có thể lấy cùng một trang nhiều lần hoặc lẫn vào các bản chỉ chỉnh sửa nhỏ, vì vậy độ tương đồng Jaccard và MinHash là cách thực tế để tìm các tài liệu “gần như giống nhau”
  • Độ tương đồng Jaccard chuyển tài liệu thành tập đặc trưng rồi tính kích thước giao / kích thước hợp, và xem các cặp vượt ngưỡng là trùng lặp tương tự, nhưng quan hệ này nhìn chung không có tính bắc cầu
  • Nếu so sánh mọi cặp tài liệu thì chi phí sẽ là O(n²) theo kích thước corpus, nên MinHash tóm tắt mỗi tài liệu thành chữ ký kích thước cố định để xấp xỉ độ tương đồng theo xác suất
  • Khi dùng k hàm băm, có thể ước lượng độ tương đồng bằng tỷ lệ các vị trí trùng khớp trong chữ ký của hai tài liệu, và các điều kiện như min-wise independence là quan trọng trong việc chọn hàm băm
  • Nếu dùng toàn bộ chữ ký hoặc một phần chữ ký làm khóa nhóm, có thể điều chỉnh xác suất tài liệu tương tự rơi vào cùng một bucket; cách chọn n-gram và tokenization sẽ quyết định độ nhạy phát hiện và chi phí

Khó khăn của việc phát hiện trùng lặp tương tự

  • Mục tiêu là tìm trong một tập tài liệu lớn những tài liệu không hoàn toàn giống nhau nhưng gần như giống nhau
    • Khi crawl web theo chu kỳ, có thể lấy cùng một trang nhiều lần nhưng metadata hơi khác nhau
    • Cũng có thể tồn tại nhiều bản chỉnh sửa nhỏ của cùng một trang
  • Cách tiếp cận cơ bản là định nghĩa một hàm độ tương đồng S(A, B) giữa hai tài liệu, rồi coi các cặp có giá trị từ ngưỡng Scrit trở lên là trùng lặp tương tự
  • “Gần như giống hệt” nói chung không phải là quan hệ bắc cầu
    • A và B, B và C có thể tương tự vượt ngưỡng
    • Nhưng đồng thời A và C có thể thấp hơn ngưỡng
    • Vì vậy, phát hiện trùng lặp tương tự ở quy mô lớn khó xử lý hơn phát hiện trùng lặp chính xác

Định nghĩa độ tương đồng Jaccard

  • Jaccard index biểu diễn độ tương đồng của hai tập hữu hạn bằng kích thước giao / kích thước hợp

    [ J(A, B) = \frac{|A \cap B|}{|A \cup B|} ]

  • Nếu hai tập giống nhau, chúng sẽ chia sẻ phần lớn phần tử nên hợp chỉ tăng ít còn giao chỉ giảm ít

  • Nếu hai tập tách biệt hoàn toàn thì kích thước giao là 0, nên độ tương đồng Jaccard bằng 0

  • Nếu hai tập giống hệt nhau thì giao và hợp đều là cùng một tập, nên độ tương đồng Jaccard bằng 1

  • Tài liệu thực tế có dạng như chuỗi Unicode, nên trước hết cần chuyển tài liệu thành tập đặc trưng

Vấn đề mở rộng khi so sánh mọi cặp

  • Sau khi chuyển tài liệu thành tập đặc trưng, định nghĩa tìm các cặp có độ tương đồng Jaccard cao tự nó khá đơn giản
  • Nhưng nếu so sánh mọi cặp tài liệu thì chi phí tăng thành O(n²) theo kích thước corpus
  • Với phát hiện trùng lặp chính xác, người ta băm tài liệu rồi gom các tài liệu vào cùng bucket băm để tránh chi phí này
  • Phát hiện trùng lặp tương tự cũng cần một đường vòng tương tự; trong lĩnh vực này, nó được gọi là locality-sensitive hash
  • Với độ tương đồng Jaccard, có một kỹ thuật phù hợp cho mục đích này, và cốt lõi của nó là MinHash

Xấp xỉ độ tương đồng Jaccard bằng MinHash

  • MinHash xấp xỉ độ tương đồng Jaccard chỉ bằng một chữ ký (signature) nhỏ được tính trước cho mỗi tài liệu, thay vì phải so sánh toàn bộ tập mỗi lần

  • Ý tưởng cơ bản là lấy ngẫu nhiên đồng đều một phần tử từ hợp và xem phần tử đó có thuộc giao hay không

  • Trên thực tế, thay vì hoán vị ngẫu nhiên, người ta dùng một hàm băm tốt H(x) và lưu đặc trưng có giá trị băm nhỏ nhất trong mỗi tập

    [ a_{min} \leftarrow \min_{x \in A} H(x) ]

    [ b_{min} \leftarrow \min_{x \in B} H(x) ]

  • Phép min có tính kết hợp, nên có thể tiền xử lý độc lập giá trị băm nhỏ nhất của từng tài liệu

  • Xác suất giá trị băm nhỏ nhất của hai tập bằng nhau chính bằng độ tương đồng Jaccard của chúng

Nhiều hàm băm và vector chữ ký

  • Nếu chỉ dùng một hàm băm thì chỉ có thể ước lượng kiểu boolean “giống/không giống” cho hai tài liệu

  • Nếu dùng k hàm băm khác nhau, có thể tóm tắt mỗi tài liệu thành một vector gồm k giá trị MinHash

    [ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]

  • Xấp xỉ độ tương đồng Jaccard bằng tỷ lệ các vị trí có cùng giá trị trong hai chữ ký

    [ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]

  • Việc chọn họ hàm băm có những điểm tinh tế

    • Mục tiêu là xấp xỉ một hoán vị ngẫu nhiên trên toàn bộ không gian đặc trưng
    • Trên thực tế, họ hàm băm chỉ biểu diễn được một phần cực nhỏ trong mọi hoán vị khả dĩ
    • Cần tránh các tương quan không phù hợp, và tính chất liên quan được gọi là min-wise independence
    • Vấn đề này đã được nghiên cứu khá kỹ và trong tài liệu có các lời giải hiệu quả

Tìm các cặp ứng viên trong toàn bộ corpus

  • Khi đã rút mỗi tài liệu xuống thành dấu vân tay gồm k giá trị băm, có thể xấp xỉ độ tương đồng Jaccard hiệu quả
  • Vấn đề còn lại là tìm các tài liệu có độ tương đồng cao trong toàn bộ corpus mà không phải xét mọi cặp tài liệu
  • Chiến lược là nhóm tài liệu theo một khóa nào đó, rồi chỉ so sánh trong cùng nhóm
  • Khóa nhóm phải được thiết kế sao cho tài liệu tương tự có xác suất cao được gom cùng nhau, còn tài liệu không tương tự thì cố tránh bị gom chung

  • Dùng toàn bộ chữ ký MinHash làm khóa

    • Cách đơn giản nhất là dùng toàn bộ k giá trị MinHash làm một khóa nhóm duy nhất
    • Chỉ coi hai tài liệu là trùng lặp tương tự khi mọi giá trị MinHash đều trùng nhau
    • Bài báo GPT-3 đã dùng loại bỏ trùng lặp tương tự trong pipeline chuẩn bị dataset, và theo cách diễn đạt được trích dẫn thì có thể hiểu là họ dùng triển khai MinHashLSH của Spark cùng 10 hàm băm
    • Ưu điểm của cách này là đơn giản và hiệu quả
    • Việc nhóm theo một chuỗi byte có cardinality cao như vậy rất dễ mở rộng theo chiều ngang
    • Nó tương ứng với các primitive cơ bản của công cụ xử lý dữ liệu, như bước “shuffle” giữa map và reduce trong MapReduce
    • Nếu độ tương đồng Jaccard của hai tài liệu là J(A, B) và cần cả k giá trị đều trùng nhau, thì xác suất va chạm cho một cặp đơn lẻ là J(A, B)^k
    • Với k = 10, các tài liệu có độ tương đồng khoảng 0.6 trở xuống gần như không va chạm
    • Xác suất trùng bắt đầu tăng mạnh quanh mức tương đồng khoảng 0.95
    • Nếu mục tiêu là tìm các tài liệu cực kỳ gần nhau thì như vậy có thể đã đủ
    • Phép tính J^k này là dành cho một cặp tài liệu đơn lẻ
    • Nếu có nhiều tài liệu rất giống nhau thì xác suất theo từng cặp không còn độc lập
    • Trên thực tế, các tài liệu rất giống nhau thường rơi vào chỉ hai hoặc ba bucket, và có thể tìm được gần như toàn bộ trùng lặp

Phát hiện trùng lặp lỏng hơn

  • Nếu muốn tìm không chỉ các tài liệu có độ tương đồng gần 1 mà cả các tài liệu từ 0.8 hoặc 0.7 trở lên, thì dùng toàn bộ chữ ký làm khóa có thể quá nghiêm ngặt

  • Nếu chỉ dùng một phần trong k giá trị MinHash làm khóa nhóm thì xác suất va chạm ở mức tương đồng thấp hơn sẽ tăng lên

    • Ví dụ, có thể nhóm theo 4 giá trị MinHash đầu tiên, rồi trong cùng bucket dùng toàn bộ giá trị MinHash để ước lượng độ tương đồng thực sự

  • Việc giảm số lượng băm cũng có giới hạn

    • J^r luôn nhỏ hơn J
    • Nếu r quá nhỏ thì có thể phát sinh quá nhiều va chạm sai

  • Thay vào đó, có thể tạo nhiều khóa cho mỗi tài liệu để đưa nó vào nhiều bucket

    • Ví dụ, tính k = 20 giá trị băm, chia vào b = 4 bucket, và mỗi khóa gồm r = 5 giá trị băm

  • Xác suất hai tài liệu va chạm trong ít nhất một bucket là

    [ p = 1 - (1 - J^r)^b ]

  • Trong ví dụ dùng 4 nhóm và 5 giá trị băm mỗi nhóm, điểm mà xác suất va chạm đạt 50% dịch xuống gần khoảng J = 0.7

  • Khi cả r và b đều lớn hơn 1, đường cong kết quả thường có dạng chữ S, tạo ra không gian điều chỉnh giữa độ nhạy, recall và chi phí hiệu năng

Liên hệ với HyperLogLog

  • Mánh cốt lõi của MinHash có nét tương đồng với các thuật toán sketch như HyperLogLog
  • HyperLogLog băm từng phần tử của dòng dữ liệu rồi lưu giá trị cực đại đang chạy của số lượng bit 0 đứng đầu trong giá trị băm
  • Cả hai kỹ thuật đều ánh xạ phần tử đầu vào sang phân phối đồng đều bằng hàm băm, rồi tính cực trị đang chạy để ước lượng các tính chất phân phối chỉ bằng bản tóm tắt kích thước hằng số
  • Nếu đảo cách nhìn về thứ tự bit, HyperLogLog có thể được xem là tính cực tiểu đang chạy của log2(H(x)), còn MinHash dùng cực tiểu của chính H(x)
  • Theo một nghĩa nào đó, hai cấu trúc này là đối ngẫu
    • Kết hợp hai cấu trúc HyperLogLog có thể ước lượng kích thước hợp của hai tập
    • So sánh hai cấu trúc MinHash có thể ước lượng kích thước tương đối của giao giữa hai tập
  • Kết hợp hai cấu trúc này có thể tạo ra sketch xử lý các câu hỏi về giao và hợp của những tập bất kỳ

Cách biểu diễn tài liệu dưới dạng tập

  • Để dùng Jaccard và MinHash, trước hết phải chuyển tài liệu chuỗi thành tập đặc trưng
  • Dù chọn cách nào, vẫn có thể chuẩn hóa tài liệu ở bước tiền xử lý
    • Chuyển sang Unicode normalization form
    • Gộp chữ hoa/chữ thường
    • Rút gọn khoảng trắng liên tiếp
    • Và các biến đổi tương tự

  • n-gram hoặc shingle

    • Có thể biểu diễn tài liệu bằng tập всех n-gram xuất hiện trong đó
    • Trong tài liệu xử lý văn bản quy mô lớn, thuật ngữ “shingle” cũng được dùng, nhưng ở đây nó đóng vai trò giống n-gram
    • Việc chọn giá trị n có sự đánh đổi
    • Giá trị nhỏ so sánh tài liệu theo cách thô hơn
    • Ví dụ, phần lớn văn bản tiếng Anh có thể trông khá giống nhau nếu nhìn theo bigram
    • Giá trị lớn tạo ra các đặc trưng phân biệt hơn và tập lớn hơn
    • Nếu quá lớn thì độ nhạy có thể giảm, nhưng trước đó có khả năng vấn đề hiệu năng đã xuất hiện
    • Theo Mining of Massive Datasets §3.2.2, trong nhiều ứng dụng các giá trị từ n = 5 đến 9 là lựa chọn phổ biến

  • Tách từ hoặc token

    • Cũng có thể chia đầu vào thành “từ” hoặc “token” rồi dùng chúng làm đặc trưng
    • Đoạn trích từ bài báo GPT-3 nhắc đến tokenizer chuẩn của Spark, có vẻ là pyspark.ml.feature.Tokenizer, bộ này chuyển đầu vào sang chữ thường rồi tách theo khoảng trắng
    • Cũng có thể dùng NLTK tokenizer tinh vi hơn
    • Một cách lai cũng khả thi: token hóa trước rồi dùng n-gram của token
    • Vì token riêng lẻ có entropy cao hơn byte hay ký tự, nên trong trường hợp này thường dùng giá trị n nhỏ hơn

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-06
Các ý kiến trên Hacker News

  • Nhiều người bỏ qua việc các chỉ số dựa trên tập hợp như độ tương đồng Jaccard (hệ số Tanimoto) hay điểm F1 (hệ số Dice) cũng có thể dùng tương tự cho tập mờ
    Tuy nhiên cần chọn một cặp T-Norm / T-Conorm phù hợp để biểu diễn khái niệm giao và hợp của tập mờ, và có vô số loại như vậy
    Ngược lại, việc có thể chọn cặp phù hợp với ngữ nghĩa mong muốn lại là một lợi thế
    Trong kiểm chứng phân đoạn ảnh y khoa, tôi từng xử lý nội dung này khi kết quả phân đoạn và đáp án đúng không phải là mặt nạ nhị phân mà ở dạng xác suất/mờ: https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
    Thông thường người ta đặt ngưỡng 0,5 để tạo tập nhị phân rồi dùng biến thể nhị phân của Jaccard/Dice, nhưng làm vậy có vẻ khiến độ chính xác của toán tử kiểm chứng giảm khoảng hai chữ số thập phân
    Tức là công bố rằng thuật toán tốt hơn kỹ thuật mới nhất 0,001, nhưng lại bỏ qua việc biên sai số của toán tử kiểm chứng thực ra là 0,1

  • Từng có một khách hàng tự tạo bản triển khai Python của kỹ thuật này để loại bỏ trùng lặp các mục công dân trong một cơ sở dữ liệu lớn của chính phủ Pháp, và nó hoạt động tốt
    Nếu là hiện nay thì có lẽ tôi đã bảo họ dùng datasketch: https://pypi.org/project/datasketch/
    Tìm thử thì thấy các công cụ mới về chủ đề này vẫn liên tục xuất hiện. Chẳng hạn https://pypi.org/project/rensa/ là một phiên bản chuyên biệt hơn và nhanh hơn so với MinHash của datasketch, được viết bằng Rust và phủ thêm một chút Python bên trên

    • Với việc loại bỏ trùng lặp người, mô hình Fellegi-Sunter cũng là một hướng tiếp cận mạnh. Splink là thư viện Python miễn phí triển khai mô hình này cho các tập dữ liệu lớn, và có lẽ cũng có thể kết hợp một phần của hai hướng tiếp cận
      Tôi xin nói rõ mình là tác giả chính
      Tôi cũng đã viết một hướng dẫn tương tác giải thích cách nó hoạt động: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
    • Còn có gaoya nữa. Nó do tôi làm, viết bằng Rust và cũng cung cấp binding Python
      datasketch rất tuyệt, nhưng hiệu năng không đủ cho trường hợp sử dụng của tôi, còn gaoya đang được dùng trong một hệ thống vận hành phân cụm quy mô lớn: https://github.com/serega/gaoya

  • Thật là trùng hợp đáng kinh ngạc. Tôi vừa triển khai một hệ thống MinHash mà có thể sẽ có người thấy thú vị
    Bài toán là tìm giả nghịch đảo của nhiều ma trận con phù hợp trong một ma trận vuông lớn
    Dùng các đẳng thức ma trận như Woodbury, Banachiewicz có thể cập nhật nghịch đảo của các ma trận con “gần” nhau để tính nghịch đảo mới với chi phí thấp
    Chỉ cần lưu các nghịch đảo đã tính với chỉ số hàng/cột làm khóa, rồi với mỗi ma trận con mới, tìm một nghịch đảo đã có gần nó để làm điểm xuất phát cập nhật
    Tôi đã giải bài toán này bằng MinHash, xử lý hash giá trị nhỏ nhất cho các chỉ số để các ma trận gần nhau có xác suất cao có cùng hash
    Trong bản triển khai của tôi, tôi dùng hash đa độ phân giải để có thể điều chỉnh độ chọn lọc tìm kiếm khi số nghịch đảo đã tính tăng lên

  • Bổ sung thêm một chút bối cảnh mà bài viết này còn thiếu: theo tôi biết, kỹ thuật này được tạo ra vào thời kỳ đầu của Google để loại bỏ trùng lặp trong tập dữ liệu crawl
    Cũng thú vị là việc tạo LLM và việc lập chỉ mục văn bản web thông thường lại giống nhau đến mức đáng ngạc nhiên
    Có thể đọc chi tiết trong cuốn sách miễn phí “Mining Massive Datasets” của Jeffrey Ullman, trong đó giải thích nhiều kỹ thuật ấn tượng và rất hay từng được dùng để xây dựng chỉ mục cho toàn bộ Internet thời đó
    Có thể tìm tài liệu liên quan miễn phí bằng cách tìm “chapter 3 pdf mmds ullman”
    Chỉnh sửa: hóa ra tôi đã nhầm, theo Wikipedia thì nó được phát minh ở DEC cho AltaVista: https://en.wikipedia.org/wiki/MinHash
    Dù sao thì sách của Ullman cũng có phần giải thích tốt và cũng nói về cách nó được dùng ở Google

  • Khi cố hiểu MinHash và các biến thể của nó, tôi thấy khá khó ngấm, nên đang làm một công cụ trực quan hóa trực tuyến: https://websla.sh/tools/minhash
    Nó vẫn chưa hoàn thiện và tôi cũng muốn hiển thị cả phần tính độ tương đồng Jaccard, nhưng hiện giờ bạn đã có thể nhập nhiều chuỗi để tự xem “minhash” thực sự là gì

  • Việc dùng hashing hoặc mạng nơ-ron nhỏ cùng với công cụ tìm kiếm vector và Tanimoto/Jaccard là một chiến lược rất phổ biến trong khử trùng lặp tập dữ liệu quy mô lớn
    Cách này có thể khôn ngoan hơn so với dùng các tác vụ MapReduce có độ phức tạp tuyến tính
    Có một dự án hay của Google dùng mô hình RETSim 500 nghìn tham số và engine USearch: https://github.com/google/unisim

  • Hiện trong PostgreSQL tôi đang gặp một vấn đề tương tự. Có 600.000 feed_items và schema là (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
    Đặc biệt, các cột content và summary của một số mục tin tức rất giống nhau nhưng không hoàn toàn giống
    Khi có hai mục tin tức như vậy, tôi muốn gộp chúng thành một; có cách nào hay không?

    • Tôi đã triển khai một hệ thống giống MinHash trong BigQuery và có thể tính cosine similarity giữa tất cả các mục Stack Overflow trong thời gian hợp lý
      Quy trình đại khái như sau
      1. Nối tất cả các trường văn bản lại và tách thành mảng n-gram, ví dụ theo đơn vị 2~n ký tự
      2. Khai báo hai mảng toàn cục A và B có độ dài n, rồi điền bằng các số nguyên ngẫu nhiên 32~64 bit
      3. Hash từng n-gram thành số nguyên 32~64 bit, sau đó nhân hash đó với từng giá trị ngẫu nhiên trong mảng A, lấy phần dư khi chia kết quả cho từng giá trị ngẫu nhiên trong mảng B, rồi lấy giá trị nhỏ nhất
        Mục tiêu là với mỗi hàng, thu được một mảng số nguyên “minhashed” có cùng độ dài với các mảng ở bước 2. Nếu khai báo độ dài mảng toàn cục là 64 thì mảng MinHash của mỗi hàng cũng có độ dài 64
      4. Dùng window function để cộng N giá trị MinHash liên tiếp nhằm bucket hóa mảng hash. Ví dụ cộng từng 4 hàng liên tiếp
        Nếu làm đúng, hãy trải mảng này ra làm “hàng nguồn”, rồi join dataset với chính nó theo từng giá trị MinHash đã bucket hóa, khi đó sẽ có thêm cột “hàng đích”
        Nhóm theo các cột nguồn/đích và đếm số lần xuất hiện thì có thể ước lượng hai hàng giống nhau đến mức nào
        Về bản chất, hai mục càng được hash vào các bucket tương tự nhau thì càng giống nhau; còn từ ngưỡng nào mới tính Jaccard hoặc cosine similarity theo từng cặp thực tế thì bạn tự quyết định
    • Ở đây, cách dùng text embedding và cosine similarity có thể hữu ích: https://simonwillison.net/2023/Oct/23/embeddings/
    • Dùng MinHash có thể tránh ma trận khoảng cách O(N^2) đầy đủ, nhưng nếu chỉ có 600.000 mục thì để đơn giản, cũng có thể tính brute force toàn bộ ma trận
      Điểm mấu chốt là ngân sách thời gian của bạn là bao nhiêu
    • Nếu xem hai mục là đang đề cập đến các từ khóa rất giống nhau thì khoảng cách Jaccard sẽ phù hợp
      Nếu xem hai mục là chia sẻ phần văn bản rất giống nhau thì đáng thử khoảng cách Levenshtein
    • Có thể để LLM tạo chỉ mục đảo cho các mục, nhưng ép nó giữ cardinality thấp
      Khi đó có thể dùng Jaccard similarity

  • Tôi thích bài viết này. Nhóm chúng tôi ở NVIDIA gần đây đã công bố phiên bản tăng tốc GPU của thuật toán khử trùng lặp mờ được mô tả, và có lẽ cộng đồng này cũng sẽ quan tâm
    Repository ở đây: https://github.com/NVIDIA/NeMo-Curator/
    Tài liệu script khử trùng lặp mờ ở đây: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
    Cũng có ví dụ Python: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
    Rất muốn nghe phản hồi

  • Những kỹ thuật kiểu này đọc bằng bài viết thì không hiểu được, nhưng chỉ cần đưa dữ liệu của mình vào ví dụ code chạy được vài lần và xem bên trong diễn ra thế nào là hấp thụ ngay
    Tôi học kỹ thuật này lần đầu từ Douglas Eck: https://research.google/people/douglas-eck/
    Google đã dùng nó để clustering bài hát, và tôi nhớ ông ấy nói về hashing và vector ngẫu nhiên
    Khi đó tôi thấy bối rối vì nghĩ rằng các tối ưu hóa ít tính ngẫu nhiên hơn sẽ hoạt động tốt hơn

    • Trực giác cốt lõi, ít nhất với tôi, là nếu chia đối tượng thành một đống các mảnh rất nhỏ và tạo n cách sắp xếp các đống đó, thì các đối tượng giống nhau sẽ có cùng một mảnh nằm trên cùng trong nhiều cách sắp xếp
      Thêm banding và một chút xác suất vào đó, ta có thể xấp xỉ Jaccard similarity trên dataset khổng lồ theo cách rẻ và rất dễ song song hóa

  • Nếu xem đây là kỹ thuật clustering tài liệu hoặc khử trùng lặp dataset, thì cách “ném machine learning vào vấn đề” sẽ thế nào về chất lượng và hiệu năng so với phương pháp thuật toán rời rạc đơn giản hơn này?
    Ví dụ tạo vector embedding tài liệu bằng một LLM encoder đã pre-train, đưa các vector đó vào vector DB rồi clustering bằng k-means

    • LLM chỉ là một trong nhiều cách tạo embedding
      Muốn dùng k-means thì vẫn phải chọn một hàm khoảng cách như Jaccard, và k-means có lẽ không lý tưởng cho near-duplicate
      Cũng có thể dùng MinHash làm bước tiền xử lý cho k-means để tăng tốc
      Tôi không nghĩ vector DB giúp được nhiều
      Nếu có hàng trăm triệu tài liệu thì có thể dùng nó để tăng tốc tra cứu MinHash sketch, nhưng nhìn chung có lẽ là lựa chọn quá tay
    • Tôi từng thấy cách như vậy hoạt động tốt hơn LSH
      Mỗi khi embedding một tài liệu, trước khi thêm vào sẽ tìm approximate nearest neighbors, nên cũng là O(N) như MinHash
      Các vector index như HNSW và PQ có đánh đổi hiệu năng/chất lượng tốt hơn SimHash LSH, vốn tương ứng với MinHash cho cosine distance
      Chất lượng phụ thuộc vào việc định nghĩa near-duplicate là gì và dùng mô hình embedding nào
      Các mô hình hiện đại hoạt động tốt, và nếu có dữ liệu gán nhãn thì fine-tuning có thể làm tốt hơn nữa
      Nhược điểm chính là chi phí bổ sung để embedding toàn bộ tài liệu, đặc biệt nặng với tài liệu dài
      Nhưng nhờ các mô hình nhỏ, tối ưu hóa tốt hơn và phần cứng nhanh hơn, chi phí này đã giảm rất nhanh