Giải quyết bài toán Submodular Cover trong môi trường nhiễu cộng bằng thuật toán streaming

Bài toán Submodular Cover là một trong những phần quan trọng của toán tối ưu và thuật toán xấp xỉ. Nó được ứng dụng đa dạng trong học máy, khoa học máy tính, tiếp thị số và kinh tế. Bài viết trình bày nghiên cứu và đề xuất thuật toán Streaming để giải quyết cho bài toán Submodular cover trong môi trường nhiễu cộng (Streaming Submodular Cover under Additive Noise - SSCAN).
Nội dung trích xuất từ tài liệu:
Giải quyết bài toán Submodular Cover trong môi trường nhiễu cộng bằng thuật toán streamingKỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021DOI: 10.15625/vap.2021.00103 GIẢI QUYẾT BÀI TOÁN SUBMODULAR COVER TRONG MÔI TRƯỜNG NHIỄU CỘNG BẰNG THUẬT TOÁN STREAMING Nguyễn Thị Bích Ngân , Trần Hữu Lợi, Nguyễn Đình Thìn, Phạm Nguyễn Huy Phương Đại học Công nghiệp Thực phẩm TP. Hồ Chí Minh, nganntb@hufi.edu.vn, tranloi876@gmail.com, nguyendinhthinkg@gmail.com, phuongpnh@hufi.edu.vn TÓM TẮT: Bài toán Submodular Cover là một trong những phần quan trọng của toán tối ưu và thuật toán xấp xỉ. Nó đượcứng dụng đa dạng trong học máy, khoa học máy tính, tiếp thị số và kinh tế. Các nghiên cứu trước đây tập trung giải quyết bài toántrong môi trường không có nhiễu hoặc áp dụng thuật toán tham lam để giải quyết với môi trường có nhiễu. Tuy nhiên, dữ liệu thựctế của một số ứng dụng thường có quy mô rất lớn, do đó việc xuất hiện nhiễu trong dữ liệu là điều không tránh khỏi. Nguyên nhânnày làm giảm tính hiệu quả của các phương pháp được đề xuất trước đây hoặc không khả thi khi đưa vào ứng dụng. Dựa trên ýtưởng đó, trong bài báo này chúng tôi nghiên cứu và đề xuất thuật toán Streaming để giải quyết cho bài toán Submodular covertrong môi trường nhiễu cộng (Streaming Submodular Cover under Additive Noise - SSCAN). Phương pháp mà chúng tôi đề xuất sẽduyệt một lần qua bộ dữ liệu (single-pass streaming) trong khi vẫn đảm bảo kết quả có độ chính xác xấp xỉ tiệm cận kết quả tối ưu.Kết quả thực nghiệm cho thấy thuật toán SSCAN đạt kết quả cao với hàm mục tiêu (objective function) và có hiệu suất vượt trội sovới các thuật toán tham lam hiện tại cả về số lần truy vấn hàm mục tiêu và thời gian thực thi chương trình. Từ khóa: Submodular Cover, thuật toán xấp xỉ, nhiễu cộng, thuật toán Streaming. I. GIỚI THIỆU Việc tối ưu hóa các hàm submodular là một bài toán quan trọng trong nhiều lĩnh vực, đã được chứng minh quacác nghiên cứu khoa học. Nó xuất hiện rộng rãi trong nhiều ứng dụng như kinh tế [1], phúc lợi xã hội [21], tối ưu hóatổ hợp [2]. Trong khoa học máy tính, nó ứng dụng trong học máy [7] tiếp thị lan truyền [4], phân đoạn hình ảnh [11],tóm tắt tài liệu [15]. Hàm submodular được định nghĩa như sau: giả sử, cho hàm để đo giá trị của một tập hợp con S , với = { + là tập hợp nguồn. Hàm vừa có tính đơn điệu (monotone), vừa là submodular nếu với A BV, (A) (B) và , ta có: (A ∪ {x}) − (A) ≥ (B ∪ {x}) − (B) (1) Trong bài báo này, chúng tôi tập trung vào giải một bài toán nhỏ thuộc nhóm bài toán tối ưu hóa hàmsubmodular. Đó là bài toán Submodular Cover (SC) [10]. Nó được định nghĩa như sau: Định nghĩa 1: (Submodular Cover - SC) Cho một tập nguồn , một hàm có tính đơn điệu và là submodular : , một giá trị ngưỡng T (V), bài toán cần tìm những tập hợp con S V với số lượng tối thiểu sao cho (S) ≥ T. Bài toán SC được tìm thấy trong các nghiên cứu liên quan về tổng hợp dữ liệu [16, 17], giám sát vị trí [19], t mđộ ảnh hư ng trong mạng xã hội [9, 12], lựa chọn tập nhân [18]. Dựa vào các nghi n cứu gần đầy [19, 22, 23], các giảipháp hiện có cho bài toán SC thường giả định giá trị dự đoán của , nghĩa là có thể tính được tại bất k tập con S . Tuy nhiên, trong các ứng dụng và nghiên cứu đã chứng minh việc tính hàm f là rất khó và tốn nhiều chi phí [3,24]. Do đó, thay cho việc tính trực tiếp giá trị hàm , ch ng ta ch có thể tính một hàm thay thế F của . F là một giá trịxấp x tr n mô h nh nhiễu cộng của [6], nghĩa là: ( ) ( ) ( ) Gần đây, Crawford và cộng sự [6] lần đầu ti n nghi n cứu bài toán SC dưới mô h nh nhiễu. Tác giả đề xuất mộtthuật toán tham lam (Greedy) để giải quyết nó với các ngưỡng biên giá trị được chứng minh đảm bảo theo lý thuyết.Tuy nhi n, thuật toán này có độ phức tạp về thời gian là ( ) và trong một số trường hợp, nó không thể được áp dụngkhi dữ liệu quá lớn v số lần duyệt dữ liệu là n. Trong thực tế, dữ liệu của một số ứng dụng thường có dung lượng lớn, gây khó kh n trong việc lưu trữ dữ liệutrong máy tính. Do đó, một vấn đề quan trọng là cần đưa ra các thuật toán hiệu quả không ch cung cấp đảm bảo về lthuyết, mà c n phải duyệt dữ liệu ch ít lần. Để giải quyết thách thức này, ch ng tôi đề xuất thuật toán Streaming đểgiải quyết bài toán SC dưới nhiễu cộng. Phương pháp này ch cần duyệt dữ liệu một lần và vẫn đảm bảo giới hạn giá trịvề mặt l thuyết. Cụ thể, những đóng góp của ch ng tôi như sau: Ch ng tôi đề xuất thuật toán streaming để giải bài toán SC dưới mô hình nhiễu cộng (Streaming ...