Xem mẫu
- Kỷ 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/2021
DOI: 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án
trong 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ực
tế 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ân
nà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 cover
trong 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 so
vớ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 qua
cá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óa
tổ 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 B
V, (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àm
submodular. Đó 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ải
phá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ột
thuậ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ụng
khi 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ệu
trong 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ề l
thuyế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
Submodular Cover under Additive Noise - SSCAN). Phương pháp này ch cần duyệt dữ liệu một lần và kết
quả có độ chính xác xấp x tiệm cận kết quả tối ưu. Cụ thể là, kết quả thuật toán t m được tập :
- 560 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…
( ) ( ) và ( ) , với
là các tham số đầu vào, là kết quả tối ưu của bài toán.
Ch ng tôi tiến hành thực nghiệm thuật toán tr n bài toán xác định tầm ảnh hư ng theo giá trị ngưỡng
(influenced threshold - IT), đây là một bài toán phổ biến trong phân tích mạng xã hội [17, 18, 23]. Kết quả
cho thấy thuật toán của ch ng tôi cung cấp các giải pháp của hàm F có giá trị cao và hoạt động tốt hơn so
với thuật toán hiện hành về cả số lượng truy vấn tính F và thời gian chạy chương tr nh.
Phần c n lại của bài báo được tổ chức như sau: Phần II thảo luận về các nghi n cứu liên quan. Phần III tr nh bày
các định nghĩa, thuật toán và phân tích l thuyết. Kết quả thực nghiệm và đánh giá kết quả được mô tả trong Phần IV.
Phần V là kết luận của bài báo.
II. CÁC NGHIÊN CỨU LIÊN QUAN
Một số nghiên cứu đã dùng phương pháp tham lam để giải bài toán SC với giá trị dự đoán f[19, 22, 23]. Wolsey
và cộng sự [23] đã chứng minh rằng nếu là hàm submodular và là một giá trị tích phân, t lệ xấp x của thuật toán
tham lam là ( ), trong đó là giá trị đơn điệu lớn nhất của . Ngược lại, nếu là giá trị thực, t lệ xấp x là
1+ ( ), trong đó β là độ lợi cận bi n khác 0 nhỏ nhất. Trong khi đó, nếu là một tích phân, Wan [22] đã chứng
minh rằng thuật toán tham lam có t lệ xấp x là γln(α), trong đó là độ cong của . Soma và Yoshida [19] đề xuất bài
toán SC tr n mạng lưới số nguy n, một phần m rộng của tập các hàm. Họ đã chứng minh rằng thuật toán ngưỡng
giảm dần có t lệ xấp x hai điều kiện là (1 + 3γ) (1 + ( )), với tham số đầu vào là < 1. Crawford và cộng sự
[6] đã nghi n cứu bài toán Submodular Cost Submodular Cover (SCSC) một phi n bản tổng quát của SC với một giá
trị xấp x gần đ ng với . Họ đã đề xuất thuật toán tham lam để giải quyết vấn đề này. Kết quả cung cấp t lệ xấp x là
(2 + ln((nα )/(γµ))), trong đó > 4 và (0, 1-4 ).
Hầu hết các nghi n cứu trước đây đều giả định dữ liệu không có nhiễu. Tuy nhiên, trong thực tế, nhiều ứng
dụng phải xử lý dữ liệu thường có nhiễu. Ví dụ, để tối đa hóa sự ảnh hư ng của tài khoản trong mạng xã hội, việc tính
hàm mục ti u lan truyền sự ảnh hư ng là rất khó và do đó thường được ước tính bằng cách mô phỏng quá tr nh khuếch
tán ngẫu nhi n [12] mang nhiễu. Khác với vấn đề nghi n cứu nói tr n, trong bài báo này, phương pháp streaming mà
ch ng tôi đề xuất sẽ duyệt một lần qua bộ dữ liệu trong khi vẫn đảm bảo ch ng có độ chính xác tiệm cận. 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 so
với các thuật toán tham lam hiện tại cả về số lần truy vấn tính hàm F và thời gian thực thi.
III. THUẬT TOÁN ĐỀ XUẤT
A. Định nghĩa bài toán
Cho một tập nguồn V = { + và một hàm : để đo lường giá trị của một tập hợp con S , với
A B V và B, là hàm có tính chất đơn điệu nếu (A) (B), và là một hàm submodular nếu
(A ∪ {x}) − (A) ≥ (B ∪ {x}) − (B) (2)
Để đơn giản, ch ng tôi k hiệu S + là S ∪ { + và giả sử rằng ( ) = 0. Giả định rằng giá trị hàm mục tiêu
( ) không tính được, nhưng giá trị hàm ( ), là giá trị xấp x của ( ) th tính được dễ dàng. Trong bài báo này, ch ng
tôi xem x t bài toán SC dưới mô hình dự đoán nhiễu cộng với giá trị dự đoán -nhiễu cộng, được định nghĩa như sau:
Định nghĩa : ( -nhiễu ng) Một hàm F : là một dự đoán nhiễu cộng của nếu S , ta có:
( ) ( ) ( ) (3)
Trong bài báo này, ch ng tôi nghi n cứu bài toán Submodular cover trong môi trường nhiễu cộng (SSCAN),
được định nghĩa như sau:
Định nghĩa : (SSCAN) Cho tập hợp V, một ngưỡng T, một giá trị dự đoán nhiễu cộng F, là xấp x của một
hàm đơn điệu và submodular : . Bài toán y u cầu t m tập con S có nhỏ nhất sao cho ( ) .
Trong suốt bài báo này, ch ng tôi k hiệu S* là một kết quả tối ưu và OPT = . Ch ng tôi gọi một thuật toán
là xấp x nhị phân (α, β) cho bài toán SSCAN nếu nó trả về một tập S thỏa mãn ( ) . T và . OPT, với
0.
B. Thuật toán Streaming
Ch ng tôi đề xuất một thuật toán streaming duyệt dữ liệu một lần cho bài toán SSCAN. Ý tư ng chính của thuật
toán là: (1) Dự đoán giá trị của OPT dựa tr n tập các những phần tử đang x t, gi p giảm bộ nhớ cho việc lưu trữ các
tập S ứng vi n của bài toán; (2) So sánh sự t ng giá trị của hàm F tr n mỗi phần tử để lựa chọn các phần tử mang lại
giá trị F cao hơn đưa vào tập kết quả.
- 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 561
Thuật toán có các tham số đầu vào gồm: ngưỡng T, các tham số m, , tham số l được kh i tạo ban đầu
l=⌈ ( ) ⌉, tập các ứng vi n và một tập dự đoán X được kh i tạo rỗng. Đối với mỗi phần tử e, nếu e
thỏa điều kiện tr n d ng 5 th nó cũng đảm bảo rằng:
( ) ( )
khi thuật toán cập nhật X bằng cách th m e. Đồng thời, l cũng sẽ được cập nhật để giảm số lượng tập ứng vi n và thời
gian thực thi của thuật toán. Tiếp theo thuật toán sẽ cập nhật tập giải pháp như sau: nếu th m e vào thỏa điều kiện
( ∪ * +) ( )
( )
th thuật toán sẽ th m e vào . Ngược lại, thuật toán sẽ bỏ qua e và chuyển đến tập giải pháp tiếp theo. Giá trị của
( ∪ * +) ( ) đại diện cho độ t ng của f tại e khi chúng ta thêm e vào .
Sau khi duyệt một lần qua toàn bộ dữ liệu ban đầu, thuật toán sẽ t m lời giải tốt nhất trong các tập giải pháp. Chi
tiết thuật toán được mô tả đầy đủ trong Thuật toán SSCAN.
Thuật toán SSCAN
Input: Hàm F, ngưỡng T, ( , ,n
Output: Tập con S
1. ⌈ ( ) ⌉,
2.
3.
4. foreach do
5. if ( ∪ * +) then
6. Xóa với
7. Cập nhật ⌈ ( ) ⌉
8. else
9. ∪* +
10. for i = 1 to l do
11. if ( ∪ * +) ( ) and ( ) then
( )
12. ∪* +
13. Tìm * +* ( ) ( ) +.
14. return S
Khi phân tích độ phức tạp của thuật toán SSCAN, ch ng ta thấy rằng SSCAN là thuật toán streaming duyệt các
phần tử trong V một lần. Độ phức tạp của thuật toán phụ thuộc hoàn toàn vào số lần lặp của 2 d ng lệnh (4) và (10).
Lệnh (4) luôn chạy n lần, và trong trường hợp xấu nhất lệnh (10) chạy l với ⌈ ( ) ⌉. Do đó, thuật toán SSCAN
có ( ( ) ) độ phức tạp truy vấn hàm F và chiếm ( ( ) ) về độ phức tạp bộ nhớ.
IV. THỰC NGHIỆM
Trong mục này, ch ng tôi tiến hành một số thực nghiệm tr n bài toán ngưỡng của tầm ảnh hư ng (Influence
Threshold - IT), đây là một ứng dụng của bài toán SC [6].
Mô tả bài toán IT. Cho ( ) là một mạng xã hội mà trong đó các đ nh V đại diện cho các người dùng,
cạnh E đại diện cho các mối quan hệ trong mạng xã hội. Giả sử ( ) ( ) ( ), trong đó
, đại diện cho N thể hiện của các cộng đồng trong mạng xã hội. Trong mỗi thể hiện, các cá nhân bị ảnh hư ng
trong mạng xã hội bắt nguồn từ một tập nhân ban đầu rồi sau đó họ mới lan truyền thông tin của m nh đến những cá
nhân khác trong mạng xã hội thông qua các cạnh. Đặt là một hàm xác định sự ảnh hư ng được lan truyền
của một nhân S, hay nói cách khác, là số người dùng bị ảnh hư ng qua quá trình lan truyền thông tin. Với ( )
là số lượng đ nh trung b nh mà các đ nh từ S có thể đi đến được trong từng thể hiện của N thể hiện và hàm f là một hàm
đơn điệu và submodular. Cho ngưỡng ( ), y u cầu của bài toán IT là t m tập nhân S sao cho:
* ( ) +.
- 562 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…
Nghiên cứu của Crawford [6] đã chứng minh việc tính f là một bài toán #P-hard, chúng ta ch có thể tính được
hàm F, là một -nhiễu cộng xấp x của f, bằng cách áp dụng cách tính khả n ng lan truyền với độ xấp x được đề xuất
trong nghi n cứu của Cohen [5].
Trong mục này, tất cả các thử nghiệm sẽ được triển khai để so sánh các thông số trả về của hai thuật toán là
SSCAN và thuật toán Greedy [6].
Từ dữ liệu thu được, ch ng ta có thể đánh giá hiệu suất của từng thuật toán dựa trên các yếu tố như thời gian
thực thi, t lệ , số lần truy vấn tính F, độ lớn tập nhân S.
Hình 1. So sánh kết quả thực nghiệm của thuật toán SSCAN và Greedy với m = 0,5 tr n bộ dữ liệu ArXiV
A. Thiết lập thực nghiệm
1. Tập dữ liệu để thực nghiệm
Để cho thử nghiệm được thực hiện một cách tổng quát, ch ng tôi đã chọn 2 bộ dữ liệu bao gồm: ArXiV 1 General
Relativity collaboration network [13] và LastFM 2 Asia Social Network, [14] được thử nghiệm phổ biến trong các bài
toán phân tích mạng xã hội. Chi tiết các bộ dữ liệu được mô tả trong Bảng 1.
1
https://snap.stanford.edu/data/ca-GrQc.html
- 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 563
Bảng 1. Mô tả các tập dữ liệu thực nghiệm
Tập dữ liệu Số nút Số ạnh Kiểu đồ thị
ArXiV 5242 14496 Vô hướng, không có trọng số
LastFM 7624 27806 Vô hướng, không có trọng số
2. Môi trường cài đặt
Tất cả các thử nghiệm được triển khai tr n hệ thống Linux với 2 x Intel(R) Xeon CPU E5-2630 v4 @ 2.20GHz,
64GB DDR4 @2400MHz RAM. Thuật toán được cài đặt bằng ngôn ngữ C++ và bi n dịch bằng g++ 11.
3. So sánh thuật toán và cài đặt tham số
Ch ng tôi thử nghiệm hai thuật toán là SSCAN và Tham lam (Greedy) [6] để t m tập nhân S nhỏ nhất nhưng nó
phải đảm bảo có giá trị ảnh hư ng đạt mức ngưỡng T và có thời gian thực thi nhanh nhất.
Dựa tr n thuật toán Greedy, ch ng tôi đặt các tham số cụ thể như sau: các tập dữ liệu trong thực nghiệm là các
đồ thị có hướng, có trọng số. Ch ng tôi đã tiền xử l các bộ dữ liệu từ đồ thị vô hướng, không trọng số sang đồ thị có
hướng có trọng số bằng cách áp dụng phương pháp Trivalent Weighted Model [12]. Mỗi cạnh có hướng sẽ được phân
phối ngẫu nhiên một xác suất * +. Cách tính F được dựa trên cách tính Reachability của [5]. Các
tham số mặc định: ⌈ ⌉ , * + và kết quả ch ng tôi chọn giá trị m = 0,5
để minh họa v kết quả này là tốt nhất. Tùy thuộc vào số n t của các bộ dữ liệu mà giá trị ngưỡng T sẽ thay đổi, cách
nhau 1000 node. Cụ thể như sau: bộ ArXiV có T {1000, 2000, 3000, 4000, 5000}; bộ LastFM có T {1000, 2000,
3000, 4000, 5000, 6000, 7000}.
B. Kết quả thử nghiệm
Trong thực nghiệm, ch ng tôi so sánh về thời gian chạy (tính giây), số lần truy vấn tính F, t lệ F/T, số phần tử
tập nhân S và dung lượng bộ nhớ RAM được sử dụng. Trong đó, hai lợi thế vượt trội của SSCAN so với Greedy là: (1)
Giá trị của hàm F gần với ngưỡng T và số phần tử của tập nhân S của SSCAN gần với kích thước của tập S khi chạy
Greedy; (2) Thời gian thực thi của SSCAN nhanh hơn Greedy từ 6,8 đến 98,4 lần, số lần truy vấn tính F của SSCAN
nhỏ hơn số lần của Greedy từ 10,4 đến 137,1 lần. Kết quả được thể hiện trong các Hình 1, 2.
1. Thời gian thực thi và số lần truy vấn tính hàm F
Thuật toán SSCAN có độ phức tạp phụ thuộc vào n và m, không phụ thuộc vào T. Đặc biệt, độ phức tạp của
thuật toán t lệ nghịch với m, m càng lớn th số lần duyệt t m S càng ít. Ngoài ra, số lần duyệt t m S ch phụ thuộc m,
không phụ thuộc vào T cho n n thời gian chạy của DSSA gần như xác định, ch dao động nhỏ quanh một lượng thời
gian nhất định. Ngược lại thuật toán Greedy phụ thuộc hoàn toàn vào T, khi T càng tiệm cận với n, làm cho thời gian
chạy của Greedy rất lâu, và khi n là dữ liệu lớn, Greedy tr nên bất khả thi v độ phức tạ của nó là ( )
Greedy có thời gian chạy lâu vì nó phải lồng hai lần duyệt các phần tử để duyệt qua bộ dữ liệu nhằm tìm ra
được tập nhân S có tầm ảnh hư ng cao nhất. Ngược lại, SSCAN có độ phức tạp là ( ( ) ), thực hiện dựa tr n
kỹ thuật streaming n n ch duyệt một lần qua bộ dữ liệu để t m các phần tử có F thỏa điều kiện của ngưỡng T. B i v ,
thời gian chạy chương tr nh chủ yếu t m phần tử và tính F của nó, cho n n số lần truy vấn tính F t lệ thuận thời gian
thực thi của mỗi thuật toán. Kết quả thực nghiệm cho thấy hai thông số thời gian thực thi và số lần truy vấn tính F của
SSCAN có thể nhanh hơn Greedy rất nhiều lần tùy thuộc vào cấu tr c và số lượng phần tử của dữ liệu. Ngoài ra, nếu
dữ liệu càng lớn th Greedy chạy càng lâu và có thể không khả thi thực hiện.
Trong H nh 1 và 2, phần thời gian chạy và số lần truy vấn F của SSCAN gần như không đổi trong khi Greedy
t ng tuyến tính theo T. B i v , như đã phân tích độ phức tạp thuật toán, Greedy phụ thuộc hoàn thoàn vào T, ngược
lại SSCAN ch phụ thuộc m, không phụ thuộc T. Do vậy khi m cố định th T dù có thay đổi cũng không làm ảnh hư ng
nhiều đến thời gian chạy và số lần truy vấn F của SSCAN.
2. Tỷ lệ F/T
B i v thuật toán Greedy tính F cho mọi phần tử của V trong từng lần lặp n n nó luôn t m ra được tập nhân S mà
có giá trị F gần như là bằng với ngưỡng T. Ngược lại, thuật toán SSCAN ch cần tìm ra tập nhân S mà thỏa điều kiện
( ) ( ) . Vì vậy, kết quả của thuật toán cho thấy giải pháp S mà thuật toán của chúng tôi tìm ra có ( )
gần với giá trị ngưỡng T trong từng trường hợp thử của các bộ tham số đầu vào. Kết quả thể hiện rõ Hình 1 và 2,
phần t lệ F/T. Kết quả của Greedy hầu như không đổi với mọi ngưỡng T, ngược lại SSCAN ch tính F gần đạt ngưỡng
T, nhưng vẫn đảm bảo xấp x ( ) ( ) .
2
https://snap.stanford.edu/data/feather-lastfm-social.html
- 564 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…
Hình 2. So sánh kết quả thực nghiệm của thuật toán SSCAN và Greedy với m = 0,5 tr n bộ dữ liệu LastFM
3. Kích thước tập nhân S
Theo kết quả thực nghiệm, thể hiện trong Hình 1 và 2, kích thước của tập nhân S của thuật toán SSCAN có t lệ so
với kích thước tập nhân S của thuật toán Greedy từ 0,8 đến 1,2 lần. Đây là kết quả rất tốt đối với loại dạng thuật toán xấp
x tối ưu. V |S| của SSCAN không phải ch có t m S có số lượng lớn hơn của Greedy mà cũng có trường hợp nhỏ hơn.
4. Tài nguyên sử dụng bộ nhớ RAM
Khi thực thi chương tr nh, thuật toán SSCAN phải thực hiện việc lưu các tập ứng vi n Si tiềm n ng để có thể t m
được kết quả sau cùng, việc này vốn không cần thiết đối với thuật toán tham lam, n n thuật toán SSCAN ti u tốn nhiều
tài nguy n hơn thuật toán Greedy từ 1,2 đến 2,7 lần.
Tóm lại, mặc dù việc chiếm dụng bộ nhớ RAM của SSCAN nhiều hơn Greedy, nhưng sự thua k m đó là nhỏ khi
so sánh với lợi thế về chi phí thời gian và hiệu quả tập nhân S do SSCAN t m được. Hiệu quả mà SSCAN mang lại đáp
ứng y u cầu xử l nhanh và t m được tập nhân kết quả đạt y u cầu ngưỡng của các tập dữ liệu lớn chứa nhiễu trong các
ứng dụng ngày nay.
- 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 565
V. KẾT LUẬN
Trong bài báo này, ch ng tôi đề xuất thuật toán streaming để giải quyết bài toán Submodular cover trong môi
trường nhiễu cộng (SSCAN) có ràng buộc giá trị ngưỡng. Ch ng tôi so sánh kết quả thực nghiệm giữa thuật toán của
ch ng tôi với thuật toán hiện đại khác là Greedy. Kết quả cho thấy rằng SSCAN có khả n ng m rộng cao và hoạt động
tốt hơn với các bộ dữ liệu lớn khi điều ch nh các bộ tham số phù hợp. Trong tương lai, ch ng tôi có kế hoạch triển khai
thuật toán SSCAN để đánh giá thời gian chạy nhỏ nhất và kích thước tập hợp hạt giống trong các tập dữ liệu lớn hơn
và đa dạng hơn.
TÀI LIỆU THAM KHẢO
[1]. Rabah Amir, “Supermodularity and complementarity in economics: An elementary survey”, Southern Economic Journal,
71(3): pp.636-660, 2005.
[2]. N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz, “A tight linear time (1/2)-approximation for unconstrained submodular
maximization”. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 649-658, 2012.
[3]. Qian. Chao, Shi. Jing-Cheng, Yu. Yang, Tang. Ke, and Zhou. Zhi-Hua, “Subset selection under noise”. In Advances in Neural
Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[4]. Wei Chen, Chi Wang, and Yajun Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social
networks”, In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
page 1029-1038, USA, 2010. Association for Computing Machinery.
[5]. Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F. Werneck, “Sketch-based influence maximization and computation:
Scaling up with guarantees”, In Jianzhong Li, Xiaoyang Sean Wang, Minos N. Garofalakis, Ian Soboroff, Torsten Suel, and
Min Wang, editors, Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge
Management, CIKM 2014, Shanghai, China, November 3-7, 2014, pages 629-638. ACM, 2014.
[6]. Victoria G. Crawford, Alan Kuhnle, and My T. Thai, “Submodular cost submodular cover with an approximate oracle”, In
Proceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97, pages 1426-1435. PMLR,
2019.
[7]. Abhimanyu Das and David Kempe, “Approximate submodularity and its applications: Subset selection, sparse approximation
and dictionary selection”, Journal of Machine Learning Research, 19(3):1-34, 2018.
[8]. Satoru Fujishige, “Submodular Functions and Optimization”, page 71-104. 2005.
[9]. Amit Goyal, Francesco Bonchi, V. S. Laks Lakshmanan, and Suresh Venkatasubramanian, “On minimizing budget and time in
influence propagation over social networks Social Netw”, Analys. Mining, pages 179-192, 2013.
[10]. Rishabh K. Iyer and Jeff A. Bilmes, “Submodular optimization with submodular cover and submodular knapsack constraints”,
In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural
Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of
a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2436-2444, 2013.
[11]. S. Jegelka and J. Bilmes, “Submodularity beyond submodular energies: Coupling edges in graph cuts”, In CVPR 2011, pages
1897-1904, 2011.
[12]. David Kempe, Jon M. Kleinberg, and Éva Tardos, “Maximizing the spread of influence through a social network” In
Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington,
DC, USA, August 24 - 27, 2003, pages 137-146, 2003.
[13]. Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. “Graph evolution: Densification and shrinking diameters”, ACM Trans.
Knowl. Discov. Data, 1(1):2-es, March 2007.
[14]. Benedek Rozemberczki and Rik Sarkar, “Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to
Parametric Models”, Proceedings of the 29th ACM International Conference on Information and Knowledge Management
(CIKM '20), pp. 1325-1334, 2020.
[15]. Hui Lin and Jeff Bilmes, “A class of submodular functions for document summarization”, In Proceedings of the 49th Annual
Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 510-520, Portland, Oregon,
USA, June 2011. Association for Computational Linguistics.
[16]. Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause, “Distributed submodular cover:
Succinctly summarizing massive data”, In Proceedings of the 28th International Conference on Neural Information Processing
Systems - Volume 2, NIPS’15, page 2881-2889, Cambridge, MA, USA, 2015. MIT Press.
[17]. Baharan Mirzasoleiman, Morteza Zadimoghaddam, and Amin Karbasi, “Fast distributed submodular cover: Public-private data
summarization”, In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16,
page 3601-3609. Curran Associates Inc., 2016.
[18]. Ashkan Norouzi-Fard, Abbas Bazzi, Ilija Bogunovic, Marwa El Halabi, Ya-Ping Hsieh, and Volkan Cevher, “An efficient
streaming algorithm for the submodular cover problem”, In Advances in Neural Information Processing Systems 29: Annual
Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 4493-4501, 2016.
[19]. Tasuku Soma and Yuichi Yoshida. “A generalization of submodular cover via the diminishing return property on the integer
lattice’, In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing
Systems, volume 28. Curran Associates, Inc., 2015.
[20]. Matthew Streeter and Daniel Golovin, “An online algorithm for maximizing submodular functions”, In D. Koller, D.
Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc.,
2009.
- 566 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…
[21]. Jan Vondrak, “Optimal approximation for the submodular welfare problem in the value oracle model”, In Proceedings of the
Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 67-74, New York, NY, USA, 2008. Association
for Computing Machinery.
[22]. P. Wan, D. Du, P. Pardalos, and W. Wu. “Greedy approximations for minimum submodular cover with submodular cost”,
Computational Optimization and Applications, 45:463-474, 2010.
[23]. L.A. Wolsey “An analysis of the greedy algorithm for the submodular set covering problem”, LIDAM Reprints CORE 519,
Université catholique de Louvain, Center for Operations Research and Econometrics (CORE), January 1982.
[24]. Ruiqi Yang, Dachuan Xu, Yukun Cheng, Chuangen Gao, and Ding-Zhu Du, “Streaming submodular maximization under
noises”, In 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019, Dallas, TX, USA, July 7-10,
2019, pages 348-357. IEEE, 2019.
STREAMING ALGORITHM FOR SUBMODULAR COVER PROBLEM UNDER ADDITIVE NOISE
Nguyen Thi Bich Ngan, Tran Huu Loi, Nguyen Dinh Thin, Pham Nguyen Huy Phuong
ABSTRACT: Submodular cover problem is one of the important parts of the optimization and approximation algorithms.
It is widely used in machine learning, computer science, digital marketing, and economics. Previous studies focused on solving
problems in non-noise environments or applying greedy algorithms to solve under noise. However, the actual data of some
applications are often very large scale, so the occurrence of noise in data is inevitable. This cause reduces the effectiveness of the
previously proposed methods or is not feasible in the application. Motivated by this phenomenon, in this article, we study and
propose the Streaming algorithm to solve the Submodular cover problem in the additive noise environment (Streaming Submodular
Cover under Additive Noise - SSCAN). Our method handles a single pass streaming while ensuring that they are as close as possible
to the bicriteria approximation model. The experimental results show that the SSCAN algorithm achieved high value of objective
functions and outperformed the-state-of-art greedy algorithms in terms of both number of queries and running time.
nguon tai.lieu . vn
