Trong khoa học dữ liệu, học máy chủ động (Active Learning) và kỹ thuật thực nghiệm, việc thu thập dữ liệu thường tốn kém chi phí, thời gian hoặc năng lượng. Một câu hỏi cốt lõi đặt ra là: Nếu ta chỉ có ngân sách thực hiện $m$ phép đo từ một tập $p$ phép thử khả dĩ ($p\ge n$), ta nên phân bổ số lần đo cho từng phép thử như thế nào để vector chưa biết được ước lượng với độ chính xác cao nhất?

Bài toán thiết kế thí nghiệm tối ưu (Optimal Experiment Design) giải quyết trọn vẹn câu hỏi này. Bằng cách kết nối thông tin Fisher với ellipsoid sai số ước lượng, bài toán phân bổ nguyên được thành một bài toán tối ưu lồi quy mô lớn, mở đường cho các tiêu chuẩn tối ưu kinh điển như $D$-optimal, $A$-optimal và $E$-optimal.

1. Mô hình đo lường tuyến tính và Ma trận Fisher

Xét bài toán ước lượng vector ẩn $x\in {\mathbb{R}}^n$. Người làm thí nghiệm có thể lựa chọn từ $p$ phép đo thử nghiệm khả dĩ với các vector đặc trưng $v_1,v_2,\dots ,v_p\in {\mathbb{R}}^n$.

Mỗi khi chọn phép thử $i$, ta thu được một kết quả đo vô hướng $y$:

$$y=v_i^{T}x+w,$$

trong đó $w$ là nhiễu đo lường ngẫu nhiên độc lập có phân phối chuẩn $\mathcal{N}(0,{\sigma }^2)$ với ${\sigma }^2>0$.

Giả sử ta thực hiện phép thử thứ $i$ đúng $m_i$ lần ($m_i\in \{0,1,2,\dots \}$), với tổng ngân sách đo lường cố định là $m$:

$$\sum _{i=1}^p{m}_i=m_1+m_2+\cdots +m_p=m.$$

Sau khi hoàn tất toàn bộ $m$ phép đo, ước lượng bình phương tối thiểu (cũng là ước lượng hợp lý cực đại - MLE) của vector $x$ có hiệp phương sai sai số là:

$$\mathrm{Cov}(\hat{x})={\sigma }^2{\left(\sum _{i=1}^p{m}_i{v}_i{v}_i^T\right)}^{-1}.$$

Đại lượng trung tâm quyết định độ chuẩn xác của ước lượng chính là thông tin Fisher (Fisher Information Matrix):

$$M=\sum _{i=1}^p{m}_i{v}_i{v}_i^T=m_1{v}_1{v}_1^T+m_2{v}_2{v}_2^T+\cdots +m_p{v}_p{v}_p^T.$$

$M\in {\mathbb{S}}_{+}^n$ là một ma trận đối xứng . Để vector $x$ có thể ước lượng được (hệ xác định duy nhất), ma trận $M$ bắt buộc phải khả nghịch, tức là đối xứng xác định dương $M\succ 0$. Khi đó, ellipsoid tin cậy của sai số ước lượng $\hat{x}-x$ tại mức ý nghĩa thống kê tỷ lệ thuận với ma trận nghịch đảo:

$${\mathcal{E}}_{\text{error}}=\{e\in {\mathbb{R}}^n\mid e^{T}Me\le 1\}.$$

Mục tiêu của người thiết kế thí nghiệm là làm cho thông tin $M$ "càng lớn càng tốt" theo nghĩa , tương đương với việc thu nhỏ thể tích hoặc bán kính của ellipsoid sai số $M^{-1}$.

2. Nới lỏng liên tục (Relaxed Experiment Design)

Bài toán tìm các số nguyên $m_i\in \mathbb{N}$ thỏa mãn $\sum _{i=1}^p{m}_i=m$ là một bài toán tối ưu rời rạc (tổ hợp) rất khó giải khi $p$ và $m$ lớn.

Để giải quyết một cách hiệu quả, ta chia cả hai vế cho tổng số phép đo $m$ và đặt:

$${\lambda }_i=\frac{m_i}{m},\mathrm{\forall }i=1,\dots ,p.$$

Đại lượng ${\lambda }_i$ biểu diễn tỷ lệ phần trăm phân bổ ngân sách cho phép thử thứ $i$. Khi cho phép ${\lambda }_i$ nhận các giá trị thực liên tục trong đoạn $[0,1]$, ta thu được bài toán thiết kế thí (Relaxed Design):

$$\lambda \in \mathrm{\Delta }=\{\lambda \in {\mathbb{R}}^p|\sum _{i=1}^p{\lambda }_i={\lambda }_1+\cdots +{\lambda }_p=1,{\lambda }_i\ge 0,\mathrm{\forall }i=1,\dots ,p\}.$$

thông tin Fisher chuẩn hóa trở thành một hàm affine theo vector phân bổ $\lambda$:

$$M(\lambda )=\sum _{i=1}^p{\lambda }_i{v}_i{v}_i^T={\lambda }_1{v}_1{v}_1^T+{\lambda }_2{v}_2{v}_2^T+\cdots +{\lambda }_p{v}_p{v}_p^T.$$

Vì $M(\lambda )$ là tổ hợp lồi của các hạng một $v_i{v}_i^T⪰0$, ánh xạ $\lambda \mapsto M(\lambda )$ là ánh xạ affine, bảo toàn trọn vẹn tính lồi của các hàm tiêu chuẩn tiếp theo.

3. Các tiêu chuẩn tối ưu lồi kinh điển

Có nhiều cách khác nhau để định lượng độ "lớn" của thông tin $M(\lambda )$, tương ứng với các tiêu chuẩn thiết kế thực nghiệm cổ điển:

Tiêu chuẩn D-optimal (Determinant Criterion)

Tiêu chuẩn $D$-optimal hướng tới việc thu nhỏ thể tích của ellipsoid tin cậy sai số. Thể tích của ellipsoid ${\mathcal{E}}_{\text{error}}$ tỷ lệ nghịch với căn bậc hai định thức của $M(\lambda )$:

$$\mathrm{Vol}({\mathcal{E}}_{\text{error}})\propto \frac{1}{\sqrt{detM(\lambda )}}={(detM(\lambda {)}^{-1})}^{1/2}.$$

Thu nhỏ thể tích tương đương với cực đại hóa định thức $detM(\lambda )$, hay thuận tiện hơn là cực tiểu hóa hàm đối logarit định thức:

$$\begin{array}{rl}& \underset{\lambda }{min}-\log detM(\lambda )\\ & \text{s.t.}\sum _{i=1}^p{\lambda }_i=1,\\ & \phantom{\text{subject to}}{\lambda }_i\ge 0,\mathrm{\forall }i=1,\dots ,p.\end{array}$$

Vì hàm số $f(X)=-\log detX$ là ngặt trên nón đối xứng xác định dương ${\mathbb{S}}_{++}^n$, và $M(\lambda )$ phụ thuộc affine vào $\lambda$, bài toán $D$-optimal là một bài toán tối ưu lồi ngặt. Nghiệm tối ưu ${\lambda }^{\ast }$ là duy nhất và có thể giải quyết nhanh chóng bằng thuật toán Newton hoặc phương pháp điểm trong.

Tiêu chuẩn A-optimal (Average Variance Criterion)

Tiêu chuẩn $A$-optimal hướng tới việc cực tiểu hóa tổng phương sai (hoặc phương sai trung bình) của các thành phần ước lượng:

$$\sum _{j=1}^n\mathrm{Var}({\hat{x}}_j)={\sigma }^2\mathrm{tr}(M(\lambda {)}^{-1}).$$

Bỏ qua hằng số ${\sigma }^2$, bài toán được phát biểu thành:

$$\begin{array}{rl}& \underset{\lambda }{min}\mathrm{tr}(M(\lambda {)}^{-1})\\ & \text{s.t.}\sum _{i=1}^p{\lambda }_i=1,\\ & \phantom{\text{subject to}}{\lambda }_i\ge 0,\mathrm{\forall }i=1,\dots ,p.\end{array}$$

Hàm số $f(X)=\mathrm{tr}(X^{-1})$ là trên ${\mathbb{S}}_{++}^n$. Dùng bổ đề phần bù Schur, ta chuyển đổi bài toán $A$-optimal sang dạng Quy hoạch nửa xác định (SDP) chuẩn mực bằng cách đưa vào các biến phụ $u\in {\mathbb{R}}^n$:

$$\begin{array}{rl}& \underset{\lambda ,u}{min}\sum _{j=1}^n{u}_j\\ & \text{s.t.}\left[\begin{array}{cc}M(\lambda )& e_j\\ & e_j^T{u}_j\end{array}\right]⪰0,\mathrm{\forall }j=1,\dots ,n,\\ & \phantom{\text{subject to}}\sum _{i=1}^p{\lambda }_i=1,{\lambda }_i\ge 0,\mathrm{\forall }i=1,\dots ,p,\end{array}$$

trong đó $e_j$ là vector đơn vị thứ $j$ trong ${\mathbb{R}}^n$.

Tiêu chuẩn E-optimal (Eigenvalue Criterion)

Tiêu chuẩn $E$-optimal hướng tới việc bảo vệ ước lượng trong trường hợp xấu nhất. Chiều dài trục bán kính dài nhất của ellipsoid sai số bằng căn bậc hai của trị riêng lớn nhất của nghịch đảo ${\lambda }_{max}(M(\lambda {)}^{-1})$, tức là $1/{\lambda }_{min}(M(\lambda ))$.

Do đó, tiêu chuẩn $E$-optimal cực đại hóa trị riêng nhỏ nhất của $M(\lambda )$:

$$\begin{array}{rl}& \underset{\lambda ,t}{max}t\\ & \text{s.t.}M(\lambda )⪰t{I}_n,\\ & \phantom{\text{subject to}}\sum _{i=1}^p{\lambda }_i=1,{\lambda }_i\ge 0,\mathrm{\forall }i=1,\dots ,p.\end{array}$$

Đây là một bài toán Quy hoạch nửa xác định (SDP) trực tiếp với một bất đẳng thức tuyến tính (LMI).

4. Làm tròn số nguyên (Rounding) và Tính thưa

Sau khi tìm được nghiệm liên tục tối ưu ${\lambda }^{\ast }$, ta cần khôi phục lại các số nguyên $m_i$:

1. Nếu tổng số phép đo $m$ rất lớn ($m\gg n$), ta chỉ cần làm tròn đơn giản:
   $$m_i\approx \mathrm{round}(m{\lambda }_i^{\ast }),$$
   sau đó điều chỉnh nhỏ để tổng bằng $m$. Tổn thất độ chính xác do làm tròn khi đó là không đáng kể (cỡ $\mathcal{O}(1/m)$).
2. Tính thưa của nghiệm (Sparsity): Một định lý sâu sắc của lý thuyết thiết kế thực nghiệm chỉ ra rằng luôn tồn tại một nghiệm tối ưu ${\lambda }^{\ast }$ có nhiều nhất $n(n+1)/2$ thành phần khác 0. Điều này có nghĩa là ta không cần thực hiện toàn bộ $p$ phép thử, mà chỉ cần chọn lọc một tập hợp con rất nhỏ các phép đo quan trọng nhất.

5. Ví dụ tính toán minh họa

Xét bài toán ước lượng vector hai chiều $x\in {\mathbb{R}}^2$ ($n=2$) với ngân sách đo lường $m=100$. Ta có $p=3$ phép thử ứng viên:

$$v_1=\left[\begin{array}{c}1\\ 0\end{array}\right],v_2=\left[\begin{array}{c}0\\ 1\end{array}\right],v_3=\left[\begin{array}{c}1\\ 1\end{array}\right].$$

Ta phân bổ tỷ lệ đo $\lambda =({\lambda }_1,{\lambda }_2,{\lambda }_3)$ với ${\lambda }_1+{\lambda }_2+{\lambda }_3=1$ và ${\lambda }_i\ge 0$.

Các hạng một tương ứng:

$$v_1{v}_1^T=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right],v_2{v}_2^T=\left[\begin{array}{cc}0& 0\\ 0& 1\end{array}\right],v_3{v}_3^T=\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right].$$

thông tin Fisher:

$$M(\lambda )=\left[\begin{array}{cc}{\lambda }_1+{\lambda }_3& {\lambda }_3\\ {\lambda }_3& {\lambda }_2+{\lambda }_3\end{array}\right].$$

Định thức của :

$$detM(\lambda )=({\lambda }_1+{\lambda }_3)({\lambda }_2+{\lambda }_3)-{\lambda }_3^2={\lambda }_1{\lambda }_2+{\lambda }_1{\lambda }_3+{\lambda }_2{\lambda }_3.$$

Để áp dụng tiêu chuẩn $D$-optimal, ta cực đại hóa định thức này với điều kiện ${\lambda }_1+{\lambda }_2+{\lambda }_3=1$:

Theo bất đẳng thức đại số quen thuộc:

$${\lambda }_1{\lambda }_2+{\lambda }_1{\lambda }_3+{\lambda }_2{\lambda }_3\le \frac{1}{3}({\lambda }_1+{\lambda }_2+{\lambda }_3{)}^2=\frac{1}{3}.$$

Dấu bằng đạt được khi và chỉ khi:

$${\lambda }_1^{\ast }={\lambda }_2^{\ast }={\lambda }_3^{\ast }=\frac{1}{3}.$$

Nghiệm $D$-optimal khuyến nghị phân bổ đồng đều ngân sách cho cả ba hướng thử nghiệm: Mỗi hướng đo xấp xỉ $33$ đến $34$ lần. Khi đó định thức đạt giá trị cực đại là $1/3$, cho thể tích ellipsoid sai số nhỏ nhất có thể.

Bài tập tự luyện

Bài tập: Bài toán phân bổ cảm biến định vị

Một trạm quan trắc cần ước lượng vị trí nguồn phát tín hiệu $x\in {\mathbb{R}}^2$. Trạm có thể kích hoạt 4 cảm biến đặt tại các góc đo:

$$v_1=\left[\begin{array}{c}1\\ 0\end{array}\right],v_2=\left[\begin{array}{c}-1\\ 0\end{array}\right],v_3=\left[\begin{array}{c}0\\ 1\end{array}\right],v_4=\left[\begin{array}{c}0\\ -1\end{array}\right].$$

1. Chứng minh rằng $v_1{v}_1^T=v_2{v}_2^T$ và $v_3{v}_3^T=v_4{v}_4^T$.
2. Hãy rút gọn thông tin $M(\lambda )$ theo hai biến gộp $w_1={\lambda }_1+{\lambda }_2$ và $w_2={\lambda }_3+{\lambda }_4$.
3. Tìm phân bổ tối ưu theo tiêu chuẩn $D$-optimal và $A$-optimal.

Lời giải

1. Tính các hạng một:

   $$v_1{v}_1^T=\left[\begin{array}{c}1\\ 0\end{array}\right]\left[\begin{array}{cc}1& 0\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right],v_2{v}_2^T=\left[\begin{array}{c}-1\\ 0\end{array}\right]\left[\begin{array}{cc}-1& 0\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right].$$

   Tương tự:

   $$v_3{v}_3^T=v_4{v}_4^T=\left[\begin{array}{cc}0& 0\\ 0& 1\end{array}\right].$$

   Hai cảm biến đối xứng nhau qua gốc tọa độ mang lại thông tin giống hệt nhau.

2. Rút gọn Fisher: Đặt $w_1={\lambda }_1+{\lambda }_2$ và $w_2={\lambda }_3+{\lambda }_4$. Ta có $w_1+w_2=1$ với $w_1,w_2\ge 0$. Ma trận Fisher có dạng đường chéo:

   $$M(w)=\left[\begin{array}{cc}{w}_1& 0\\ 0& w_2\end{array}\right].$$

3. Tìm phân bổ tối ưu:

   • Tiêu chuẩn $D$-optimal: Cực đại $detM(w)=w_1{w}_2$. Tích này đạt cực đại trên đoạn $[0,1]$ khi $w_1^{\ast }=w_2^{\ast }=1/2$.
   • Tiêu chuẩn $A$-optimal: Cực tiểu $\mathrm{tr}(M(w{)}^{-1})=\frac{1}{w_1}+\frac{1}{w_2}$. Theo bất đẳng thức Cauchy-Schwarz, tổng này đạt cực tiểu khi $w_1^{\ast }=w_2^{\ast }=1/2$. Như vậy, cả hai tiêu chuẩn đều dẫn tới kết luận: Dành $50\mathrm{\%}$ thời gian đo theo phương ngang (chia tùy ý giữa cảm biến 1 và 2) và $50\mathrm{\%}$ thời gian đo theo phương dọc (chia tùy ý giữa cảm biến 3 và 4).

Tóm tắt

Thiết kế thí nghiệm tối ưu (Optimal Experiment Design) biến bài toán chọn mẫu dữ liệu thực nghiệm thành một bài toán tối ưu lồi quy mô lớn thông qua việc liên tục phân bổ ngân sách. Việc cực đại hóa thông tin Fisher hoặc cực tiểu hóa ellipsoid sai số qua các tiêu chuẩn $D$-optimal (log-det), $A$-optimal (trace inverse) và $E$-optimal (SDP) là nền móng toán học vững chắc cho các kỹ thuật Active Learning, A/B Testing và giảm thiểu chi phí gắn nhãn dữ liệu trong Trí tuệ Nhân tạo hiện đại.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, Chapter 7: Statistical Estimation (§7.5).