Taklit Ederek Agnostik Öğrenme

Özetle: Bir makine öğrenimi modelleri sınıfı ve ikili etiketlerle bir veri dağıtımına örnek erişim göz önüne alındığında, hangi hesaplama görevi daha zordur: pozitif ve negatif etiketleri ve sınıfın en iyi üyesini ayıran ayırt …

Özet

Bir makine öğrenimi modelleri sınıfı ve ikili etiketlerle bir veri dağıtımına örnek erişim göz önüne alındığında, hangi hesaplama görevi daha zordur: pozitif ve negatif etiketleri ve sınıfın en iyi üyesini ayıran ayırt edici bir modelin eğitimi mi, yoksa çıktıları sınıfın tüm üyeleri tarafından gerçek verilerden ayırt edilemeyen üretken bir modelin eğitimi mi? Hesaplamalı öğrenme teorisindeki bu iki temel görevin sadece yakından ilişkili olmadığını, aynı zamanda karmaşıklık açısından birbirine eşdeğer olduğunu kanıtlıyoruz. Bu eşdeğerliğin bir yönü daha önce biliniyordu. Aslında, karmaşıklık teorisindeki güçlü düzenlilik lemması, algoritmaları güçlendirme tarzında ayırt edilemezlik görevinden (diğer adıyla çoklu doğruluk) ayırt edici göreve (a.k.a. agnostik öğrenme) etkili bir kehanet indirgemesi sağlar. Ana katkımız diğer yönde etkili bir kehanet azaltımıdır. Bu fikri daha da ileri götürerek, çok-doğruluklu bir kehanetin dikkat çekici derecede güçlü bir ilkel olduğunu, sadece agnostik öğrenmeyi değil, aynı zamanda benzer verimli ve doğrudan yapılar yoluyla görünüşte daha zorlu öğrenme hedeflerini de gerçekleştirdiğini gösteriyoruz. Sonuçlarımız, kehanete uyarlanabilir sorgular yapmanın gücünü önemli ölçüde kullanıyor ve tek bir çok doğru tahmin edicinin sonradan işlenmesinin zayıf öğrenme biçimleri için bile yetersiz olduğunu gösteren önceki çalışmayla tam bir tezat oluşturuyor. Teknik düzeyde, (çevrimdışı) problemimiz ile çevrimiçi ortamda pişmanlık duymayan öğrenmenin bir versiyonu arasında bir bağlantı kuruyoruz; bu, etiket dağıtımını değiştirmek ve çok doğruluklu kehanetin tahminlerini bir araya getirmek için lideri takip eden türden algoritmalar kullanmamıza olanak tanıyor.

Orijinal Özet (İngilizce)

Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive and negative labels as well as the best member of the class, or training a generative model whose outputs are indistinguishable from real data by all members of the class? We prove that these two fundamental tasks in computational learning theory are not just closely related, but actually equivalent to each other in complexity. One direction of this equivalence was previously known. Indeed, the powerful regularity lemma in complexity theory gives an efficient oracle reduction from the indistinguishability task (a.k.a. multiaccuracy) to the distinguishing task (a.k.a. agnostic learning) in the style of boosting algorithms. Our main contribution is an efficient oracle reduction in the other direction. Taking this idea further, we show that a multiaccuracy oracle is a remarkably powerful primitive, achieving not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions. Our results crucially use the power of making adaptive queries to the oracle, and stand in stark contrast to prior work, which showed that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning. On a technical level, we draw a connection between our (offline) problem and a version of no-regret learning in the online setting, which allows us to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.

Kaynak: arXiv:2611.05346 · PDF