Chủ đề của bài này là bổ đề Johnson-Lindenstrauss [1], một công cụ được sử dụng rất nhiều để giảm chiều dữ liệu. Về các ứng dụng cụ thể của bổ đề mình khuyến khích các bạn tự Google, do ở đây mình không có nhiều không gian để viết về vấn đề đó.

Bài này mang tính chất giới thiệu ý tưởng là chính, sau đó là một chút "hương vị" trong chứng minh bổ đề. Lối trình bày của bài này xuất phát từ [8]. Mình sẽ vạch ra con đường để chứng minh và khuyến khích bạn đọc tự "lấp đầy" những đoạn bỏ trống của bài viết. Lời giải đầy đủ của những đoạn bỏ trống mình sẽ liên kết đến tài liệu tham khảo. Trước hết chúng ta phát biểu bổ đề:

Johnson-Lindenstrauss Lemma: Cho một số cố định \epsilon \in (0,1) và một tập n điểm P = \{x_1,x_2,\ldots, x_n\} trong không gian Euclidean \mathrm{R}^d. Tồn tại một hàm F: \mathrm{R}^d \rightarrow \mathrm{R}^k, với k = \frac{20\log n}{\epsilon^2}, ánh xạ mỗi điểm x_i trong không gian gốc \mathrm{R}^d vào một điểm F(x_i) trong không gian \mathrm{R}^k thỏa mãn:

(1-\epsilon)||x_i-x_j||_2 \leq ||F(x_i) - F(x_j)||_2 \leq (1+\epsilon)||x_i-x_j||_2 \quad \forall i\not= j \in \{1,2,\ldots, n\}\qquad (1)

 
Ở đây ||.||_2\ell_2 norm. Từ nay về sau, ta viết tắt Johnson-Lindenstrauss Lemma là JLL.

Ý nghĩa của JLL: Trong một số ứng dụng big data, số chiều của dữ liệu rất lớn, xấp xỉ số điểm dữ liệu. Ví dụ n = d = 10^9. Sử dụng JLL, ta có thể chiếu lượng dữ liệu này về không gian cỡ \frac{600}{\epsilon^2} để đảm bảo khoảng cách giữa hai điểm dữ liệu bất kì thay đổi không quá \epsilon lần. Ta có thể lấy \epsilon = 1/2 thì số chiều cần thiết là không quá 2400, nhỏ hơn nhiều lần số chiều gốc là 10^9.

Remark 1: Con số k = \frac{20\log n}{\epsilon^2} là con số lý thyết để đảm bảo sự tồn tại của F(.). Con số thực tế cần thiết thường nhỏ hơn rất nhiều (cỡ vài trăm).

Remark 2: Phát biểu của bổ đề trên mới đảm bảo tồn tại của hàm F(.). Chứng minh dưới đây sẽ cho chúng ta một thuật toán (ngẫu nhiên) để tìm ra F(.).

Remark 3: Bổ đề JLL thường được ứng dụng để tiền xử lí (preprocess) dữ liệu trước khi đi vào xử lí sâu hơn (ví dụ phân loại hoặc phần cụm dữ liệu). JLL chỉ bảo toàn khoảng cách giữa mọi cặp điểm, do đó, chúng ta cần phải cẩn thận trong việc ứng dụng JLL tiền xử lí. Ví dụ ta muốn phân loại dữ liệu thì tiền xử lí bằng JLL chưa chắc đã là tốt (có thể dùng LDA thay thế). Nếu muốn phân cụm dữ liệu thì có lẽ JLL áp dụng được. Trong phần Example của note [3], Jelani Nelson chứng minh rằng JLL có thể dùng để tiền xử lí cho thuật toán k-means.

Remark 4: Theo JLL, k \sim \frac{1}{\epsilon^2}. Quan hệ phụ thuộc giữa k\epsilon đã được Larsen và Nelson [5] chứng minh là tối ưu về mặt lý thuyết.

Remark 5: Có hai phiển bản khác của JLL: phiên bản Fast JLL [6] và phiên bản Sparse JLL [7]. Bạn đọc có thể tham khảo thêm trong note [4] của Jelani Nelson.

Phác họa chứng minh

Trong phần này mình sẽ phác họa (sketch) chứng minh (cũng như đi tìm hàm F(.)) của JLL. Lemma 1 dưới đây cho ta biết, hàm F(.) chỉ đơn giản là một ma trận với các phần tử được chọn ngẫu nhiên từ phân bố chuẩn (normal distribution) \mathcal{N}(0,1). Cuối bài mình sẽ thảo luận 2 cách khác để tìm hàm F(.).

Lemma 1: Gọi x \in \mathbb{R}^d là một vector d chiều và A \in \mathbb{R}^{k\times d} là một ma trận thực có kích thước k \times d trong đó mỗi phần tử của ma trận được sample độc lập với nhau từ phân bố \mathcal{N}(0,1). Đặt F(x) = \frac{1}{\sqrt{k}} A\cdot x. Ta có:

\mathrm{Pr}[(1-\epsilon)||x||_2 \leq ||F(x)||_2 \leq (1+\epsilon)||x||_2] \geq 1 - 2e^{\frac{-(\epsilon^2 - \epsilon^3)k}{4}} \qquad (2)

 

Chứng minh JLL từ Lemma 1: Phương pháp chứng minh là sử dụng union-bound. Bạn có thể xem lại một số khái niệm cơ bản về xác suất tại đây.

Xác suất để một cặp x_i,x_j bất kì không thỏa mãn phương trình (1), theo Lemma 1 (cho x = x_i - x_j), là không quá  2e^{\frac{-(\epsilon^2 - \epsilon^3)k}{4}}. Do đó, xác suất đề tồn tại một cặp x_i,x_j bất không thỏa mãn phương trình (1) là không quá  2n^2e^{\frac{-(\epsilon^2 - \epsilon^3)k}{4}}. Do đó, xác xuất để F(x) = \frac{1}{\sqrt{k}} A\cdot x thỏa mãn phương trình (1) với mọi cặp x_i,x_jít nhất:

1 -2n^2e^{\frac{-(\epsilon^2 - \epsilon^3)k}{4}} \qquad (3)

Xác suất này lớn hơn 0 khi k = \frac{20\log n}{\epsilon^2}. Một sự kiện có xác suất lớn hơn không khi và chỉ khó nó tồn tại. Điều đó có nghĩa là tồn tại F(x) = \frac{1}{\sqrt{k}} A\cdot x thỏa mãn JLL.


Từ đây về sau, ta sẽ tập trung chứng minh Lemma 1. Bằng cách chia hay vế của bất đẳng thức:

(1-\epsilon)||x||_2 \leq ||F(x)||_2 \leq (1+\epsilon)||x||_2

cho ||x||_2, ta có thể giả sử ||x||_2 = 1. Do đó, ta chỉ cần chứng minh:

\mathrm{Pr}[(1-\epsilon)\leq ||F(x)||_2 \leq (1+\epsilon)] \geq 1 - 2e^{\frac{-(\epsilon^2 - \epsilon^3)k}{4}} \forall x \mbox{ s.t } ||x||_2 = 1\qquad (4)

Đặt:

Y_i = \sum_{j=1}^d A[i,j]x_j \qquad (5)

Ta có:

||F(x)||_2^2 = \frac{1}{k}\sum_{i=1}^k Y^2_i \qquad (6)

Do A[i,j] \sim \mathcal{N}(0,1), từ (4) suy ra Y_i chính là một tổ hợp tuyến tính (linear combination) của các biến ngẫu nhiên Gauss đồng nhất và phân phối độc lập. Ta nhắc lại tính chất sau của phân phối \mathcal{N}(0,1):

Fact 1: Nếu Z_1, Z_2 là hai biến ngẫu nhiên độc lập tuân theo phân bố chuẩn \mathcal{N}(0,1)Z = aZ_1 + bZ_2 với a,b là hai số thực thì:

Z \sim \mathcal{N}(0,a^2+b^2) \qquad(7)

 
Fact 1 kết hợp với quy nạp và điều kiện ||x||_2 = 1, ta suy ra:

Y_i \sim \mathcal{N}(0,1)  \quad \forall 1 \leq i \leq k\qquad(8)

Ta biến đổi vế trái của (4) như sau:

\begin{array} {l} &\mathrm{Pr}[(1-\epsilon)\leq ||F(x)||_2 \leq (1+\epsilon)]  \\ &=   \mathrm{Pr}[(1-\epsilon)^2\leq ||F(x)||^2_2 \leq (1+\epsilon)^2]  \\ & \geq  \mathrm{Pr}[(1-\epsilon)\leq ||F(x)||^2_2 \leq (1+\epsilon)] \\ & =  \mathrm{Pr}[(1-\epsilon)\leq  \frac{1}{k}\sum_{i=1}^k Y^2_i  \leq (1+\epsilon)] \\  &= \mathrm{Pr}[k(1-\epsilon)\leq  \sum_{i=1}^k Y^2_i  \leq (1+\epsilon)k] \\  &= \mathrm{Pr}[k(1-\epsilon)\leq  \tilde{Z}  \leq (1+\epsilon)k] \end{array} \qquad (9)

Ở đây, \tilde{Z} = \sum_{i=1}^k Y^2_i phân bố chi-squared với k bậc tự do vì nó là tổng bình phương của k biến ngẫu nhiên độc lập có cùng phân bố \mathcal{N}(0,1).

Để chứng minh (4), ta chỉ cần chứng minh:

\mathrm{Pr}[k(1-\epsilon)\leq  \tilde{Z}  \leq (1+\epsilon)k] \geq 1 - 2e^{\frac{-(\epsilon^2 - \epsilon^3)k}{4}} \qquad (10)

Mình sẽ dừng chứng minh ở đây vì chứng minh (10) thực ra là tính tail-bound của phân bố chi-squared, một bài toán khá cổ điển trong xác suất thống kê. Bạn đọc có thể tiếp cận (10) bằng 2 cách: (a) sử dụng tích chất của phân phối chi-squared và (b) sử dụng Markov's inequality moment-generating function giống như trong chứng minh của Chernoff boundHoeffding bound. Cách (a) thì bạn chịu khó đọc trang wikipedia của chi-squared còn cách (b) đã được trình bày trong note [8].


Có hai cách khác để sinh ra hàm F(.) như trong Lemma 1.

  • Cách 1: Chọn ngẫu nhiên không gian con \mathbb{R}^k của \mathbb{R}^n và chiếu toàn bộ dữ liệu xuống không gian con đã chọn, scale dữ liệu với thừa số \sqrt{n/k}. Cách này là cách mà Johnson và Lindenstrauss [1] đề xuất.
  • Cách 2: Thay vì chọn các phần tử của ma trận A như trong Lemma 1 là theo \mathcal{N}(0,1), ta chọn các phần tử ngẫu nhiên là 1 hoặc -1. Cách này sẽ làm thực thi thuật toán đơn giản hơn.

Tuy nhiên, chứng minh bổ đề JLL với cả hai cách trọn trên đều không đơn giản. Các bạn có thể tham khảo note [2] của Jiri Matousek.

Tham khảo

[1] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz Mappings into a Hilbert Space . Conference in modern analysis and probability (New Haven, Conn., 1982), 189–206. Contemp. Math 26 (1984).
[2] J. Matousek. Lecture Notes on Metric Embeddings.
[3] J. Nelson. Lecture Notes on Dimensionality Reduction - Note 1. August, 2015.
[4] J. Nelson. Lecture Notes on Dimensionality Reduction - Note 2. August, 2015.
[5] K. G. Larsen and J. Nelson. Optimality of the Johnson-Lindenstrauss Lemma. arXiv preprint arXiv:1609.02094 (2016).
[6] N. Ailon and B. Chazelle. Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform. Proceedings of the 38th Annual ACM Symposium on Theory of Computing. pp. 557–563. 2006.
[7] D. M. Kane and J. Nelson. Sparser Johnson-Lindenstrauss Transforms. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1195–1203. 2012.
[8] S. Kakade and G. Shakhnarovich, Lecture Notes on Random Projection. 2009.

Tags: , , , ,

« Older entries § Newer entries »