ترجمه فارسی مقاله حداکثرسازی زیرمدولار ضعیف بدون قید منظم

چکیده

Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${O}(frac{n}εlog frac{n}{γε})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) geq γ(1-ε)f(OPT)-c(OPT)-frac{c(OPT)}{γ(1-ε)}logfrac{f(OPT)}{c(OPT)}$, where $γ$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.

چکیده به فارسی (ترجمه ماشینی)

بهینه سازی زیرودیک برنامه هایی در یادگیری ماشین و داده کاوی پیدا می کند.در این مقاله ، ما مسئله حداکثر رساندن عملکردهای فرم $ H = F-C $ را بررسی می کنیم ، جایی که $ f $ یک عملکرد یکنواخت ، غیر منفی ، ضعیف است و $ c $ یک عملکرد مدولار است.ما یک الگوریتم تقریبی قطعی را طراحی می کنیم که با $ {o} اجرا می شود ( frac {n} ε log frac {n {{γε}) $ oracle فراخوانی می کند تا $ h $ عمل کند ، و یک مجموعه $ s {s} $ چنین استکه $ h ({s}) geq γ (1-ε) f (opt) -c (opt)- frac {c (opt)} {γ (1-ε)} log frac {f (opt)} {C (OPT)} $ ، جایی که $ γ $ نسبت زیرمجموعه $ f $ است.الگوریتم های موجود برای این مشکل یا نسبت تقریب بدتر را قبول می کنند یا زمان اجرا درجه دوم دارند.ما همچنین نسبت تقریب الگوریتم خود را برای این مشکل با یک اوراکل تقریبی از $ f $ ارائه می دهیم.ما نتایج نظری خود را از طریق ارزیابی های تجربی گسترده در مورد برنامه های دنیای واقعی ، از جمله پوشش ورتکس و مشکلات انتشار تأثیر برای عملکرد ابزار فرعی $ F $ و طراحی بهینه A Bayesian برای ضعیف $ f $ تأیید می کنیم.نتایج تجربی ما نشان می دهد که الگوریتم های ما به طور مؤثر به راه حل های با کیفیت بالا می رسند.