Algoritma seçimi - Algorithm selection

Algoritma seçimi (bazen de denir örnek başına algoritma seçimi veya çevrimdışı algoritma seçimi) bir meta-algoritmik teknik bir portföyden örnek bazında bir algoritma seçmek için. Algoritmaların birçok pratik problemde farklı performansları olduğu gözlemi ile motive edilir. Diğer bir deyişle, bir algoritma bazı durumlarda iyi performans gösterirken, diğerlerinde kötü performans gösterir ve bunun tersi başka bir algoritma için de geçerlidir. Hangi algoritmayı ne zaman kullanacağımızı belirleyebilirsek, her iki dünyanın da en iyisini elde edebilir ve genel performansı artırabiliriz. Algoritma seçiminin yapmayı amaçladığı şey budur. Algoritma seçim tekniklerini uygulamak için tek ön koşul, bir dizi tamamlayıcı algoritmanın mevcut olmasıdır (veya oluşturulabilir).

Tanım

Bir portföy verildiğinde ${ displaystyle { mathcal {P}}}$ algoritmaların ${ mathcal {P}}} içinde { displaystyle { mathcal {A}}$ , bir dizi örnek ${ mathcal {I}}} içinde { displaystyle i$ ve bir maliyet ölçütü ${ displaystyle m: { mathcal {P}} times { mathcal {I}} to mathbb {R}}$ algoritma seçim problemi bir eşleme bulmaktan ibarettir ${ displaystyle s: { mathcal {I}} - { mathcal {P}}}$ örneklerden ${ displaystyle { mathcal {I}}}$ algoritmalara ${ displaystyle { mathcal {P}}}$ öyle ki maliyet ${ displaystyle toplamı _ {i { mathcal {I}}} m (s (i), i)}$ tüm örneklerde optimize edilmiştir.^[1]^[2]

Örnekler

Boolean tatmin problemi (ve diğer zor kombinatoryal problemler)

Algoritma seçiminin iyi bilinen bir uygulaması, Boole karşılanabilirlik sorunu. Burada, algoritma portföyü bir dizi (tamamlayıcı) SAT çözücüler örnekler Boole formülleridir, maliyet ölçüsü örneğin ortalama çalışma süresi veya çözülmemiş örneklerin sayısıdır. Bu nedenle amaç, her bir örnek için iyi performans gösteren bir SAT çözücü seçmektir. Aynı şekilde, algoritma seçimi diğer birçok ${ displaystyle { mathcal {NP}}}$ -zor problemler (örneğin karışık tamsayı programlama, CSP, AI planlaması, TSP, MAXSAT, QBF ve cevap seti programlama ). SAT'da rekabet kazanan sistemler SATzilla,^[3] 3S^[4] ve CSHC^[5]

Makine öğrenme

İçinde makine öğrenme algoritma seçimi daha çok meta öğrenme. Algoritma portföyü makine öğrenimi algoritmalarından (ör. Random Forest, SVM, DNN) oluşur, örnekler veri kümeleridir ve maliyet ölçüsü örneğin hata oranıdır. Yani amaç, hangi makine öğrenimi algoritmasının her veri setinde küçük bir hata içereceğini tahmin etmektir.

Örnek özellikleri

Algoritma seçim problemi esas olarak makine öğrenimi teknikleriyle çözülür. Problem örneklerini sayısal özelliklerle temsil ederek ${ displaystyle f}$ algoritma seçimi bir çok sınıflı sınıflandırma bir haritalama öğrenerek problem ${ displaystyle f_ {i} mapsto { mathcal {A}}}$ belirli bir örnek için ${ displaystyle i}$ .

Örnek özellikleri, örneklerin sayısal temsilleridir. Örneğin, Boole formülleri için değişkenlerin sayısını, cümleleri, ortalama cümle uzunluğunu sayabiliriz,^[6] veya ML veri kümelerinin özellikleri hakkında bir izlenim elde etmek için örnek sayısı, özellikleri, sınıf dengesi.

Statik ve problama özellikleri

İki tür özelliği birbirinden ayırıyoruz:

Statik özellikler çoğu durumda bazı sayılar ve istatistiklerdir (örneğin SAT'daki cümle-değişken oranı). Bu özellikler, çok ucuz özelliklerden (örneğin değişken sayısı) çok karmaşık özelliklere (örneğin, değişken cümleci grafiklerle ilgili istatistikler) kadar çeşitlilik gösterir.
Problama özellikleri (bazen işaretleme özellikleri olarak da adlandırılır), bir örnekte algoritma davranışının bazı analizlerini çalıştırarak (örneğin, bir ML veri setinde ucuz bir karar ağacı algoritmasının doğruluğu veya kısa bir süre için bir stokastik yerel arama çözümleyicisini çalıştırarak Boole formülü). Bu özellikler genellikle basit statik özelliklerden daha pahalıdır.

Özellik maliyetleri

Kullanılan performans metriğine bağlı olarak ${ displaystyle m}$ , özellik hesaplaması maliyetlerle ilişkilendirilebilir.Örneğin, performans ölçütü olarak çalışma süresini kullanırsak, örnek özelliklerimizi hesaplama süresini bir algoritma seçim sisteminin performansına dahil ederiz.SAT çözümü, bu tür özellik maliyetlerinin olduğu somut bir örnektir. ihmal edilemez, çünkü örnek özellikleri CNF formüller ya çok ucuz (örneğin değişken sayısını elde etmek için DIMAC formatındaki CNF'ler için sabit zamanda yapılabilir) veya çok pahalı (örneğin onlarca veya yüzlerce saniyeye mal olabilen grafik özellikleri) olabilir.

Bu tür senaryolarda pratikte özellik hesaplamasının ek yükünün hesaba katılması önemlidir; aksi takdirde, algoritma seçme yaklaşımının performansına ilişkin yanıltıcı bir izlenim yaratılır. Örneğin hangi algoritmanın seçileceğine karar mükemmel bir doğrulukla verilebiliyorsa, ancak özellikler portföy algoritmalarının çalışma süresiyse portföy yaklaşımının bir faydası yoktur. Özellik maliyetleri çıkarılsaydı bu açık olmazdı.

Yaklaşımlar

Regresyon yaklaşımı

İlk başarılı algoritma seçme yaklaşımlarından biri, her algoritmanın performansını tahmin etti ${ displaystyle { hat {m}} _ { mathcal {A}}: { mathcal {I}} to mathbb {R}}$ ve tahmin edilen en iyi performansa sahip algoritmayı seçti ${ displaystyle arg min _ {{ mathcal {A}} in { mathcal {P}}} { hat {m}} _ { mathcal {A}} (i)}$ bir örnek için ${ displaystyle i}$ .^[3]

Kümeleme yaklaşımı

Yaygın bir varsayım, verilen örnek kümesinin ${ displaystyle { mathcal {I}}}$ homojen alt kümeler halinde kümelenebilir ve bu alt kümelerin her biri için, oradaki tüm örnekler için iyi performans gösteren bir algoritma vardır.Bu nedenle, eğitim, homojen kümelerin denetimsiz bir kümeleme yaklaşımı aracılığıyla tanımlanması ve her kümeyle bir algoritmanın ilişkilendirilmesinden oluşur. yeni örnek bir kümeye atanır ve ilişkili algoritma seçilir.^[7]

Daha modern bir yaklaşım maliyete duyarlıdır hiyerarşik kümeleme^[5] homojen örnek alt kümelerini belirlemek için denetimli öğrenmeyi kullanma.

İkili maliyete duyarlı sınıflandırma yaklaşımı

Çok sınıflı sınıflandırma için yaygın bir yaklaşım, her sınıf çifti (burada algoritmalar) arasındaki ikili modelleri öğrenmek ve ikili modeller tarafından en sık tahmin edilen sınıfı seçmektir. İkili tahmin probleminin örneklerini performans farkıyla ağırlıklandırabiliriz Bu, büyük farklara sahip tahminleri doğru almayı en çok önemsediğimiz gerçeğinden kaynaklanmaktadır, ancak neredeyse hiç performans farkı yoksa yanlış bir tahminin cezası küçüktür. ${ displaystyle i}$ bir sınıflandırma modeli eğitmek için ${ displaystyle { mathcal {A}} _ {1}}$ vs ${ displaystyle { mathcal {A}} _ {2}}$ bir maliyetle ilişkili ${ displaystyle | m ({ mathcal {A}} _ {1}, i) -m ({ mathcal {A}} _ {2}, i) |}$ .^[8]

Gereksinimler

Spearman korelasyon katsayısına göre SAT12-INDU ASlib senaryosundan SAT çözücülerinin kümelenmesi.

SAT12-INDU ASlib Senaryosunda tamamlayıcı analiz için Shapley değerleri^[9]

Algoritma seçim problemi, aşağıdaki varsayımlar altında etkin bir şekilde uygulanabilir:

Portföy ${ displaystyle { mathcal {P}}}$ Algoritmaların sayısı, örnek kümesine göre tamamlayıcıdır ${ displaystyle { mathcal {I}}}$ yani, tek bir algoritma yoktur ${ mathcal {P}}} içinde { displaystyle { mathcal {A}}$ diğer tüm algoritmaların performansına hakim olan ${ displaystyle { mathcal {I}}}$ (tamamlayıcı analize ilişkin örnekler için sağdaki şekillere bakın).
Bazı uygulamalarda, örnek özelliklerinin hesaplanması bir maliyetle ilişkilendirilir. Örneğin, maliyet ölçüsü çalışma süresiyse, örnek özelliklerini hesaplamak için süreyi de dikkate almalıyız. Bu gibi durumlarda, özellikleri hesaplamanın maliyeti, algoritma seçimi yoluyla elde edilen performans kazancından daha büyük olmamalıdır.

Uygulama alanları

Algoritma seçimi tek alanlarla sınırlı değildir, ancak yukarıdaki gereksinimler karşılanırsa her türlü algoritmaya uygulanabilir.

zor kombinatoryal problemler:^[10] OTURDU, Karışık Tamsayı Programlama, CSP, AI Planlama, TSP, MAXSAT, QBF ve Cevap Seti Programlama
kombinatoryal müzayedeler
makine öğreniminde sorun şu şekilde bilinir: meta öğrenme
yazılım Tasarımı
kara kutu optimizasyonu
çok etmenli sistemler
sayısal optimizasyon
doğrusal cebir, diferansiyel denklemler
evrimsel algoritmalar
araç yönlendirme sorunu
güç Sistemleri

Algoritma seçimi hakkında kapsamlı bir literatür listesi için, literatür taramasına bakıyoruz.

Algoritma seçiminin çeşitleri

Çevrimiçi seçim

Çevrimiçi algoritma seçimi, çözme işlemi sırasında farklı algoritmalar arasında geçiş yapmayı ifade eder. Bu bir hiper sezgisel. Bunun tersine, çevrimdışı algoritma seçimi, belirli bir örnek için yalnızca bir kez ve çözme sürecinden önce bir algoritma seçer.

Programların hesaplanması

Algoritma seçiminin bir uzantısı, örnek başına algoritma çizelgeleme problemidir; burada yalnızca bir çözücü seçmiyoruz, ancak her algoritma için her örnek için bir zaman bütçesi seçiyoruz. Bu yaklaşım, özellikle örnek özellikleri çok bilgilendirici değilse ve tek bir çözücünün yanlış seçilmesi muhtemelse, seçim sistemlerinin performansını iyileştirir.^[11]

Paralel portföylerin seçimi

Paralel hesaplamanın artan önemi göz önüne alındığında, paralel hesaplama için algoritma seçiminin bir uzantısı paralel portföy seçimidir, burada paralel bir portföyde eşzamanlı olarak çalıştırmak için algoritmaların bir alt kümesini seçeriz.^[12]

Dış bağlantılar

Referanslar

^ Pirinç, John R. (1976). "Algoritma Seçimi Problemi". Bilgisayarlardaki Gelişmeler. 15. s. 65–118. doi:10.1016 / S0065-2458 (08) 60520-3. ISBN 9780120121151.
^ Bischl, Bernd; Kerschke, Pascal; Kotthoff, Lars; Lindauer, Marius; Malitsky, Yuri; Fréchette, Alexandre; Hoos, Holger; Hutter, Frank; Leyton-Brown, Kevin; Tierney, Kevin; Vanschoren, Joaquin (2016). "ASlib: Algoritma seçimi için bir kıyaslama kitaplığı". Yapay zeka. 237: 41–58. arXiv:1506.02465. doi:10.1016 / j.artint.2016.04.003.
^ ^a ^b L. Xu; F. Hutter; H. Hoos ve K. Leyton-Brown (2008). "SATzilla: SAT için Portfolyo Tabanlı Algoritma Seçimi". Yapay Zeka Araştırmaları Dergisi. 32: 565–606. arXiv:1111.2249. doi:10.1613 / jair.2490.
^ S. Kadıoğlu; Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2011). "Algoritma Seçimi ve Çizelgeleme". Lee, J. (ed.). Kısıt Programlama İlkeleri ve Uygulaması. Bilgisayar Bilimlerinde Ders Notları. 6876. s. 454–469. CiteSeerX 10.1.1.211.1807. doi:10.1007/978-3-642-23786-7_35. ISBN 978-3-642-23785-0.
^ ^a ^b Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2013). "Maliyete Duyarlı Hiyerarşik Kümelemeye Dayalı Algoritma Portföyleri". Yirmi Üçüncü Uluslararası Yapay Zeka Ortak Konferansı Bildirileri. s. 608–614. ISBN 978-1-57735-633-2.
^ E. Nudelman; K. Leyton-Brown; H. Hoos; A. Devkar; Y. Shoham (2004). "Rastgele SAT'ı Anlamak: Maddelerin Değişkenlere Oranının Ötesinde" (PDF). CP Takibi.
^ S. Kadıoğlu; Y. Malitsky; M. Sellmann; K. Tierney (2010). "ISAC - Örneğe Özgü Algoritma Yapılandırması" (PDF). Avrupa Yapay Zeka Konferansı Bildirileri.
^ L. Xu; F. Hutter; J. Shen; H. Hoos; K. Leyton-Brown (2012). "SATzilla2012: Maliyete Duyarlı Sınıflandırma Modellerine Dayalı Geliştirilmiş Algoritma Seçimi" (PDF). SAT Challenge 2012 Bildirileri: Çözücü ve Kıyaslama Açıklamaları.
^ A. Frechette; L. Kotthoff; T. Michalak; T. Rahwan; H. Hoos ve K. Leyton-Brown (2016). "Algoritma Portföylerini Analiz Etmek İçin Shapley Değerini Kullanma". AAAI Uluslararası Konferansı Bildirileri.
^ Kotthoff, Lars. "Kombinasyonel arama problemleri için algoritma seçimi: Bir anket. "Veri Madenciliği ve Kısıt Programlama. Springer, Cham, 2016. 149-190.
^ M. Lindauer; R. Bergdoll; F. Hutter (2016). "Örnek Başına Algoritma Planlamasının Ampirik Bir Çalışması" (PDF). Uluslararası Öğrenme ve Akıllı Optimizasyon Konferansı Bildirileri. Bilgisayar Bilimlerinde Ders Notları. 10079: 253–259. doi:10.1007/978-3-319-50349-3_20. ISBN 978-3-319-50348-6.
^ M. Lindauer; H. Hoos ve F. Hutter (2015). "Sıralı Algoritma Seçiminden Paralel Portföy Seçimine" (PDF). Uluslararası Öğrenme ve Akıllı Optimizasyon Konferansı Bildirileri. Bilgisayar Bilimlerinde Ders Notları. 8994: 1–16. doi:10.1007/978-3-319-19084-6_1. ISBN 978-3-319-19083-9.

[1] Pirinç, John R. (1976). "Algoritma Seçimi Problemi". Bilgisayarlardaki Gelişmeler. 15. s. 65–118. doi:10.1016 / S0065-2458 (08) 60520-3. ISBN 9780120121151.

[2] Bischl, Bernd; Kerschke, Pascal; Kotthoff, Lars; Lindauer, Marius; Malitsky, Yuri; Fréchette, Alexandre; Hoos, Holger; Hutter, Frank; Leyton-Brown, Kevin; Tierney, Kevin; Vanschoren, Joaquin (2016). "ASlib: Algoritma seçimi için bir kıyaslama kitaplığı". Yapay zeka. 237: 41–58. arXiv:1506.02465. doi:10.1016 / j.artint.2016.04.003.

[zilla08-3] L. Xu; F. Hutter; H. Hoos ve K. Leyton-Brown (2008). "SATzilla: SAT için Portfolyo Tabanlı Algoritma Seçimi". Yapay Zeka Araştırmaları Dergisi. 32: 565–606. arXiv:1111.2249. doi:10.1613 / jair.2490.

[4] S. Kadıoğlu; Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2011). "Algoritma Seçimi ve Çizelgeleme". Lee, J. (ed.). Kısıt Programlama İlkeleri ve Uygulaması. Bilgisayar Bilimlerinde Ders Notları. 6876. s. 454–469. CiteSeerX 10.1.1.211.1807. doi:10.1007/978-3-642-23786-7_35. ISBN 978-3-642-23785-0.

[CSHC-5] Y. Malitsky; A. Sabharwal; H. Samulowitz; M. Sellmann (2013). "Maliyete Duyarlı Hiyerarşik Kümelemeye Dayalı Algoritma Portföyleri". Yirmi Üçüncü Uluslararası Yapay Zeka Ortak Konferansı Bildirileri. s. 608–614. ISBN 978-1-57735-633-2.

[6] E. Nudelman; K. Leyton-Brown; H. Hoos; A. Devkar; Y. Shoham (2004). "Rastgele SAT'ı Anlamak: Maddelerin Değişkenlere Oranının Ötesinde" (PDF). CP Takibi.

[7] S. Kadıoğlu; Y. Malitsky; M. Sellmann; K. Tierney (2010). "ISAC - Örneğe Özgü Algoritma Yapılandırması" (PDF). Avrupa Yapay Zeka Konferansı Bildirileri.

[8] L. Xu; F. Hutter; J. Shen; H. Hoos; K. Leyton-Brown (2012). "SATzilla2012: Maliyete Duyarlı Sınıflandırma Modellerine Dayalı Geliştirilmiş Algoritma Seçimi" (PDF). SAT Challenge 2012 Bildirileri: Çözücü ve Kıyaslama Açıklamaları.

[9] A. Frechette; L. Kotthoff; T. Michalak; T. Rahwan; H. Hoos ve K. Leyton-Brown (2016). "Algoritma Portföylerini Analiz Etmek İçin Shapley Değerini Kullanma". AAAI Uluslararası Konferansı Bildirileri.

[10] Kotthoff, Lars. "Kombinasyonel arama problemleri için algoritma seçimi: Bir anket. "Veri Madenciliği ve Kısıt Programlama. Springer, Cham, 2016. 149-190.

[11] M. Lindauer; R. Bergdoll; F. Hutter (2016). "Örnek Başına Algoritma Planlamasının Ampirik Bir Çalışması" (PDF). Uluslararası Öğrenme ve Akıllı Optimizasyon Konferansı Bildirileri. Bilgisayar Bilimlerinde Ders Notları. 10079: 253–259. doi:10.1007/978-3-319-50349-3_20. ISBN 978-3-319-50348-6.

[12] M. Lindauer; H. Hoos ve F. Hutter (2015). "Sıralı Algoritma Seçiminden Paralel Portföy Seçimine" (PDF). Uluslararası Öğrenme ve Akıllı Optimizasyon Konferansı Bildirileri. Bilgisayar Bilimlerinde Ders Notları. 8994: 1–16. doi:10.1007/978-3-319-19084-6_1. ISBN 978-3-319-19083-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]