# TOWARD UNSUPERVISED OUTLIER MODEL SELECTION

## I. ABSTRACT


Trong lĩnh vực phát hiện điểm bất thường (anomaly detection, outlier detection), ngày càng có nhiều thuật toán với vô số siêu tham số, nhưng lại thiếu đi việc hướng dẫn cụ thể để chọn mô hình phù hợp khi không có nhãn. Việc “lựa chọn thuật toán nào và giá trị siêu tham số nào để sử dụng trên một bộ dữ liệu mới” vẫn là một vấn đề mở.

Trong bài báo này, các tác giả đề xuất ELECT, một hướng tiếp cận mới để chọn một mô hình ứng viên hiệu quả, tức là một thuật toán phát hiện mô hình ngoại lai và bộ siêu tham số của nó, để sử dụng trên một tập dữ liệu không có bất kỳ nhãn nào.

Về bản chất, ELECT dựa trên meta-learning, chuyển giao tri thức trước đó (ví dụ như hiệu suất mô hình) trên các tập dữ liệu lịch sử tương tự như một tập dữ liệu mới để tạo điều kiện thuận lợi giải quyết bài toán lựa chọn mô hình ngoại lai không giám sát (UOMS). Đặc biệt, nó sử dụng biện pháp đo độ tương đồng của tập dữ liệu dựa trên hiệu suất, tức là việc dựa trên hiệu suất như này sẽ mang tính trực tiếp và hướng đến mục tiêu hơn so với các độ đo khác sử dụng trước đây. Các tác giả nhận định ELECT có khả năng tìm kiếm thích ứng các tập dữ liệu lịch sử tương tự, do đó, nó có thể cung cấp đầu ra theo yêu cầu, có thể phù hợp với nhiều chi phí thời gian khác nhau.

Kết luận: ELECT vượt trội hơn nhiều so với nhiều baselines đơn giản UOMS. Các baselines này bao gồm là các phương pháp không lựa chọn model (như việc luôn sử dụng cùng một mô hình phổ biến như iForest) cũng như các chiến lược lựa chọn gần đây hơn dựa trên các meta-features.

## II. METHOD


Cho một tập dữ liệu mới không có nhãn, nhiệm vụ là chọn một mô hình – được xác định bởi cả (i) một thuật toán phát hiện ngoại lệ và (ii) các giá trị của các siêu tham số (HP) của nó. Phần đầu (thuật toán) là lựa chọn rời rạc, vì số lượng thuật toán phát hiện hiện có là hữu hạn. Phần sau (tham số) là liên tục, và do đó tạo ra vô hạn mô hình ứng cử.

Việc tối ưu tham số liên tục thường được giải quyết bằng các chiến lược tìm kiếm lặp (ví dụ tối ưu đàn bầy – particle swarm optimization, hay tối ưu Bayes – BO). Những phương pháp này gặp khó khăn lớn cho bài toán UOMS, bởi trong trường hợp thiếu nhãn, việc đánh giá mô hình không thể thực hiện đáng tin cậy.

Do đó, trong bài báo này các tác giả đơn giản hóa và thu hẹp không gian tìm kiếm bằng cách xác định trước một tập các mô hình OD ứng cử.

Cụ thể, các tác giả định nghĩa một tập hữu hạn các mô hình, kí hiệu M = {M₁, …, M_m}, bằng cách rời rạc hóa không gian HP của mỗi bộ phát hiện ứng cử. Mỗi mô hình M ∈ M ở đây là một cặp {detector, configuration}, trong đó configuration mô tả một thiết lập cụ thể của các giá trị siêu tham số cho mỗi detector.

* Cho: nhiệm vụ OD mới không giám sát, tức tập dữ liệu đầu vào D_test = (X_test, ∅) không có nhãn, và tập các mô hình ứng cử viên hữu hạn M.

* Nhiệm vụ: Chọn một mô hình M ∈ M hiệu quả để áp dụng cho D_test.


Trọng tâm của phương pháp là meta-học (meta-learning), nguyên lý cơ bản là chuyển giao thông tin hữu ích từ các nhiệm vụ lịch sử sang nhiệm vụ mới. Để thực hiện điều này, ELECT nhận đầu vào là tập các dữ liệu OD lịch sử D_train = {D₁, …, Dₙ}, tức cơ sở dữ liệu huấn luyện meta có nhãn, với D_i = (X_i, y_i). Từ đó, ELECT tính toán:
* Điểm ngoại lệ đầu ra lịch sử: O_i,j := M_j(D_i), tức điểm ngoại lệ đầu ra của mô hình thứ j trên tập dữ liệu D_i, cho mỗi mô hình ứng cử M_j ∈ M và mỗi tập D_i ∈ D_train.
* Ma trận hiệu suất lịch sử: P ∈ ℝ^n×m, trong đó P_i,j cho biết hiệu suất (ví dụ AP – diện tích dưới đồ thị PR) của mô hình M_j trên tập D_i.

ELECT bao gồm hai pha chính.
* Trong pha huấn luyện meta (ngoại tuyến), hệ thống học các thông tin cần thiết để định lượng độ tương tự giữa hai nhiệm vụ dựa trên D_train.
* Trong pha lựa chọn mô hình (trực tuyến), ELECT dùng thông tin này để xác định các nhiệm vụ lịch sử trong D_train tương tự với nhiệm vụ đầu vào D_test và chọn một mô hình mà không sử dụng nhãn.

### 1. META-TRAINING (OFFLINE)


Cho tập nhiệm vụ lịch sử D_train và nhiệm vụ mới D_test, ý tưởng chính là trước tiên tìm một tập con N ⊂ D_train gồm những nhiệm vụ tương tự với D_test, sau đó chọn mô hình có hiệu suất trung bình tốt nhất trên các nhiệm vụ “hàng xóm” này. Do đó, một thành phần chủ chốt của ELECT là biện pháp đo độ tương đồng giữa các nhiệm vụ. Khác biệt của ELECT là sử dụng độ tương đồng dựa trên hiệu suất: hai nhiệm vụ được cho là tương tự nếu thứ tự xếp hạng hiệu suất của tất cả các mô hình trên mỗi nhiệm vụ giống nhau.

#### Performance-driven Task Similarity

Phương pháp MetaOD mà họ đề xuất lượng hóa độ tương đồng giữa các tác vụ dựa trên siêu-đặc trưng (meta-features), vốn phản ánh các tính chất thống kê tổng quát của một bộ dữ liệu mà phần lớn điểm dữ liệu trong đó là điểm bình thường (inliers). Do đó, hai bộ dữ liệu có phân bố inlier tương tự nhau nhưng có các loại điểm ngoại lai khác nhau có thể trông giống nhau về mặt siêu-đặc trưng, trong khi những mô hình phát hiện ngoại lai khác nhau lại có thể hiệu quả hơn trong việc phát hiện những loại ngoại lai khác nhau mà chúng thể hiện. Trong các trường hợp như vậy, sự tương đồng về siêu-đặc trưng sẽ là một chỉ báo kém về sự tương đồng về hiệu suất của mô hình.

Độ đo này là độ đo rank-based, hệ số tương quan thứ tự Kendall có trọng số τ, ượng hóa mức độ tương đồng giữa sự sắp xếp của các mô hình ứng viên theo hiệu suất.


#### Internal Performance Measures (IPMs)


IPMs là các đặc trưng chỉ dựa trên dữ liệu đầu vào và thứ tự/chỉ số điểm ngoại lệ (chẳng hạn độ đồng thuận giữa các mô hình, cấu trúc đồ thị, độ trung tâm của điểm ngoại lệ trong không gian điểm, v.v.) giúp so sánh các mô hình mà không cần nhãn. ELECT sử dụng nhiều IPMs khác nhau (ví dụ ModelCentrality, HITS, SELECT) làm đầu vào.

Ở cốt lõi của quá trình huấn luyện meta của ELECT là việc học một hàm ánh xạ từ IPM sang hiệu suất thật thông qua sự giám sát từ cơ sở dữ liệu meta-train. Cụ thể, ELECT học một bộ hồi quy để ánh xạ IPM của hai mô hình vào sự khác biệt hiệu suất của chúng. Nói cách khác, ELECT thực hiện hồi quy cặp (pairwise) để dự đoán chênh lệch hiệu suất giữa hai mô hình dựa trên IPM của chúng.

### 2. MODEL SELECTION(ONLINE)

Sau giai đoạn huấn luyện meta (meta-training), ELECT đã sẵn sàng nhận một tác vụ mới để lựa chọn mô hình.

Về cơ bản, ELECT chọn mô hình có hiệu suất trung bình cao nhất trong các tác vụ meta-training tương tự nhất với tác vụ mới. Các tác vụ meta tương tự này được xác định một cách lặp lại thông qua việc cải thiện ước lượng độ tương đồng một cách thích nghi.

#### Model Selection via Similar Meta-tasks


Cho một tác vụ mới $D_\text{test}$, mục tiêu là xác định các tác vụ meta-train tương tự (gọi là tập lân cận $N \subset D_\text{train}$). Theo nguyên tắc của meta-learning, mô hình (hoặc các mô hình) có hiệu năng cao hơn trên tập lân cận này cũng có khả năng cao sẽ cho hiệu năng cao trên tác vụ mới tương ứng. Do đó, chúng ta có thể chọn mô hình có hiệu năng trung bình lớn nhất trên tập lân cận làm mô hình được chọn cho tác vụ mới, tức:


Nếu các hiệu suất $P_\text{test}$ của các mô hình trên $D_\text{test}$ có sẵn, ta có thể duyệt toàn bộ cơ sở dữ liệu meta-train để đo độ tương đồng giữa các tác vụ thông qua hệ số tương quan Kendall τ, và chọn $N$ gồm $t$ tác vụ meta-train tương đồng nhất, như mô tả trong công thức (3). Ở đây $t$ là kích thước của tập lân cận (tức $|N|=t$), có thể được xác định thông qua cross-validation trên cơ sở dữ liệu meta-train.

Tuy nhiên, trong thực tế chúng ta không thể trực tiếp xác định $N$ vì thiếu nhãn thật và do đó không có $P_\text{test}$ cho tác vụ mới. Bằng cách thay các giá trị sai khác hiệu năng dự đoán ($\hat{\Delta}$) của tác vụ mới vào Công thức (1), chúng ta có thể ước tính tập lân cận $N$ ngay cả khi $P_\text{test}$ không thể đo lường được.

Cụ thể, đối với tác vụ mới $D_\text{test}$, chúng ta đầu tiên tính điểm ngoại lệ $O_\text{test} = M(D_\text{test})$ và xây dựng các IPMs $m_\text{test} = \phi(O_\text{test})$ trên các mô hình ứng viên.

Sau đó, chúng ta có thể dự đoán sai khác hiệu năng $\Delta$ của bất kỳ cặp mô hình $(M_j, M_{j'})$ cho $D_\text{test}$ bằng bộ hồi quy $f(\cdot)$ theo công thức: $\displaystyle \hat{\Delta}{j,j'}^{(\text{test})} := f(m{\text{test},j}, m_{\text{test},j'}) \approx \Delta_{j,j'}^{(\text{test})},$

Các giá trị sai khác hiệu năng dự đoán này được dùng để tính toán hệ số tương đồng Kendall-τ ước tính ($\hat{\tau}$) giữa tác vụ mới và các tác vụ meta-train.

Cuối cùng, đưa các giá trị độ tương đồng ước tính vào Công thức (3), ta thu được tập lân cận $N$ của tác vụ mới gồm $t$ tác vụ meta-train có độ tương đồng Kendall-τ ước tính lớn nhất, tức:

$N := \text{top-}t_{i=1,\dots,n}\ \hat{\tau}(\text{test},i) \approx \text{top-}t_{i=1,\dots,n}\ \tau(\text{test},i).$

#### Unsupervised Adaptive Search


Việc lượng hóa độ tương đồng giữa các tác vụ bằng hệ số tương quan Kendall-tau sử dụng toàn bộ tập hợp mô hình $M$. tạo ra chi phí tính toán rất lớn, vì phải huấn luyện tất cả mô hình để lấy điểm ngoại lệ và trích xuất IPMs. Do đó, các tác giả chỉ xét một tập con mô hình, gọi là $M_s \subset M$, để ước tính độ tương đồng tác vụ.

Sau đó ta sẽ mở rộng tập con mô hình để liên tục cải thiện ước lượng độ tương đồng tác vụ, từ đó thu được các ước lượng ngày càng chính xác hơn về những bộ dữ liệu tương tự nhất với $D_\text{test}$

Mục tiêu của quá trình tìm kiếm thích ứng là xác định chính xác tập lân cận $N$ chỉ với một số nhỏ các mô hình được huấn luyện trên $D_\text{test}$, qua đó giảm tổng chi phí tính toán.

Trong quá trình lặp, các tác giả đề xuất hai tiêu chí cho việc chọn mô hình tiếp theo:
(1) Độ không chắc chắn (Uncertainty): thứ hạng hiệu năng của mô hình thêm vào phải biến thiên trên tập lân cận hiện tại (tức các tác vụ trong $N$ có sự khác biệt ý kiến về mô hình đó);
(2) Chất lượng (Quality): mô hình thêm vào phải có hiệu năng tốt trên tập $N$ hiện tại.

Việc cân nhắc hai tiêu chí này giúp đảm bảo rằng tập $M_s$ sau mỗi vòng vẫn đa dạng (không chỉ gồm các mô hình tương tự nhau) và tập trung vào các mô hình chất lượng cao, qua đó tìm ra các tác vụ thực sự tương tự và từ đó chọn ra mô hình tốt nhất cho tác vụ mới.

## III. EXPERIMENTS








Kết quả trên Wild Testbed: Như minh họa ở Hình 3, ELECT có hiệu năng vượt trội so với tất cả các phương pháp baseline với thứ hạng trung bình thấp nhất trong môi trường “hoang dã”. ELECT cũng tốt hơn rõ rệt so với các baseline không chọn mô hình (LOF, iForest, ME) và các baseline meta-learning khác (GB, ISAC, ALORS, SS, IPM SS). Với các baseline còn lại, giá trị $p$ vẫn thấp dù chưa đạt ngưỡng 0.05.


Kết quả: Như thể hiện ở Hình 5, ELECT vượt trội so với tất cả các phương pháp dựa trên meta-feature, với xếp hạng AP trung bình của nó là 55, trong khi các phương pháp meta-feature đều trên 130. Điều này cho thấy hiệu suất của các phương pháp meta-feature bị suy giảm khi độ tương đồng dựa trên hiệu năng và độ tương đồng dựa trên meta-feature không tương ứng. Ngược lại, ELECT không phụ thuộc vào meta-feature mà tập trung trực tiếp vào độ tương đồng dựa trên hiệu năng, dẫn đến kết quả chọn mô hình tốt hơn rõ rệt.

## Hạn chế


* Cần kho bài toán lịch sử có nhãn đủ lớn và đa dạng; nếu thiếu hoặc không đại diện, hiệu quả giảm.
* ELECT cần một cơ sở dữ liệu các nhiệm vụ OD lịch sử với nhãn đầy đủ để học meta‑regressor và xác định các nhiệm vụ “hàng xóm” tương tự. Nếu trong meta‑train không có các tập dữ liệu đủ giống với nhiệm vụ mới, việc chọn mô hình có thể kém chính xác do thông tin chuyển giao không phù hợp

* Không khám phá thuật toán mới ngoài kho mô hình định trước.
* ELECT chỉ lựa chọn trong một tập hữu hạn các mô hình đã được rời rạc hóa (discretized) từ trước (M = {M₁,…,Mₘ}). Do đó, nếu trong tương lai xuất hiện thuật toán OD mới hoặc cài đặt siêu tham số ngoài lưới rời rạc hóa, ELECT sẽ không thể cân nhắc đến chúng

* Chi phí huấn luyện ngoại tuyến (offline) cao
* Giai đoạn meta‑training của ELECT có độ phức tạp rất cao. Điều này đòi hỏi tài nguyên tính toán và thời gian đáng kể khi số lượng nhiệm vụ hoặc mô hình tăng lên.