Một trong số những bài toán cơ bản có rất nhiều ứng dụng trong khoa học máy tính là bài toán tìm điểm gần nhất.

Trong bài này ta chỉ xét hàm khoảng cách $d(.,.)$ là khoảng cách Euclidean. Cách đơn giản nhất để thiết kế cấu trúc dữ liệu như vậy là ta sẽ tính khoảng cách giữa mọi cặp điểm, và sau đó lưu vào một mảng hai nhiều (ma trận) $D[\ldots,\ldots]$. Mỗi khi ta nhận được điểm truy vấn $\mathbf{p}$, ta chỉ việc duyệt qua tất cả các điểm khác và đưa ra các điểm có khoảng cách không quá $r$ từ $\mathbf{p}$. Dễ thấy:

1. Xây dựng bảng $D$ mất thời gian $O(n^2d)$ vì ta phải trả thời gian $O(d)$ để tính khoảng cách giữa hai điểm cho trước.
2. Trả lời một truy vấn mất thời gian $O(n)$.

Một số cấu trúc dữ liệu như $k$-$d$ tree có thể sử dụng khi số chiều $d$ nhỏ (thường là 2 hoặc 3 chiều). Ta có thể xây dựng các cấu trúc này trong thời gian $O(n\log n)$ và truy vấn có thể được trả lời trong thời gian $O(\log n)$. Tuy nhiên, sự phụ thuộc của hằng số ẩn sau $O(.)$ trong các cấu trúc này là lũy thừa theo số chiều $d$ (còn gọi là hiện tượng the curse of dimensionality), do đó, nó không phù hợp ngay cả khi $d$ không quá lớn ($d = 20$ chẳng hạn).

Trong thời đại big data hiện nay, ta thường phải tìm điểm gần nhất khi $P$ có tới hàng triệu điểm và các điểm có số chiều cũng lên tới hàng triệu ($d \sim n \geq 10^6$). (Ví dụ thuật toán KNN trong học máy (machine learning) là một biến thể của bài toán tìm điểm gần nhất trên.) Do đó, bài toán trên trở nên vô cùng khó. Cấu trúc dữ liệu bảng ở trên chỉ có thể làm việc khi $n$ cỡ $10000$, còn các cấu trúc như $k$-$d$ tree thì hoàn toàn vô dụng.

Locality Sensitive Hashing (LSH) là một kĩ thuật xấp xỉ dùng để giải quyết tìm điểm gần nhất một cách hiệu quả khi $n$ và $d$ đều vô cùng lớn. Khái niệm này được giới thiệu bởi Indyk và Motwani [1]. Trình bày trong bài này phỏng theo note của Matoušek [2].

Locality Sensitive Hashing

Ý tưởng của LSH là sử dụng một hàm băm $h(.)$ để băm các điểm dữ liệu trong $P$ vào một bảng $T[.]$ sao cho nếu hai điểm $\mathbf{p},\mathbf{q}$ gần nhau thì khả năng cao $\mathbf{p},\mathbf{q}$ sẽ được băm vào cùng một ô. Ngược lại, $\mathbf{p}$ và $\mathbf{q}$ sẽ bị băm vào hai ô khác nhau. Khi trả lời truy vấn, ta chỉ việc tính mã băm $h(\mathbf{p})$ và đưa ra tất cả các điểm lưu trong ô $T[h(\mathbf{p})]$. Hàm băm $h(.)$ như vậy đưcọ gọi là kiểu locality sensitive.

Figure 1: Minh họa một hàm băm locality sensitive.

Trong định nghĩa trên, ta mong muốn $p_{\mathrm{far}}$ gần $0$ còn $p_{\mathrm{close}}$ gần với $1$ vì như vậy, xác suất hai điểm gần nhau được băm vào cùng một ô lớn, còn xác suất hai điểm xa nhau bị băm vào cùng một ô sẽ nhỏ.

Remark 1: Theo định nghĩa trên, với các điểm mà khoảng cách trong khoảng $r \leq d(\mathbf{p}, \mathbf{q}) \leq Cr$ thì ta không quan tâm đến chúng sẽ bị băm vào một ô hay không. Nếu ta chọn hằng số $C$ càng gần $1$ thì số các điểm như vậy càng nhỏ, phương pháp của chúng ta cần chính xác. Tuy nhiên, bạn sẽ thấy dưới đây, thời gian và bộ nhớ của cấu trúc sẽ phụ thuộc vào $C$, theo nghĩa, chúng ta càng muốn độ chính xác cao thì ta càng phải trả nhiều thời gian và bộ nhớ.

Remark 2: Theo định nghĩa trên không chỉ áp dụng đối với không gian Euclidean mà với mọi không gian metric. Trong phạm vi của bài này, ta chỉ quan tâm đến không gian Euclidean.

Xây dựng một LSH family

Để bài toán trở nên đơn giản, ta sẽ giả sử $r = 1$ bằng cách nhân tập các vector (hay điểm) trong $P$ với $1/r$. Như vậy ta đã tiết kiệm được một tham số.

Gọi $\mathbf{Z} = (Z_1,Z_2,\ldots, Z_d) \in \mathbb{R}^d$ là một vector ngẫu nhiên, trong đó mỗi $Z_i \sim \mathcal{N}(0,1)$ là một biến ngẫu nhiên có phân phối chuẩn (standard normal distribution). Gọi $U$ là một số ngẫu nhiên trong đoạn $[0,1)$; $U$ được chọn đồng đều (uniformly), và $w$ là một tham số thực mà ta sẽ định nghĩa sau. Định nghĩa họ các hàm băm $\mathcal{H}_{\mathrm{Gauss}}$ như sau:

Ta sẽ chứng minh xác suất $\mathbf{x}$ và $\mathbf{y}$ bị băm vào cùng một ô xấp xỉ tỉ lệ thuận với khoảng cách giữa hai điểm $\mathbf{x}$ và $\mathbf{y}$.

 
Trước khi đi vào chi tiết chứng minh, ta xét ý nghĩa của Lemma 1. Do $w$ là tham số ta có thể tùy chọn, ta sẽ chọn $w$ đủ lớn. Khi đó phần $o(\frac{1}{w}))$ trong phương trình (2) sẽ đóng góp không đáng kể và xác suất $\mathrm{Pr}[h(\mathbf{x}) \not= h(\mathbf{y})]$. Do đó, ta có thể coi xác suất này là tỉ lệ thuận với khoảng cách giữa hai điểm $\mathbf{x}$ và $\mathbf{y}$. Điều đó có nghĩa là $\mathbf{x}$ và $\mathbf{y}$ càng gần nhau thì xác suất chúng được băm vào cùng một ô càng lớn. Đây chính là điều mà chúng ta cần.

Chú ý, trong phần này ta đang giả sử $r = 1$. Từ $(2)$ ta suy ra, họ hàm băm $\mathcal{H}$ định nghĩa như trong phương trình $(1)$ là một họ $(r,Cr,p_{\mathrm{close}}, p_{\mathrm{far}})$-sensitive với $p_{\mathrm{close}} = 1 - \sqrt{\frac{2}{\pi}}\frac{1}{w} + o(\frac{1}{w}) $ và $p_{\mathrm{far}} = 1 - \sqrt{\frac{2}{\pi}}\frac{C}{w} + o(\frac{1}{w}) $.

Để chứng minh Lemma 1, ta cần sử dụng hai tính chất sau đây:

Chứng minh Lemma 1: Gọi $s = d(\mathbf{x}, \mathbf{y})$ là khoảng cách giữa hai điểm $\mathbf{x}$ và $\mathbf{y}$ và $p(s)$ là xác suất $\mathbf{x}$ và $\mathbf{y}$ bị băm vào cùng một ô. Theo Fact 1, ta có:

$\mathrm{Pr}[h(\mathbf{x}) \not= h(\mathbf{y}) | \mathbf{Z} ] = \min(1, \frac{|\langle \mathbf{Z}, \mathbf{x} - \mathbf{y} \rangle|}{w}) \qquad(5)$

Theo Fact 2, $X = \langle \mathbf{Z}, \mathbf{x} - \mathbf{y} \rangle$ là một phân phối chuẩn có mean $0$ và độ lệch tiêu chuẩn $d^2(\mathbf{x},\mathbf{y}) = s^2$. Do đó, $t = X/s$ phân bố theo $\mathcal{N}(0,1)$. Từ đó suy ra :

$\begin{array} {l} p(s) &= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{+\infty} \min(1, |\frac{s}{w}t|) e^{-t^2/2} dt \\ & = \mathrm{Pr}[|t|\geq \frac{w}{s}] + \frac{s}{w} \int_{-w/s}^{w/s}|t| e^{-t^2/2} dt \\
&= \mathrm{Pr}[|t|\geq \frac{w}{s}] + \frac{s}{w} E[|t|] + \frac{2}{\sqrt{2\pi}} \frac{s}{w}\int_{w/s}^{+\infty} te^{-t^2/2} \end{array} \qquad (6)$

Trong các bài tập dưới đây, mình sẽ hướng dẫn các bạn chứng minh các tính chất sau:

• $\mathrm{Pr}[|t|\geq \frac{w}{s}] = o(\frac{1}{w})$.
• $E[|t|] = \sqrt{2/\pi}$ với $t \sim \mathcal{N}(0,1)$.
• $\frac{s}{w}\int_{w/s}^{+\infty} te^{-t^2/2} = o(\frac{1}{w})$

Do đó, từ $(6)$, ta suy ra dpcm.

Xây dựng cấu trúc NNS từ LSH

Có mấy vấn đề mà chúng ta chưa nói rõ phần trước về họ hàm băm $\mathcal{H}$ trong $(1)$. Thứ nhất ta mới chỉ nói chọn $w$ đủ lớn, nhưng chưa nói chọn $w$ lớn bao nhiêu là vừa. Thứ hai, đầu ra của hàm băm trong $(1)$ là toàn bộ không gian $\mathbb{Z}$, mà để thực hiện được trên máy tính, đầu ra phải hữu hạn (và phải không quá lớn so với $n$ để cấu trúc của chúng ta trở nên hiệu quả). Cả hai vấn đề sẽ được làm rõ trong phần này.

Trước hết, ta giả sử đã có sẵn một họ $(r, Cr, p_{\mathrm{close}},p_{\mathrm{far}})$-sensitive $\mathcal{H}$. Gọi:

$\alpha = \frac{\ln p_{\mathrm{close}}}{ \ln p_{\mathrm{far}}} \qquad (7)$

Theo định nghĩa của $\mathcal{H}$, ta chỉ biết rằng $p_{\mathrm{close}} - p_{\mathrm{far}} $ > $0$, chứ ta chưa biết sự khác biệt này lớn bao nhiêu. Đầu tiên ta sẽ khuếch đại (amplify) khoảng cách này bằng cách ghép nhiều hàm băm trong họ $\mathcal{H}$ lại với nhau.

Gọi $t$ là một số nguyên mà ta sẽ xác định sau. Ta định nghĩa một họ hàm băm mới $\mathcal{G}_t$ trong đó mỗi hàm băm $g \in \mathcal{G}_t$ là ghép của $t$ hàm băm độc lập trong $\mathcal{H}$. Một cách hình thức:

$\mathcal{G}_t = \{ g= (h_1,h_2,\ldots,h_t): h_1,h_2,\ldots,h_t \in \mathcal{H} \} \qquad (8)$

Dễ thấy, $g(\mathbf{x}) = g(\mathbf{y})$ khi và chỉ khi $h_i(\mathbf{x}) = h_i(\mathbf{y})$ với mọi $i, 1\leq i \leq t$. Do đó, $\mathcal{G}_t$ là một họ $(r, Cr, p^t_{\mathrm{close}},p^t_{\mathrm{far}})$-sensitive.

Đầu ra của mỗi hàm băm $g(.)$ trong $\mathcal{G}_t$ là một bộ $t$ số nguyên ($t$-tuple) chứ không phải là một số. Ta có thể sử dụng thêm một hàm băm nữa để băm đầu ra của $g(.)$ về các số nguyên trong khoảng $[0, O(n)]$, phục vụ cho mục đích tìm kiếm. Thiết kế hàm băm đó như thế nào thì bạn đọc có thể xem trong bài bảng băm mình đã viết trước đây.

Mặc dù băm thêm một lần nữa có thể vẫn xảy ra đụng độ, để phân tích dưới đây được đơn giản, ta sẽ giả sử không xảy ra đụng độ trong lần băm cuối cùng. Do đó, ta có thể coi $g(.)$ như là một hàm băm để băm vào bảng lưu trữ.

Tiếp theo, ta xây dựng $L$ bảng băm $T[1][],T[2][], \ldots T[L][]$ trong đó mỗi bằng băm $T[j][]$ ta sử dụng hàm băm $g_j$ chọn ngẫu nhiên từ $\mathcal{G}_t$ để băm toàn bộ các điểm dữ liệu vào $T[j][]$. Gọi $G = \{g_1,\ldots, g_L\}$ là tập $L$ hàm băm đã chọn ra từ $\mathcal{G}_t$. Thủ tục tìm kiếm các điểm gần nhất sẽ như sau:

Mục đích của biến $k$ ở trên là để ghi nhớ xem chúng ta đã kiểm tra bao nhiêu điểm $\mathbf{q}$. Nếu số điểm chúng ta kiểm tra lớn hơn $3L$ thì ta sẽ dừng và coi như không có điểm nào gần $\mathbf{p}$ cả.

Thủ tục trên chỉ trả về một điểm $\mathbf{q}$ có khoảng cách tới $\mathbf{p}$ không quá $Cr$. Ta có thể dễ dàng sửa đổi thủ tục trên để trả về số điểm hơn (nếu có).

 
Chứng minh: Tính mỗi mã băm $g_j(\mathbf{p})$ mất thời gian $O(T_h t)$. Do ta có $L$ bảng băm, tổng thời gian để băm toàn bộ $P$ vào tất cả các bảng là $g_j(\mathbf{p})L$.

Do mỗi bảng băm có bộ nhớ $O(n)$, tổng bộ nhớ của $L$ bảng băm là $O(Ln)$.

Mỗi lần truy vấn, ta phải trả thời gian $O(T_ht)$ để tính 1 mã băm. Do đó, tổng thời gian để tính $L$ mã băm là $O(T_htL)$.

Xác định các tham số

Trong phần này ta sẽ xác định hai tham số quan trọng $t, L$. Các tham số này có ảnh hưởng tới tốc độ, bộ nhớ cũng như độ chính xác của cấu trúc.

Từ thủ tục NNS, ta dễ thấy nếu thủ tục đó trả về một điểm $\mathbf{q}$ thì khoảng cách $d(\mathbf{p},\mathbf{q}) \leq Cr$. Chú ý, mục tiêu ban đầu của chúng ta tìm điểm $\mathbf{q}$ sao cho $d(\mathbf{p},\mathbf{q}) \leq r$. Do đó, cấu trúc này chỉ trả về một điểm xấp xỉ gần với $\mathbf{p}$.

Nếu không tồn tại điểm $\mathbf{q}$ mà $d(\mathbf{p},\mathbf{q}) \leq r$ thì thủ tục NNS có thể trả về một điểm, nhưng cũng có thể không trả về điểm nào cả. Điều này không quan trọng vì bài toán của chúng ta không yêu cầu trả về nếu như không tồn tại điểm $\mathbf{q}$ như vậy. Tuy nhiên, nếu có tồn tại ít nhất một điểm $\mathbf{q}$ mà $d(\mathbf{p},\mathbf{q}) \leq r$ thì thủ tục NNS có trả về hay không? Phần này ta sẽ tìm hiểu câu trả lời cho câu hỏi này.

 
Chứng minh: Chú ý $\alpha$ là tham số ta định nghĩa trong phương trình (7). Có hai trường hợp thuật toán trả về $\emptyset$ mặc dù vẫn tồn tại điểm $\mathbf{q}$ có khoảng cách tới $\mathbf{p}$ không quá $r$: (TH1) điểm $\mathbf{q}$ bị băm vào ô khác với $\mathbf{p}$ trong toàn bộ $L$ bảng băm và (TH2) khi ta đã kiểm tra $3L$ điểm mà vẫn không tìm ra điểm nào nằm có khoảng cách tới $\mathbf{p}$ không quá $Cr$. Ta lần lượt tính xác suất xảy ra một trong 2 trường hợp:

TH1: Do $\mathcal{G}$ là một họ $(r, Cr, p^t_{\mathrm{close}},p^t_{\mathrm{far}})$-sensitive, với mỗi $j$, xác suất để $g_j(\mathbf{q}) \not= g_j(\mathbf{p}) $ là $(1 - p^t_{\mathrm{close}})$. Do đó, xác suất để TH1 xảy ra là:

$P_1 = (1 - p^t_{\mathrm{close}})^L \leq e^{- p^t_{\mathrm{close}}L} \qquad (9)$

Ở trên, ta sử dụng bất đẳng thức $1 - x \leq e^{-x}$.

TH2: Trường hợp này xả ra khi ít nhất $3L$ điểm bị băm vào cùng ô với $\mathbf{p}$ mà điểm nào cũng có khoảng cách lớn hơn $Cr$. Do $\mathcal{G}$ là một họ $(r, Cr, p^t_{\mathrm{close}},p^t_{\mathrm{far}})$-sensitive, xác suất để một điểm có khoảng cách lớn hơn $Cr$ bị băm vào cùng ô $T[j][g_j(\mathbf{p})]$ là không quá $p^t_{\mathrm{far}}$. Do đó, theo tính tuyến tính của kì vọng, kì vọng số điểm bị băm cùng vào một ô nào đó với $\mathbf{p}$ trong $L$ bảng băm là không quá $nL^t_{\mathrm{far}}$. Theo bất đẳng thức Markov, xác suất để xảy ra nhiều hơn $3L$ điểm bị băm vào cùng ô với $\mathbf{p}$ như vậy là không quá:

$P_2 = \frac{nLp^t_{\mathrm{far}}}{3L}= \frac{np^t_{\mathrm{far}}}{3} \qquad (10)$

Chọn $t = \frac{\ln(n)}{\ln (1/p_{\mathrm{far}})}$, ta có $P_2 \leq 1/3$. Chọn

$L = p^{-t}_{\mathrm{close}} = e^{\ln(p_{\mathrm{close}}))\ln(n)/\ln(p_{\mathrm{far}}))} = n^{\alpha} \qquad (11)$

từ (9) ta suy ra $P_1 \leq e^{-1}$. Do đó, xác suất xảy ra một trong hai trường hợp, theo công thức cộng xác suất, là không quá $1/3 + e^{-1} \leq 3/4$.

Phần còn lại của Theorem 1, ta chỉ việc thay các tham số $t, L$ vào Lemma 2. Chú ý, $T_h = O(d)$ với $d$ là số chiều của các điểm dữ liệu.

Bây giờ ta quay trở lại xác định tham số $w$ trong phương trình (1). Trong phần phân tích ở trên, ta đã chỉ ra, chỉ cần chọn $w$ đủ lớn thì $p_{\mathrm{close}} \sim 1 - \sqrt{\frac{2}{\pi}}\frac{1}{w}$ và $p_{\mathrm{far}} \sim 1 - \sqrt{\frac{2}{\pi}}\frac{C}{w}$. Lúc đó, ta sẽ có:

$\alpha = \frac{\ln (1 - \sqrt{\frac{2}{\pi}}\frac{1}{w})}{\ln(1 - \sqrt{\frac{2}{\pi}}\frac{C}{w})} \sim \frac{- \sqrt{\frac{2}{\pi}}\frac{1}{w}}{- \sqrt{\frac{2}{\pi}}\frac{C}{w}} = \frac{1}{C} \qquad (11)$

Ở phương trình (11), ta sử dụng công thức xấp xỉ $1 - x \sim e^{-x}$. Công thức xấp xỉ này gần chính xác khi $x \rightarrow 0$, có nghĩa là khi $w\rightarrow +\infty$ (coi $C$ như một hằng số). Ta có:

Ý nghĩa của Lemma 3 là nếu ta chấp nhận tỉ lệ xấp xỉ $C$ càng lớn thì thời gian và bộ nhớ của cấu trúc NNS càng nhỏ.

Điểm cuối cùng mà mình muốn nhấn mạnh trước khi kết thúc bài này đó là xác suất $0.25$ trong Theorem 1 có vẻ không tốt lắm. Thực ra con số $0.25$ phát biểu trong đó chỉ làm cho phép chứng minh trở nên đơn giản hơn mà thôi. Có nhiều cách để khuếch đại xác suất này lên $1-\epsilon$ với $\epsilon $ nhỏ tùy ý (ví dụ $\epsilon = 0.01$ thì xác suất là $0.99$). Cách đơn giản nhất là sửa đổi cách chọn $t$ và $L$ trong chứng minh Theorem 1. Chi tiết coi như bài tập cho bạn đọc (bài tập 4).

Remark 3: Nếu $d \sim n$ thì thời gian truy vấn của cấu trúc NNS $O(n^{1+\alpha})$. Thời gian này vẫn quá lớn so với thực tế. Một cách để giảm $d$ về $O(\log n)$ là sử dụng bổ đề Johnson-Lindenstrauss.

Additional readings: Năm 2013, Adoni and Indyk cải tiến cấu trúc NNS ở trên để đạt được thời gian truy vấn xấp xỉ $O(dn^{1/C^2})$ (đối chiếu với Lemma 3). Trong survey này của Adoni, Indyk và Razenshteyn có nhắc đến nhiều kĩ thuật LSH cho các norm khác $\ell_1, \ell_\infty$. Trên trang web của Adoni còn rất nhiều tài liệu liên quan để các bạn tham khảo: http://www.mit.edu/~andoni/LSH/.

Tham khảo

[1] P. Indyk and R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. ACM, 1998.
[2] J. Matoušek. Lecture Notes on Metric Embeddings. Technical Report, ETH Zürich, 2013.
[3] A. Andoni and P. Indyk. Near-optimal Hashing Algorithms for Approximate nNearest Neighbor in High Dimensions. The 47th Annual IEEE Symposium on.Foundations of Computer Science (FOCS'06), 2006.

Bài tập

Bài tập 1: Chứng minh Fact 1. Gợi ý: không mất tính tổng quát, giả sử $b \geq a$. Viết $[b + U] = [a + (b-a) + U]$ rồi xét các trường hợp $b-a \geq 1$ và $b-a$ < $1$.

Bài tập 2: Chứng minh rằng $\mathrm{Pr}[t \geq w/s] = o(1/w)$ khi $t \sim \mathcal{N}(0,1)$, giả sử $w$ rất lớn và $s$ là một hằng số. Gợi ý: sử dụng bất đẳng thức $e^{x} \geq x^2/2$, ta có:

$\mathrm{Pr}[t \geq w/s] = \int_{w/s}^{+\infty} e^{-t^2} dt \leq \int_{w/s}^{+\infty} 2t^{-4} dt $

Bài tập 3: Sử dụng ý tưởng trong lời giải bài tập 2, chứng minh các bất đẳng thức đã sử dụng trong chứng minh Lemma 1 sau đây:

• $\mathrm{Pr}[|t|\geq \frac{w}{s}] = o(\frac{1}{w})$ khi $t\sim \mathcal{N}(0,1)$.
• $\frac{s}{w}\int_{w/s}^{+\infty} te^{-t^2/2} = o(\frac{1}{w})$

Bài tập 4: Trong Theorem 1, ta đã chứng minh xác suất thuật toán tìm được một điểm $\mathbf{q}$ có khoảng cách tới $\mathbf{p}$ là $0.25$. Chứng minh rằng xác suất này là $1-\epsilon$ nếu ta chọn $t = \frac{\ln(n)}{\ln (1/p_{\mathrm{far}})\epsilon}$ và $L = n^{\alpha}\ln(\frac{1}{\epsilon})$. Sử dụng bất đẳng thức Chernoff để giảm sự phụ thuộc của $t$ vào $\epsilon$ xuống còn $O(\frac{\ln(n)}{\ln (1/p_{\mathrm{far}})}\ln(\frac{1}{\epsilon})$.