Hai thuật toán để tìm hàng xóm gần nhất với băm nhạy cảm về địa phương, cái nào?

Question

Hiện tại tôi đang nghiên cứu cách tìm một người hàng xóm gần nhất bằng cách sử dụng băm nhạy cảm theo địa phương. Tuy nhiên trong khi tôi đang đọc các bài báo và tìm kiếm trên web, tôi tìm thấy hai thuật toán để thực hiện việc này:

1- Sử dụng L số bảng băm với L số ngẫu nhiên các chức năng LSH, do đó tăng cơ hội hai tài liệu tương tự có cùng chữ ký. Ví dụ: nếu hai tài liệu tương tự 80%, thì có 80% cơ hội là chúng sẽ có cùng chữ ký từ một hàm LSH. Tuy nhiên, nếu chúng ta sử dụng nhiều hàm LSH, thì có cơ hội cao hơn để nhận được cùng một chữ ký cho các tài liệu từ một trong các hàm LSH. Phương pháp này được giải thích trong wikipedia và tôi hy vọng hiểu biết của tôi là chính xác:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- Các thuật toán khác sử dụng một phương pháp từ một bài báo (phần 5) gọi là: Sự tương đồng Estimation Techniques từ vị trí còn thuật toán bởi Moses S. Charikar. Nó dựa trên việc sử dụng một hàm LSH để tạo chữ ký và sau đó áp dụng các hoán vị P trên nó và sau đó sắp xếp danh sách. Trên thực tế tôi không hiểu phương pháp rất tốt và tôi hy vọng nếu ai đó có thể làm rõ nó.

Câu hỏi chính của tôi là: tại sao mọi người lại sử dụng phương pháp thứ hai thay vì phương pháp đầu tiên? Như tôi thấy nó dễ dàng hơn và nhanh hơn.

Tôi thực sự hy vọng ai đó có thể trợ giúp !!!

EDIT: Thực ra tôi không chắc chắn nếu @ Raff.Edward được trộn giữa "đầu tiên" và "giây". Bởi vì chỉ có phương pháp thứ hai sử dụng một bán kính và đầu tiên chỉ sử dụng một gia đình băm mới g bao gồm các gia đình băm F. Vui lòng kiểm tra các liên kết wikipedia. Họ chỉ sử dụng nhiều hàm g để tạo ra các chữ ký khác nhau và sau đó cho mỗi hàm g nó có một bảng băm tương ứng. Để tìm người hàng xóm gần nhất của một điểm, bạn chỉ cần để cho điểm này đi qua các hàm g và kiểm tra các bảng băm tương ứng cho các xung đột. Vì vậy, làm thế nào tôi hiểu nó như là chức năng nhiều hơn ... nhiều cơ hội cho va chạm.

Tôi không tìm thấy bất kỳ đề cập nào về bán kính cho phương pháp đầu tiên.

Đối với phương pháp thứ hai, chúng chỉ tạo một chữ ký cho mỗi vectơ đặc trưng và sau đó áp dụng các hoán vị P trên chúng. Bây giờ chúng ta có P danh sách hoán vị trong đó mỗi ho chứa n chữ ký. Bây giờ họ sắp xếp mỗi danh sách từ P. Sau khi cho điểm truy vấn q, chúng tạo chữ ký cho nó và sau đó áp dụng các hoán vị P trên nó và sau đó sử dụng tìm kiếm nhị phân trên mỗi danh sách P được hoán vị và sắp xếp để tìm chữ ký tương tự nhất truy vấn q. Tôi đã kết luận điều này sau khi đọc nhiều bài báo về nó, nhưng tôi vẫn không hiểu tại sao bất cứ ai sử dụng một phương pháp như vậy bởi vì nó không có vẻ nhanh chóng trong việc tìm kiếm khoảng cách ham mê!

Đối với tôi, tôi chỉ cần làm như sau để tìm người hàng xóm gần nhất cho một điểm truy vấn q. Với một danh sách chữ ký N, tôi sẽ tạo chữ ký cho điểm truy vấn q và sau đó quét danh sách N và tính toán khoảng cách hamming giữa mỗi phần tử trong N và chữ ký của q. Vì vậy, tôi sẽ kết thúc với hàng xóm gần nhất cho q. Và phải mất O (N) !!!

Answer 1

Sự hiểu biết của bạn về điều đầu tiên là một chút. Xác suất xảy ra va chạm không tỷ lệ thuận với độ tương đồng, nhưng có hay không nhỏ hơn bán kính được xác định trước. Mục đích là bất cứ thứ gì trong bán kính sẽ có khả năng va chạm cao và bất kỳ thứ gì bên ngoài bán kính * (1 + eps) sẽ có cơ hội va chạm thấp (và khu vực giữa có chút ít âm u).

Thuật toán đầu tiên thực sự khá khó thực hiện tốt, nhưng có thể nhận được kết quả tốt.Đặc biệt, thuật toán đầu tiên là cho các chỉ số L1 và L2 (và về mặt kỹ thuật một vài chi tiết).

Thuật toán thứ hai rất đơn giản để triển khai, mặc dù triển khai ngây thơ có thể sử dụng quá nhiều bộ nhớ để hữu ích tùy thuộc vào kích thước sự cố của bạn. Trong trường hợp này, xác suất va chạm tỷ lệ thuận với độ tương tự của các đầu vào. Tuy nhiên, nó chỉ hoạt động cho tính tương tự Cosine (hoặc các số liệu khoảng cách dựa trên biến đổi tương tự.)

Vì vậy, bạn sẽ sử dụng cái nào dựa vào số liệu khoảng cách bạn đang sử dụng cho gần nhất.).

Cách thứ hai thực sự dễ hiểu và dễ thực hiện hơn cái đầu tiên, bài báo chỉ rất dài dòng.

Phiên bản ngắn: Lấy một vector ngẫu nhiên V và cung cấp cho mỗi chỉ mục một giá trị ngẫu nhiên đơn vị ngẫu nhiên độc lập. Tạo nhiều vectơ như bạn muốn có độ dài chữ ký. Chữ ký là dấu hiệu của mỗi chỉ số khi bạn làm một sản phẩm Vector Ma trận. Bây giờ khoảng cách hamming giữa hai chữ ký bất kỳ liên quan đến sự giống nhau về cosin giữa các điểm dữ liệu tương ứng.

Vì bạn có thể mã hóa chữ ký thành mảng int và sử dụng lệnh XOR với hướng dẫn đếm bit để thu được khoảng cách rất nhanh, bạn có thể nhận được điểm tương đồng cosin tương đối rất nhanh.

Thuật toán LSH không có nhiều tiêu chuẩn hóa và hai giấy tờ (và các giấy tờ khác) sử dụng các định nghĩa khác nhau, do đó, tất cả đôi khi hơi khó hiểu. Gần đây tôi chỉ triển khai cả hai thuật toán trong số JSAT và tôi vẫn đang làm việc để hiểu rõ cả hai thuật toán này.

EDIT: Trả lời chỉnh sửa của bạn. Bài viết wikipedia không phải là tuyệt vời cho LSH. Nếu bạn đọc original paper, phương pháp đầu tiên bạn đang nói về chỉ hoạt động cho một bán kính cố định. Các hàm băm sau đó được tạo dựa trên bán kính đó và được nối với nhau để tăng khả năng đến gần các điểm trong một va chạm. Sau đó, họ xây dựng một hệ thống để làm k-NN trên đầu trang này bằng cách xác định giá trị tối đa của k chúng wan, và sau đó tìm kiếm lớn nhất hợp lý khoảng cách họ sẽ tìm thấy hàng xóm gần nhất. tìm kiếm bán kính sẽ rất có khả năng trả về bộ k-NN. Để tăng tốc độ này, chúng cũng tạo ra một vài bán kính cực nhỏ vì mật độ thường không đồng đều và bán kính nhỏ hơn bạn sử dụng, kết quả càng nhanh.

Phần wikipedia bạn liên kết được lấy từ mô tả giấy cho phần "Phân phối ổn định", trình bày hàm băm cho tìm kiếm bán kính r = 1.

Đối với bài báo thứ hai, "sắp xếp" bạn mô tả không phải là một phần của băm, mà là một phần của một lược đồ để tìm kiếm không gian hamming nhanh hơn. Như tôi đã đề cập, gần đây tôi đã thực hiện điều này, và bạn có thể thấy a quick benchmark I đã sử dụng tìm kiếm bạo lực vẫn còn nhanh hơn nhiều so với phương pháp ngây thơ của NN. Một lần nữa, bạn cũng sẽ chọn phương pháp này nếu bạn cần sự tương tự cosin trên khoảng cách L2 hoặc L1. Bạn sẽ tìm thấy nhiều giấy tờ khác đề xuất các đề án khác nhau để tìm kiếm không gian hamming được tạo ra bởi các chữ ký.

Nếu bạn cần trợ giúp thuyết phục bản thân, bạn có thể nhanh hơn ngay cả khi bạn vẫn đang làm vũ lực - chỉ cần nhìn theo cách này: Giả sử tài liệu thưa thớt trung bình có 40 từ chung với tài liệu khác (một số rất bảo thủ kinh nghiệm của tôi). Bạn có n tài liệu để so sánh. Sau đó, độ tương đồng cosin vũ phu sẽ bao gồm khoảng 40 * n phép nhân dấu chấm động (và một số công việc phụ). Nếu bạn có một chữ ký 1024 bit, thì chỉ có 32 số nguyên. Điều đó có nghĩa là chúng ta có thể thực hiện tìm kiếm LSH vũ phu trong các hoạt động số nguyên 32 * n, hoạt động nhanh hơn đáng kể sau đó.

Ngoài ra còn có các yếu tố khác khi chơi ở đây. Đối với một tập dữ liệu thưa thớt, chúng tôi phải giữ cả chỉ số tăng gấp đôi và số nguyên để biểu thị các chỉ số không bằng 0, do đó sản phẩm chấm thưa thớt đang thực hiện rất nhiều hoạt động số nguyên bổ sung để xem các chỉ số nào có chung. LSH cũng cho phép chúng ta tiết kiệm bộ nhớ, bởi vì chúng ta không cần phải lưu trữ tất cả các số nguyên và tăng gấp đôi cho mỗi véc tơ, thay vào đó chúng ta chỉ có thể giữ băm của nó xung quanh - đó chỉ là một vài byte. Việc sử dụng bộ nhớ giảm có thể giúp chúng tôi khai thác bộ nhớ cache CPU tốt hơn.

O (n) là cách ngây thơ mà tôi đã sử dụng trong bài đăng trên blog của mình. Và nó nhanh. Tuy nhiên, nếu bạn sắp xếp các bit trước khi bàn tay, bạn có thể thực hiện tìm kiếm nhị phân trong O (log (n)). Ngay cả khi bạn có L trong số các danh sách này, L < < n, và vì vậy nó sẽ nhanh hơn. Vấn đề duy nhất là nó giúp bạn thu hẹp gần đúng NN mà đã xấp xỉ độ tương tự của cosin, vì vậy kết quả có thể trở nên tồi tệ hơn một chút. Nó phụ thuộc vào những gì bạn cần.