دالة المجموعة الفرعية

الموسوعة الحرة

في الرياضيات، تُعرف دالة المجموعة شبه المعيارية (أو الدالة شبه المعيارية ) بأنها دالة تصف ، بشكل غير رسمي، العلاقة بين مجموعة من المدخلات ومخرج واحد، حيث يؤدي إضافة المزيد من أحد المدخلات إلى فائدة إضافية متناقصة ( تناقص العائد ). هذه الخاصية الطبيعية لتناقص العائد تجعلها مناسبة للعديد من التطبيقات، بما في ذلك خوارزميات التقريب ، ونظرية الألعاب (كدوال تُنمذج تفضيلات المستخدم)، والشبكات الكهربائية . وقد وُجدت الدوال شبه المعيارية مؤخرًا مفيدةً في العديد من المشكلات الواقعية في مجال التعلم الآلي والذكاء الاصطناعي ، بما في ذلك التلخيص التلقائي ، وتلخيص المستندات المتعددة ، واختيار الميزات ، والتعلم النشط ، وتحديد مواقع أجهزة الاستشعار، وتلخيص مجموعات الصور، والعديد من المجالات الأخرى. [ 1 ] [ 2 ] [ 3 ] [ 4 ]

تعريف

لوΩأوميغاإذا كانت مجموعة منتهية ، فإن الدالة شبه المعيارية هي دالة مجموعةو:2Ω→R{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }، أين2Ω{\displaystyle 2^{\Omega }}يشير إلى مجموعة القوى لـΩأوميغا، والتي تحقق أحد الشروط المكافئة التالية. [ 5 ]

  1. لكلX،Y⊆Ω{\displaystyle X,Y\subseteq \Omega }معX⊆Y{\displaystyle X\subseteq Y}وكلx∈Ω∖Y{\displaystyle x\in \Omega \setminus Y}لدينا ذلكو(X∪{x})-و(X)≥و(Y∪{x})-و(Y){\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}.
  2. لكلS،تي⊆Ω{\displaystyle S,T\subseteq \Omega }لدينا ذلكو(S)+و(تي)≥و(S∪تي)+و(S∩تي){\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}.
  3. لكلX⊆Ω{\displaystyle X\subseteq \Omega }وx1،x2∈Ω∖X{\displaystyle x_{1},x_{2}\in \Omega \backslash X}بحيثx1≠x2{\displaystyle x_{1}\neq x_{2}}لدينا ذلكو(X∪{x1})+و(X∪{x2})≥و(X∪{x1،x2})+و(X){\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}أو ما يعادل ذلك،و(X∪{x1})-و(X)≥و(X∪{x1،x2})-و(X∪{x2}){\displaystyle f(X\cup \{x_{1}\})-f(X)\geq f(X\cup \{x_{1},x_{2}\})-f(X\cup \{x_{2}\})}.

الدالة شبه المعيارية غير السالبة هي أيضاً دالة شبه جمعية ، ولكن الدالة شبه الجمعية ليست بالضرورة شبه معيارية.Ωأوميغاإذا لم يُفترض أن الدالة محدودة، فإن الشروط المذكورة أعلاه غير متكافئة. على وجه الخصوص، دالة و{\displaystyle f}محدد بواسطةو(S)=1{\displaystyle f(S)=1}لوS{\displaystyle S}محدود وو(S)=0{\displaystyle f(S)=0}لوS{\displaystyle S}تحقق خاصية اللانهاية الشرط الأول المذكور أعلاه، لكن الشرط الثاني لا يتحقق عندماS{\displaystyle S}وتي{\displaystyle T}هي مجموعات غير منتهية ذات تقاطع محدود.

أنواع وأمثلة على الدوال شبه المعيارية

روتيني

دالة المجموعةو{\displaystyle f}تكون رتيبة إذا كان لكلتي⊆S{\displaystyle T\subseteq S}لدينا ذلكو(تي)≤و(S){\displaystyle f(T)\leq f(S)}تتضمن أمثلة الدوال شبه المعيارية الرتيبة ما يلي:

الدوال الخطية (النمطية)
أي دالة من الشكلو(S)=∑أنا∈Swأنا{\displaystyle f(S)=\sum _{i\in S}w_{i}}تُسمى هذه الدالة دالة خطية. بالإضافة إلى ذلك، إذا∀أنا،wأنا≥0{\displaystyle \forall i,w_{i}\geq 0}إذن، الدالة f رتيبة.
وظائف إضافية للميزانية
أي دالة من الشكلو(S)=مين{ب، ∑أنا∈Swأنا}{\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}لكلwأنا≥0{\displaystyle w_{i}\geq 0}وب≥0{\displaystyle B\geq 0}يُطلق عليه اسم "الإضافة إلى الميزانية". [ 6 ]
وظائف التغطية
يتركΩ={هـ1،هـ2،...،هـن}{\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}لتكن مجموعة من المجموعات الجزئية لمجموعة أساسية ماΩ′{\displaystyle \Omega '}الوظيفةو(S)=|⋃هـأنا∈Sهـأنا|{\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}لS⊆Ω{\displaystyle S\subseteq \Omega }تُسمى هذه الدالة دالة التغطية. ويمكن تعميمها بإضافة أوزان غير سالبة إلى العناصر.
إنتروبيا
يتركΩ={X1،X2،...،Xن}{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}لتكن مجموعة من المتغيرات العشوائية . إذن لأيS⊆Ω{\displaystyle S\subseteq \Omega }لدينا ذلكح(S){\displaystyle H(S)}هي دالة شبه معيارية، حيثح(S){\displaystyle H(S)}هي إنتروبيا مجموعة المتغيرات العشوائيةS{\displaystyle S}، وهي حقيقة تُعرف باسم متباينة شانون . [ 7 ] ومن المعروف أن هناك متباينات أخرى لدالة الإنتروبيا، انظر متجه الإنتروبيا .
دوال رتبة الماترويد
يتركΩ={هـ1،هـ2،...،هـن}{\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}لتكن المجموعة الأساسية التي يُعرَّف عليها الماترويد. عندئذٍ تكون دالة رتبة الماترويد دالة شبه معيارية. [ 8 ]

غير رتيب

تُسمى الدالة شبه المعيارية غير الرتيبة دالة غير رتيبة . وبشكل أدق، تُسمى الدالة غير رتيبة إذا كانت تتمتع بخاصية أن إضافة المزيد من العناصر إلى مجموعة ما يمكن أن يقلل من قيمتها. بتعبير أدق، الدالةو{\displaystyle f}تكون غير رتيبة إذا كانت هناك مجموعاتS،تي{\displaystyle S,T}في نطاقهاS⊂تي{\displaystyle S\subset T}وو(S)>و(تي){\displaystyle f(S)>f(T)}.

متماثل

دالة فرعية غير رتيبةو{\displaystyle f}يُطلق عليه اسم متناظر إذا كان لكلS⊆Ω{\displaystyle S\subseteq \Omega }لدينا ذلكو(S)=و(Ω-S){\displaystyle f(S)=f(\Omega -S)}تتضمن أمثلة الدوال شبه المعيارية غير الرتيبة المتناظرة ما يلي:

قطع الرسم البياني
يتركΩ={v1،v2،...،vن}{\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}لتكن رؤوس الرسم البياني . لأي مجموعة من الرؤوسS⊆Ω{\displaystyle S\subseteq \Omega }يتركو(S){\displaystyle f(S)}يشير إلى عدد الحوافهـ=(u،v){\displaystyle e=(u,v)}بحيثu∈S{\displaystyle u\in S}وv∈Ω-S{\displaystyle v\in \Omega -S}ويمكن تعميم ذلك عن طريق إضافة أوزان غير سالبة إلى الحواف.
المعلومات المتبادلة
يتركΩ={X1،X2،...،Xن}{\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}لتكن مجموعة من المتغيرات العشوائية . إذن لأيS⊆Ω{\displaystyle S\subseteq \Omega }لدينا ذلكو(S)=أنا(S؛Ω-S){\displaystyle f(S)=I(S;\Omega -S)}هي دالة شبه معيارية، حيثأنا(S؛Ω-S){\displaystyle I(S;\Omega -S)}هي المعلومات المتبادلة.

غير متماثل

تُسمى الدالة شبه المعيارية غير الرتيبة وغير المتناظرة بالدالة غير المتناظرة.

القطع الموجهة
يتركΩ={v1،v2،...،vن}{\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}لتكن رؤوس رسم بياني موجه . لأي مجموعة من الرؤوسS⊆Ω{\displaystyle S\subseteq \Omega }يتركو(S){\displaystyle f(S)}يشير إلى عدد الحوافهـ=(u،v){\displaystyle e=(u,v)}بحيثu∈S{\displaystyle u\in S}وv∈Ω-S{\displaystyle v\in \Omega -S}ويمكن تعميم ذلك عن طريق إضافة أوزان غير سالبة إلى الحواف الموجهة.

الامتدادات المستمرة لدوال المجموعة شبه المعيارية

في كثير من الأحيان، عند وجود دالة مجموعة فرعية معيارية تصف قيم مجموعات مختلفة، نحتاج إلى حساب قيم المجموعات الكسرية . على سبيل المثال: نعلم أن قيمة الحصول على المنزل أ والمنزل ب هي √، ونريد معرفة قيمة الحصول على 40% من المنزل أ و60% من المنزل ب. ولتحقيق ذلك، نحتاج إلى امتداد متصل لدالة المجموعة الفرعية المعيارية.

بصورة رسمية، دالة مجموعةو:2Ω→R{\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }مع|Ω|=ن{\displaystyle |\Omega |=n}يمكن تمثيلها كدالة على{0،1}ن{\displaystyle \{0,1\}^{n}}، من خلال ربط كلS⊆Ω{\displaystyle S\subseteq \Omega }مع متجه ثنائيxS∈{0،1}ن{\displaystyle x^{S}\in \{0,1\}^{n}}بحيثxأناS=1{\displaystyle x_{i}^{S}=1}متىأنا∈S{\displaystyle i\in S}، وxأناS=0{\displaystyle x_{i}^{S}=0}وإلا. امتداد مستمر لـو{\displaystyle f}هي دالة متصلةF:[0،1]ن→R{\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }، الذي يتطابق مع قيمةو{\displaystyle f}علىx∈{0،1}ن{\displaystyle x\in \{0,1\}^{n}}، أيF(xS)=و(S){\displaystyle F(x^{S})=f(S)}.

تُستخدم أنواع عديدة من الامتدادات المستمرة للوظائف شبه المعيارية بشكل شائع، والتي تم وصفها أدناه.

امتداد لوفاس

تم تسمية هذا الامتداد على اسم عالم الرياضيات László Lovász . [ 9 ] النظر في أي ناقلx={x1،x2،...،xن}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}بحيث يكون كل0≤xأنا≤1{\displaystyle 0\leq x_{i}\leq 1}ثم يُعرَّف امتداد لوفاس على النحو التالي:

ول(x)=هـ(و({أنا|xأنا≥λ})){\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}

حيث ينتهي التوقعλ{\displaystyle \lambda }مختارة من التوزيع المنتظم على الفترة[0،1]{\displaystyle [0,1]}تكون دالة لوفاس الممتدة محدبة إذا وفقط إذاو{\displaystyle f}هي دالة فرعية معيارية.

امتداد متعدد الخطوط

لنفترض أي متجهx={x1،x2،...،xن}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}بحيث يكون كل0≤xأنا≤1{\displaystyle 0\leq x_{i}\leq 1}ثم يتم تعريف الامتداد متعدد الخطوط على النحو التالي [ 10 ] [ 11 ]F(x)=∑S⊆Ωو(S)∏أنا∈Sxأنا∏أنا∉S(1-xأنا){\displaystyle F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}.

بشكل بديهي، يُمثل xᵢ احتمال اختيار العنصر i للمجموعة. لكل مجموعة S ، يُمثل حاصل الضرب الداخلي احتمال أن تكون المجموعة المختارة هي S تحديدًا . بالتالي، يُمثل المجموع القيمة المتوقعة للدالة f للمجموعة المُشكّلة باختيار كل عنصر i عشوائيًا باحتمال xi، بشكل مستقل عن العناصر الأخرى .

إغلاق محدب

لنفترض أي متجهx={x1،x2،...،xن}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}بحيث يكون كل0≤xأنا≤1{\displaystyle 0\leq x_{i}\leq 1}ثم يُعرَّف الإغلاق المحدب على النحو التالي:و-(x)=مين(∑SαSو(S):∑SαS1S=x،∑SαS=1،αS≥0){\displaystyle f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}.

يكون الإغلاق المحدب لأي دالة مجموعة محدبًا على[0،1]ن{\displaystyle [0,1]^{n}}.

إغلاق مقعر

لنفترض أي متجهx={x1،x2،...،xن}{\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}بحيث يكون كل0≤xأنا≤1{\displaystyle 0\leq x_{i}\leq 1}ثم يُعرَّف الإغلاق المقعر على النحو التالي:و+(x)=الأعلى(∑SαSو(S):∑SαS1S=x،∑SαS=1،αS≥0){\displaystyle f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}.

العلاقات بين الامتدادات المتصلة

بالنسبة للتوسعات المذكورة أعلاه، يمكن إثبات أنو+(x)≥F(x)≥و-(x)=ول(x){\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}متىو{\displaystyle f}هي شبه معيارية. [ 12 ]

ملكيات

  1. تُعتبر فئة الدوال شبه المعيارية مغلقة تحت التراكيب الخطية غير السالبة . لنفترض أي دالة شبه معياريةو1،و2،...،وك{\displaystyle f_{1},f_{2},\ldots ,f_{k}}والأعداد غير السالبةα1،α2،...،αك{\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}ثم الدالةز{\displaystyle g}محدد بواسطةز(S)=∑أنا=1كαأناوأنا(S){\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}هو فرعي معياري.
  2. لأي دالة فرعية معياريةو{\displaystyle f}، الدالة المحددة بواسطةز(S)=و(Ω∖S){\displaystyle g(S)=f(\Omega \setminus S)}هو فرعي معياري.
  3. الوظيفةز(S)=مين(و(S)،ج){\displaystyle g(S)=\min(f(S),c)}، أينج{\displaystyle c}هو عدد حقيقي ، ويكون شبه معياري كلماو{\displaystyle f}هي دالة فرعية رتيبة. وبشكل أعم،ز(S)=ح(و(S)){\displaystyle g(S)=h(f(S))}تكون شبه معيارية، لأي دالة مقعرة غير متناقصةح{\displaystyle h}.
  4. لنفترض عملية عشوائية حيث مجموعةتي{\displaystyle T}يتم اختيارها مع كل عنصر فيΩ{\displaystyle \Omega }إدراجه فيتي{\displaystyle T}بشكل مستقل باحتماليةص{\displaystyle p}إذن، المتباينة التالية صحيحةهـ[و(تي)]≥صو(Ω)+(1-ص)و(∅){\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )}أين∅{\displaystyle \varnothing }هي المجموعة الفارغة . وبشكل أعم، لننظر في العملية العشوائية التالية حيث مجموعةS{\displaystyle S}يتم بناؤها على النحو التالي. لكل من1≤أنا≤ل،أأنا⊆Ω{\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }بناءSأنا{\displaystyle S_{i}}من خلال تضمين كل عنصر فيأأنا{\displaystyle A_{i}}بشكل مستقلSأنا{\displaystyle S_{i}}باحتمالصأنا{\displaystyle p_{i}}علاوة على ذلك، دعS=∪أنا=1لSأنا{\displaystyle S=\cup _{i=1}^{l}S_{i}}إذن، المتباينة التالية صحيحةهـ[و(S)]≥∑R⊆[ل]Πأنا∈RصأناΠأنا∉R(1-صأنا)و(∪أنا∈Rأأنا){\displaystyle \mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})}.

مشاكل التحسين

تتمتع الدوال شبه المعيارية بخصائص مشابهة جدًا للدوال المحدبة والمقعرة . ولهذا السبب، يمكن وصف مسألة التحسين التي تتعلق بتحسين دالة محدبة أو مقعرة بأنها مسألة تعظيم أو تصغير دالة شبه معيارية تخضع لبعض القيود.

تقليل دالة المجموعة الفرعية

تعتمد صعوبة تقليل دالة المجموعة شبه المعيارية على القيود المفروضة على المسألة.

  1. يمكن حساب مسألة تصغير دالة شبه معيارية غير المقيدة في وقت متعدد الحدود ، [ 13 ] [ 14 ] وحتى في وقت متعدد الحدود القوي . [ 15 ] [ 16 ] ويُعد حساب القطع الأدنى في الرسم البياني حالة خاصة من مسألة التصغير هذه.
  2. تُعدّ مسألة تقليل دالة شبه معيارية ذات حد أدنى لعدد عناصرها مسألة صعبة من نوع NP ، مع حدود دنيا لعامل التقريب من نوع عامل كثير الحدود. [ 17 ] [ 18 ]

تعظيم دالة المجموعة شبه المعيارية

على عكس حالة التصغير، فإن تعظيم دالة شبه معيارية عامة يُعدّ مسألة صعبة حسابيًا (NP-hard) حتى في حالة عدم وجود قيود. ولذلك، فإن معظم الأعمال في هذا المجال تُعنى بخوارزميات التقريب ذات الزمن متعدد الحدود، بما في ذلك الخوارزميات الجشعة أو خوارزميات البحث المحلي .

  1. تُقبل خوارزمية تقريبية بنسبة 1/2 في مسألة تعظيم دالة شبه معيارية غير سالبة. [ 19 ] [ 20 ] ويُعد حساب القطع الأقصى للرسم البياني حالة خاصة من هذه المسألة.
  2. تقبل مسألة تعظيم دالة شبه معيارية رتيبة تخضع لقيد العددية1-1/هـ{\displaystyle 1-1/e}خوارزمية التقريب. [ 21 ] [ 22 ] مشكلة التغطية القصوى هي حالة خاصة من هذه المشكلة.
  3. إن مسألة تعظيم دالة شبه معيارية رتيبة تخضع لقيد الماترويد (والتي تشمل الحالة المذكورة أعلاه) تقبل أيضًا1-1/هـ{\displaystyle 1-1/e}خوارزمية تقريبية. [ 23 ] [ 24 ] [ 25 ]

يمكن توحيد العديد من هذه الخوارزميات ضمن إطار عمل للخوارزميات قائم على التفاضل الجزئي. [ 18 ]

وبصرف النظر عن تصغير وتعظيم الدوال شبه المعيارية، هناك العديد من مشاكل التحسين الطبيعية الأخرى المتعلقة بالدوال شبه المعيارية.

  1. إن تقليل الفرق بين دالتين شبه معياريتين [ 26 ] ليس فقط مسألة صعبة من نوع NP، بل هو أيضاً غير قابل للتقريب. [ 27 ]
  2. إن تصغير/تعظيم دالة شبه معيارية تخضع لقيد مجموعة مستوى شبه معيارية (المعروف أيضًا باسم التحسين شبه المعياري الخاضع لقيد الغطاء شبه المعياري أو قيد حقيبة الظهر شبه المعياري) يسمح بضمانات تقريب محدودة. [ 28 ]
  3. إن تقسيم البيانات بناءً على دالة شبه معيارية لزيادة متوسط ​​الرفاهية يُعرف باسم مشكلة الرفاهية شبه المعيارية، والتي تقبل أيضًا ضمانات التقريب المحدودة (انظر تعظيم الرفاهية ).

التطبيقات

تظهر الدوال شبه المعيارية بشكل طبيعي في العديد من التطبيقات العملية، في مجالات الاقتصاد ، ونظرية الألعاب ، والتعلم الآلي ، ورؤية الحاسوب [ 4 ] [ 29 ] ، بالإضافة إلى الذكاء الاصطناعي بشكل عام [ 30 ] . ونظرًا لخاصية تناقص العوائد، تُنمذج الدوال شبه المعيارية تكاليف السلع بشكل طبيعي، حيث يكون الخصم أكبر غالبًا مع زيادة عدد السلع المشتراة. تُنمذج الدوال شبه المعيارية مفاهيم التعقيد والتشابه والتعاون عند ظهورها في مسائل التصغير. أما في مسائل التعظيم، فتُنمذج مفاهيم التنوع والمعلومات والتغطية.

انظر أيضاً

الاقتباسات

  1. ↑ H. Lin and J. Bilmes, A Class of Submodular Functions for Document Summarization, ACL-2011.
  2. ↑ S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.
  3. ↑ أ. كراوس و سي. غيسترين، القيمة غير المثلى للمعلومات في النماذج الرسومية، UAI-2005.
  4. 1 2 أ. كراوس و سي. غيسترين، ما وراء التحدب: شبه المعيارية في التعلم الآلي، ورشة عمل في مؤتمر ICML-2008
  5. ^ (شريفر 2003 ، §44، ص 766) 
  6. ↑ بوخبيندر، نيف؛ فيلدمان، موران (2018). "مسائل تعظيم الدوال شبه المعيارية" . في غونزاليس، تيوفيلو ف. (محرر). دليل خوارزميات التقريب والأساليب الاستدلالية، الطبعة الثانية: المنهجيات والتطبيقات التقليدية . تشابمان آند هول/سي آر سي. doi : 10.1201/9781351236423 . ISBN 9781351236423.
  7. ↑ "معالجة المعلومات والتعلم" (ملف PDF) . cmu.
  8. ^ فوجيشيجي (2005) ص.22
  9. ↑ لوفاس، ل. (1983). "الدوال شبه المعيارية والتحدب". البرمجة الرياضية: أحدث ما توصل إليه العلم . ص 235-257 . doi : 10.1007/978-3-642-68874-4_10 . ISBN  978-3-642-68876-8. S2CID 117358746 . 
  10. ↑ فوندراك، جان (17 مايو 2008). "التقريب الأمثل لمسألة الرفاهية شبه المعيارية في نموذج أوراكل القيمة" . وقائع الندوة السنوية الأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '08. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 67-74 . doi : 10.1145/1374376.1374389 . ISBN  978-1-60558-047-0. S2CID 170510 . 
  11. ^ كالينسكو، جرويا؛ تشيكوري، شاندرا؛ بال، مارتن؛ فوندراك ، يناير (يناير 2011). "تعظيم وظيفة رتيبة فرعية تخضع لقيود Matroid" . مجلة SIAM للحوسبة . 40 (6): 1740–1766 . دوى : 10.1137 / 080733991 . ISSN 0097-5397 . 
  12. ↑ فوندراك، جان. "التقنيات متعددة الأوجه في التحسين التوافقي: المحاضرة 17" (PDF) .
  13. ↑ غروتشل، م .؛ لوفاس، ل .؛ شريجفر، أ. (1981). "طريقة القطع الناقص ونتائجها في التحسين التوافقي". كومبيناتوريكا . 1 (2): 169-197 . doi : 10.1007/BF02579273 . hdl : 10068/182482 . S2CID 43787103 . 
  14. ↑ كانينغهام، دبليو إتش (1985). "حول تصغير الدوال شبه المعيارية". كومبيناتوريكا . 5 (3): 185-192 . doi : 10.1007/BF02579361 . S2CID 33192360 . 
  15. ↑ إيواتا، س.؛ فليشر، ل.؛ فوجيشيغي، س. (2001). "خوارزمية توافقية متعددة الحدود قوية لتقليل الدوال شبه المعيارية". مجلة ACM . 48 (4): 761-777 . doi : 10.1145/502090.502096 . S2CID 888513 . 
  16. ↑ شريجفر، أ. (2000). "خوارزمية توافقية لتقليل الدوال شبه المعيارية في وقت متعدد الحدود بقوة" . مجلة نظرية التوافق، السلسلة ب . 80 (2): 346-355 . doi : 10.1006/jctb.2000.1989 .
  17. ↑ Z. Svitkina و L. Fleischer، التقريب شبه المعياري: الخوارزميات القائمة على أخذ العينات والحدود الدنيا، مجلة SIAM للحوسبة (2011).
  18. 1 2 R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).
  19. ↑ U. Feige , V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.
  20. ↑ N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.
  21. ↑ نيمهاوزر، جورج ؛ وولسي، إل إيه؛ فيشر، إم إل (1978). "تحليل التقريبات لتعظيم دوال المجموعات شبه المعيارية I". البرمجة الرياضية . 14 (14): 265-294 . doi : 10.1007/BF01588971 . S2CID 206800425 . 
  22. ↑ ويليامسون، ديفيد ب. "الربط بين التحسين المستمر والتحسين المتقطع: المحاضرة 23" (PDF) .
  23. ↑ G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.
  24. ↑ M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).
  25. ↑ Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.
  26. ↑ M. Narasimhan و J. Bilmes، إجراء فرعي-فوق معياري مع تطبيقات لتعلم البنية التمييزية، في وقائع UAI (2005).
  27. ↑ R. Iyer و J. Bilmes، خوارزميات للتقليل التقريبي للفرق بين الدوال شبه المعيارية، في وقائع UAI (2012).
  28. ↑ R. Iyer و J. Bilmes، تحسين الوحدات الفرعية الخاضعة لغطاء الوحدات الفرعية وقيود حقيبة الظهر للوحدات الفرعية، في التقدم في NIPS (2013).
  29. ↑ ج. بيلمز، الوحدات الفرعية في تطبيقات التعلم الآلي، برنامج تعليمي في AAAI-2015.
  30. ↑ بيلمز، جيف (31 يناير 2022). "النمطية الفرعية في التعلم الآلي والذكاء الاصطناعي". arXiv : 2202.00132 [ cs.LG ].

مراجع