Tóm tắt Luận án Tiến sĩ Toán học: Áp dụng các phương pháp giải tích và tối ưu toán học vào phân lớp nhị phân và phân đoạn hình ảnh trong học máy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

8
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của luận án "Áp dụng các phương pháp giải tích và tối ưu toán học vào phân lớp nhị phân và phân đoạn hình ảnh trong học máy" là ứng dụng các phương pháp giải tích như cực tiểu hóa và tối ưu toán học như tối ưu dựa trên gradient vào bài toán phân lớp nhị phân và phân đoạn hình ảnh, nhằm hiểu hơn các tính chất toán học của các máy AI và tăng cường hiệu quả của việc học máy, tối ưu hóa các máy.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Toán học: Áp dụng các phương pháp giải tích và tối ưu toán học vào phân lớp nhị phân và phân đoạn hình ảnh trong học máy

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC BÁCH KHOA HÀ NỘI Lê Bích Phượng ÁP DỤNG CÁC PHƯƠNG PHÁP GIẢI TÍCH VÀ TỐI ƯU TOÁN HỌC VÀO PHÂN LỚP NHỊ PHÂN VÀ PHÂN ĐOẠN HÌNH ẢNH TRONG HỌC MÁY Ngành: Toán học Mã số: 9460101 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2023
Công trình được hoàn thành tại: ĐẠI HỌC BÁCH KHOA HÀ NỘI Người hướng dẫn khoa học: 1. PGS.TS. NGUYỄN XUÂN THẢO 2. GS. TSKH. NGUYỄN TIẾN DŨNG Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Đại học Bách khoa Hà Nội, họp tại Đại học Bách khoa Hà Nội Vào hồi...............giờ..........., ngày.............tháng..............năm 2023 Có thể tìm hiểu luận án tại: 1. Thư viện Tạ Quang Bửu-ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam
MỞ ĐẦU 1. Lịch sử vấn đề và lí do lựa chọn đề tài Vấn đề phân lớp (phân loại) trong học máy là quá trình phân lớp một đối tượng dữ liệu vào một hay nhiều lớp đã cho trước nhờ mô hình phân lớp. Quá trình phân lớp là quá trình gán nhãn cho đối tượng dữ liệu. Phân loại đối tượng vào n-lớp khác nhau được gọi là quá trình phân lớp n-phân. Mọi vấn đề phân lớp n-phân (n > 2) đều có thể đưa về vấn đề phân lớp nhị phân (binary classsification). Nghiên cứu các thước đo độ chính xác nói chung và các thước đo độ chính xác trong phân lớp nhị phân nói riêng là vấn đề quan trọng. Chính vì thế mà các thước đo độ chính xác trong bài toán phân lớp nhị phân đã được nghiên cứu nhiều, nhưng chỉ nghiên cứu từng thước đo một cách riêng biệt. Trong đề tài này, tác giả muốn nghiên cứu về mối quan hệ giữa một số thước đo độ chính xác phổ biến, liệu chúng có thể thay thế được cho nhau trong quá trình học máy hay không? Ngoài ra, luận án cũng nghiên cứu đến vấn đề thế nào là máy tối ưu trong phân lớp nhị phân. Hơn nữa, đường cong đặc trưng hoạt động của máy thu (ROC-Receiver Operating Curve) từ quan điểm thực nghiệm được cho là lồi (hoặc tương đối lồi) khi mô hình học máy hiệu quả. Trong luận án này, tác giả muốn nghiên cứu về mặt lí thuyết tính lồi của đường cong ROC của máy tối ưu trong phân lớp nhị phân. Trong học máy, hàm mất mát (loss function) là hàm 1
dùng để đo xem một máy cho ra kết quả khác với “sự thật cơ bản” hay khác với “máy lí tưởng” chừng nào, để rồi phản hồi (feedback) lại thông tin đó cho máy, tìm cách thay đổi các tham số của máy nhằm giảm mất mát đi, khiến cho máy trở nên chính xác hay hiệu quả hơn. Trong phân lớp nhị phân, các hàm mất mát hay được dùng là hàm mất mát bình phương và hàm mất mát cross-entropy, các hàm mất mát này có tính chất gì đặc biệt mà khi sử dụng nó, chúng ta thường thu được mô hình học máy như mong muốn? Dựa vào tính chất đó, liệu có nguyên tắc chung nào cho việc xây dựng các hàm mất mát mới hay không? Với những lí do trên đây, tác giả muốn nghiên cứu ứng dụng các phương pháp của giải tích và tối ưu vào vấn đề phân lớp nhị phân, cụ thể là về: Các thước đo độ chính xác và các hàm mất mát trong phân lớp nhị phân. Phân đoạn hình ảnh (Image Segmentation) trong thị giác máy tính là một kĩ thuật quan trọng, giúp giải nhiều bài toán thuộc các lĩnh vực khác nhau như: phát hiện và nhận dạng đối tượng, hệ thống camera thông minh, xe tự lái, xử lí ảnh y tế, xử lí ảnh vệ tinh v.v.. Trong phân đoạn tự động cũng như phân đoạn thủ công, người ta thường tạo ra nhiều bộ phân đoạn (segmentor) cho cùng một bài toán. Sau đó người ta hợp các bộ phân đoạn bằng một phương pháp biểu quyết (voting method) với mong muốn tạo ra được một bộ phân đoạn chính xác hơn so với từng bộ phân đoạn riêng lẻ trong chúng. Phương pháp biểu quyết hiển nhiên nhất là biểu quyết số học.Tác giả cho rằng các phương pháp biểu quyết số học chưa tính đến cấu trúc của hình ảnh nên muốn đề xuất 2
một phương pháp biểu quyết mới, gọi là phương pháp biểu quyết tô-pô. Cùng với các kết quả thực nghiệm tác giả muốn sử dụng các kiến thức giải tích, xác suất và tối ưu toán học để chứng minh phương pháp biểu quyết này là hợp lý và cho kết quả tốt hơn phương pháp biểu quyết số học thông thường. Chính vì lí do đó, tác giả chọn nghiên cứu áp dụng các phương pháp giải tích và tối ưu vào vấn đề biểu quyết trong phân đoạn hình ảnh. 2. Mục đích, đối tượng và phạm vi nghiên cứu Mục đích nghiên cứu là ứng dụng các phương pháp giải tích như cực tiểu hóa và tối ưu toán học như tối ưu dựa trên gradient vào bài toán phân lớp nhị phân và phân đoạn hình ảnh, nhằm hiểu hơn các tính chất toán học của các máy AI và tăng cường hiệu quả của việc học máy, tối ưu hóa các máy. Đối tượng nghiên cứu là - Vấn đề phân lớp nhị phân, - Vấn đề phân đoạn hình ảnh. Phạm vi nghiên cứu là - Độ chính xác trong phân lớp nhị phân, - Hàm mất mát trong phân lớp nhị phân, - Biểu quyết tăng độ chính xác trong phân đoạn hình ảnh. 3. Phương pháp và công cụ nghiên cứu Phương pháp nghiên cứu bao gồm cả lý thuyết (các công cụ toán học, mệnh đề và định lý được chứng minh chặt chẽ) và thực nghiệm (sử dụng nền tảng Tensorflow 3
và các mạng thần kinh tích chập để tạo ra các chương trình học máy và các phép biểu quyết, đo đạc và so sánh hiệu quả của chúng). Về mặt toán học, công cụ mà tác giả dùng bao gồm giải tích hàm, lý thuyết xác suất, tối ưu toán học, cụ thể là: phương pháp biến phân, quá trình ngẫu nhiên, biến đổi tích phân trên không gian xác suất, định lý giới hạn trung tâm, phương pháp giảm theo dòng gradient, v.v.. 4. Cấu trúc, các kết quả của luận án và ý nghĩa của chúng Chương 1: Kiến thức chuẩn bị. Chương 2: Độ chính xác của máy phân loại nhị phân. - Các bất đẳng thức liên hệ các thước đo độ chính xác: diện tích của miền nằm dưới đường ROC (AUC ROC- Area Under the Curve ROC), độ chính xác cân bằng cao nhất (MBA-Maximal Balanced Accuracy ) và độ chính xác có trọng cao nhất (MWA-Maximal Weighted Accu- racy). Các bất đẳng thức này cho thấy ba thước đo đó có thể dùng thay thế cho nhau để đánh giá độ chính xác của một máy phân loại nhị phân. - Tính tối ưu của máy xác suất thực, tính lồi của đường ROC của máy xác suất thực. Kết quả này giúp chúng ta hiểu vì sao các đường ROC của các máy phân loại nhị phân mà chúng ta gặp trong các công bố trên thế giới nói chung có dáng điệu gần lồi: vì các máy tối ưu có đường ROC lồi, nên các máy được tạo bởi các quá trình học máy khá tốt, đạt gần tới tối ưu cũng có đường ROC gần lồi. 4
- Công thức về giới hạn tác dụng của phương pháp biểu quyết trong việc tăng cường độ chính xác của máy phân loại nhị phân. Ý nghĩa của kết quả này là bằng phương pháp biểu quyết (đã biết hoặc sẽ có), nói chung ta tăng được độ chính xác của máy, nhưng dù số máy tham dự bỏ phiếu có tiến tới vô cùng thì độ chính xác qua việc bỏ phiếu cũng không kỳ vọng tăng đến 100%. Chương 3: Ảnh hưởng của hàm mất mát đến các bài toán phân loại nhị phân. - Trong phân lớp nhị phân, hàm mất mát bình phương và hàm cross-entropy là hai hàm mất mát mà các máy làm tối thiểu hóa mất mát theo các hàm đó chính là các máy xác suất thực. - Các hàm mất mát siêu-lồi cũng dẫn đến các nghiệm cực tiểu là các máy tối ưu về độ chính xác. Các máy đó chính là các biến đổi tham số của các máy xác suất thực. - Tính chất lồi của hàm mất mát là tính chất quan trọng, nếu thiếu nó thì quá trình học máy có thể bị rơi vào các bẫy, tức là rơi vào những nơi mà máy tương ứng không phải là máy có độ chính xác mong muốn. Chương 4: Tối ưu hóa phân đoạn hình ảnh bằng biểu quyết tô-pô. Đưa ra một phương pháp biểu quyết mới, gọi là biểu quyết tô-pô. Phương pháp này bao gồm các dạng: - Biểu quyết tô-pô ở dạng đơn giản nhất, - Biểu quyết tô-pô địa phương, - Biểu quyết kết hợp cả tô-pô và số học. Chứng minh tại sao phương pháp biểu quyết tô-pô lại hợp lý và cho kết quả tốt hơn phương pháp biểu quyết số học cổ điển trong nhiều trường hợp. 5
Xây dựng nhiều mô hình học máy cho ba vấn đề phân đoạn hình ảnh khác nhau (bài toán đóng khung mặt người trên ảnh, bài toán phân đoạn muối trong ảnh địa chấn và bài toán phân đoạn mạch máu trong ảnh võng mạc). Ba bài toán này được chọn trong số các bài toán nổi tiếng trên thế giới. Trong cả ba trường hợp, các thống kê kết quả của chúng tôi cho thấy phương pháp biểu quyết tô-pô cho kết quả vượt trội hơn phương pháp biểu quyết số học cổ điển. 5. Công bố khoa học liên quan đến luận án Các kết quả của luận án được đăng trên 4 bài báo, 01 bài báo đăng trên tạp chí thuộc danh mục ISI, 01 bài báo đăng trên tạp chí thuộc danh mục Scopus, 02 bài báo HNKHQT. 6
Chương 1 KIẾN THỨC CHUẨN BỊ Chương 1 trình bày các kiến thức cơ bản mà sẽ được sử dụng trong các Chương 2, 3 và 4, đó là: - Mô hình chung của quá trình học máy, - Dữ liệu cho máy học, - Các “đặc trưng” trong học máy, - Kiểm tra hiệu quả của máy, - Tối ưu dựa trên Gradient, - Phép tích chập và mạng thần kinh tích chập. 7
Chương 2 ĐỘ CHÍNH XÁC CỦA MÁY PHÂN LOẠI NHỊ PHÂN 2.1 Các thước đo độ chính xác của máy phân loại nhị phân Phần này trình bày về các thước đo độ chính xác của máy phân loại nhị phân như: TP, TN, FN, FP, PR, WA, BA, Fb . 2.2 Đường cong ROC và các thước đo độ chính xác của các máy phân loại nhị phân mềm ˆ Trong thực tế học máy, để xây dựng một máy Y dự đoán cho một vấn đề phân lớp nhị phân Y : Ω → {0, 1} (2.1) người ta thường dùng các “phương pháp xác suất” và tạo ra một hàm số M : Ω → [0, 1] (2.2) để dự đoán giá trị của Y , sau đó đưa ra một mức: σ ∈ (0, 1), rồi với mỗi phần tử x ∈ Ω, đặt ˆ Y (x) = Yσ (x) = 1 nếu M (x) ≥ σ (2.3) ˆ Y (x) = Yσ (x) = 0 nếu M (x) < σ (2.4) 8
Định nghĩa 2.1. Với các ký hiệu như trên, hàm số Y được gọi là sự thật cơ bản, hàm số M được gọi là máy phân loại nhị phân "mềm" (soft binary classification ˆ machine), còn hàm số Y = Yσ được gọi là máy phân loại nhị phân "cứng", dự đoán của Y . PΩ (M (x) ≥ σ , Y (x) = 1) T P (σ) = P (Yσ = 1|Y = 1) = , PΩ (Y (x) = 1) (2.5) PΩ (M (x) < σ , Y (x) = 0) T N (σ) = P (Yσ = 0|Y = 0) = . PΩ (Y (x) = 0) (2.6) Định nghĩa 2.2. Đường cong ROC của một máy phân lớp nhị phân M là tập hợp các điểm trên mặt phẳng được xác định như sau: ROC = {ROC(σ) = (1 − T N (σ), T P (σ)), σ ∈ (0, 1)} Định nghĩa 2.3. AUC là diện tích phần nằm phía dưới của đường cong ROC trong hình vuông đơn vị, và nó là một thước đo phổ biến cho độ chính xác của máy (xem hình 2.1). Định nghĩa 2.4. Cho w ∈ (0, 1) là một trọng số, ta đặt: W A(σ) = w · T P (σ) + (1 − w) · T N (σ) (2.7) = w · T P (σ) − (1 − w) · F P (σ) + (1 − w) (2.8) Khi đó MWA = max W A(σ) được gọi là độ chính xác có σ∈[0,1] trọng tối đa. Khi w = 0.5 thì MWA trở thành độ chính xác cân bằng tối đa, kí hiệu là MBA. 9
Định nghĩa 2.5. T P (σ) + T N (σ) MBA = max BA(σ), trong đó BA(σ) = σ∈[0,1] 2 (2.9) được gọi là độ chính xác cân bằng tối đa. Định lý 2.1. Với các kí hiệu như trên: (i) Đối với một máy nhị phân M bất kỳ, ta có: 1 − 2(1 − M BA)2 ≥ AU C ≥ 2M BA − 1. (2.10) Hơn nữa, nếu đường cong ROC của máy M là lồi thì: AU C ≥ M BA. (2.11) (ii) Với mỗi trọng w ∈ (0, 1) bất kỳ, và với mỗi máy M tùy ý, ta có (1 − M W A)2 1− ≥ AU C. (2.12) 2w(1 − w) Hơn nữa, nếu đường cong ROC của máy M là lồi thì (1 − M W A) AU C ≥ 1 − . (2.13) 2 min(w, 1 − w) Chứng minh. (Xem hình 2.1). 2.3 Phép chiếu thông tin, hàm sigmoid và máy tối ưu Chúng ta có thể mô tả một máy nhị phân mềm M như một hợp thành của hai ánh xạ: M = Σ ◦ ϕ, (2.14) 10
2 Hình 2.1: Đường cong ROC và đường tiếp tuyến tại điểm mà trung bình có trọng lớn nhất. trong đó ϕ:Ω→Φ (2.15) được gọi là phép chiếu thông tin (information projec- tion map) từ không gian dữ liệu gốc Ω đến một không gian các thuộc tính chắt lọc (distilled features space) hoặc có thể gọi là không gian thông tin Φ, và Σ : Φ → [0, 1] (2.16) là một hàm từ không gian thông tin Φ tới đoạn [0, 1] hay hàm sigmoid suy rộng (generalized sigmoid func- tion). Định nghĩa 2.6. Với các ký hiệu như trên, hàm xác suất có điều kiện Σproba : Φ → [0, 1] cho bởi công thức Σproba (φ) = P (Y (x) = 1|ϕ(x) = φ) (2.17) (với mỗi φ ∈ Φ) được gọi là hàm sigmoid xác suất thực (probability sigmoid function), và máy Mproba = Σproba ◦ ϕ (2.18) được gọi là máy xác suất thực. 11
Định lý 2.2. Với các kí hiệu như trên, ta có: (i) Nếu hàm sigmoid Σ : Φ → [0, 1] là một hàm tùy ý, thì máy xác suất thực Mproba = Σproba ◦ ϕ chính xác hơn (hoặc ít nhất là chính xác bằng) máy M = Σ ◦ ϕ, theo nghĩa đường cong ROC của Mproba nằm phía trên đường cong ROC của M . Nói cách khác, đối với bất kỳ mức dương tính giả α ∈]0, 1[ nào, nếu σ và σproba là các mức tương ứng sao cho F PMproba (σproba ) = F PM (σ) = α, (2.19) thì T PMproba (σproba ) ≥ T PM (σ). (2.20) (ii) Đường cong ROC của máy xác suất thực Mproba là lồi. 2.4 Cải thiện độ chính xác bằng biểu quyết Xác suất Sn có ít nhất n/2 dự đoán đúng (trong số n các chuyên gia) xấp xỉ bằng √ n(p − 1/2) Sn ≈ Φ( √ ) (2.21) pq x 1 2 trong đó Φ(x) = √ e−x /2 dx (2.22) 2π −∞ Tập dữ liệu Ω được chia thành 3 phần như sau: Ω = Ωblind ∪ Ωhb ∪ Ωl (2.23) Công thức gần đúng cho độ chính xác của quyết định tập thể bằng biểu quyết là: √ n(p − 1/2) 1 Sn ≈ Φ( √ )(1 − Pblind − Phb ) + Phb (2.24) pq 2 12
Ta có công thức giới hạn sau: 1 lim Sn = 1 − Pblind − Phb (2.25) n→∞ 2 Công thức (2.25) cho thấy dù có biểu quyết đến mấy thì ta cũng không kì vọng đạt độ chính xác tuyệt đối, do có những “điểm mù” thông thường có tính hệ thống mà chúng ta không thể vượt qua. 2.5 Kết luận và bình luận cuối chương Chương 2 trình bày các kết quả chính. 1. Các bất đẳng thức giữa các thước đo độ chính xác: AUC ROC, MBA, MWA, từ đó kết luận các thước đo này tương đương về mặt tô-pô, theo nghĩa nếu một trong các thước đo đó có giá trị dần đến 1 thì các thước đo khác cũng có giá trị dần đến 1. Điều này có ý nghĩa là các thước đo độ chính xác AUC ROC, MWA và MBA có thể dùng thay thế cho nhau trong học máy. 2. Kết luận máy xác suất thực đối với một không gian thông tin đã cho là máy tối ưu, tức là nó có độ chính xác cao nhất trong số tất cả các máy có thể. Hơn nữa đường cong ROC của máy xác suất thực luôn là đường lồi. Kết quả này giúp ta tin tưởng khi sử dụng máy xác suất thực đối với bài toán phân lớp nhị phân vì máy này cho độ chính xác cao nhất trong số tất cả các máy có thể và đường cong ROC của nó là lồi. 13
Chương 3 ẢNH HƯỞNG CỦA HÀM MẤT MÁT ĐẾN CÁC BÀI TOÁN PHÂN LOẠI NHỊ PHÂN 3.1 Tổng quan về các hàm mất mát (loss function) Phần này trình bày một cách khái quát về các hàm mất mát hồi quy, các hàm mất mát phân loại và các hàm mất mát thường dùng trong phân đoạn hình ảnh. 3.2 Học máy vi phân và hàm mất mát Định nghĩa 3.1. Hàm mất mát bình phương là hàm có công thức như sau: ℓquadratic (m, y) = (m − y)2 (3.1) Định nghĩa 3.2. Hàm mất mát cross-entropy nhị phân là hàm có công thức như sau: ℓcrossentropy (m, y) = − ln(1 − |m − y|) (3.2) Định nghĩa 3.3. Hàm mất mát bậc bốn là hàm có công thức như sau: ℓquartic (m, y) = (m − y)2 + (m − y)4 (3.3) Định lý 3.1. Với các kí hiệu như trên, ta có: (i) Máy xác suất thực là điểm cực tiểu duy nhất của hàm mất mát bình phương. (ii) Máy xác suất thực cũng là điểm cực tiểu duy nhất của hàm mất mát cross-entropy nhị phân. 14
Hình 3.1: Dáng điệu một số hàm mất mát lồi. Hàm mất mát cross- entropy (hàm log) đã được điều chỉnh bằng cách cho thêm một số dương epsilon rất nhỏ vào đó để tránh tình huống ln 0. 3.3 Hàm mất mát lồi và xác suất bị bóp méo Định lý 3.2. Cho f : [0, 1] → R+ là một hàm số lồi tùy ý, đơn điệu tăng và khả vi sao cho f ′ (0) = 0 hoặc limσ→1 f ′ (σ) = +∞, c > 0 là một số dương tùy ý (hệ số bất đối xứng), và L(M ) = [(1 − Y (x)) · f (M (x)) + cY (x) · f (1 − M (x))] dx x∈Ω (3.4) là mất mát của máy M đối với bài toán phân loại nhị phân cho trước Y , được tạo bởi f và c. Khi đó, máy cực tiểu M = Σ ◦ ϕ đối với hàm mất mát L(M ) chỉ là một phép tham số hóa lại máy xác suất thực. Nói cách khác, có một song ánh tăng g : [0, 1] → [0, 1] sao cho máy với hàm sigmoid: Σ(φ) := g(Σproba (φ)) (3.5) có mất mát tối thiểu theo L 15
3.4 Các hàm mất mát không lồi và các bẫy ngẫu nhiên Phần này trình bày các kết quả thí nghiệm khi dùng hàm mất mát không lồi thì máy học dễ bị rơi vào các bẫy và có thể không thoát ra được. Hình 3.2: Rơi vào bẫy và không thoát ra được, trường hợp c=1 và r=9. 3.5 Kết luận và bình luận cuối chương Chương 3 trình bày ba kết quả chính về hàm mất mát. Thứ nhất là: Định lý 3.1 khẳng định rằng hàm mất mát cross-entropy nhị phân và hàm mất mát bình phương là các hàm mất mát tự nhiên nhất. Thứ hai là: Định lý 3.2 khẳng định rằng cực tiểu của một hàm mất mát lồi nghiêm ngặt tùy ý là một máy tối ưu có thể đưa về máy xác suất thực (máy đã được chứng minh trong Chương 2 là máy tối ưu) qua một phép biến đổi tham số. Thứ ba là: Các kết quả thử nghiệm trong (3.4) cho chúng ta thấy nếu hàm mất mát không lồi, thì cực tiểu của nó nói chung sẽ không phải là một máy tối ưu. 16
Chương 4 TỐI ƯU HÓA PHÂN ĐOẠN HÌNH ẢNH BẰNG BIỂU QUYẾT TÔ-PÔ 4.1 Phương pháp biểu quyết tô-pô 4.1.1 Phân đoạn hình ảnh và khoảng cách Jaccard Khoảng cách Jaccard của một mặt nạ S(x) đến mặt nạ thật (true mask) Strue (x) được xác định bởi công thức sau: dJaccard (S(x), Strue (x)) = 1 − J(S(x), Strue (x)), và nó đo “độ chênh lệch” giữa S(x) và Strue (x). Hai mặt nạ trùng nhau khi và chỉ khi khoảng cách Jaccard giữa chúng bằng 0. 4.1.2 Biểu quyết số học Biểu quyết số học cứng: Lấy theo đa số. Biểu quyết số học mềm: Lấy trung bình các mặt nạ mềm. 4.1.3 Biểu quyết tô-pô: Dạng đơn giản nhất Định nghĩa 4.1. Biểu quyết tô-pô phiên bản cứng bao gồm các bước sau: (i) Đối với hình ảnh đầu vào x, lấy n mặt nạ S1 (x), . . . , Sn (x) được cho bởi n phân đoạn khác nhau S1 , . . . , Sn ; (ii) Đối với mỗi chỉ số k ∈ {1, . . . , n}, đo tổng khoảng cách từ Sk (x) tới các mặt nạ khác, theo một hàm 17
khoảng cách tự nhiên nào đó. Xác định tổng khoảng cách dk (x) từ Sk (x) tới các mặt nạ khác theo công thức sau: n dk (x) = dJaccard (Si (x), Sk (x)) (4.1) i=1 (iii) (Winner takes all) Mặt nạ có tổng khoảng cách Jac- card đến các mặt nạ khác nhỏ nhất là chiến thắng, tức là Svoted (x) = Sl (x) với l = arg min dk (x) (4.2) k Một cách tương tự để có quy tắc “Người thắng lấy tất” (“winner takes all”) là: mặt nạ với tổng tỉ số Jaccard cao nhất chiến thắng, nghĩa là: Svoted (x) = Sl (x) với l = arg max Jk (x) (4.3) k và n Jk (x) = J(Si (x), Sk (x)) (4.4) i=1 Các khoảng cách tự nhiên khác nhau trong hình học phù hợp với các bài toán khác nhau. 4.1.4 Biểu quyết tô-pô địa phương Định nghĩa 4.2. Thuật toán biểu quyết tô-pô địa phương bao gồm các bước: (i) Chọn một số tự nhiên nào đó s, mà nó sẽ được dùng làm bán kính của lân cận địa phương; 18