सीखने के समूह

हम संगणकीय शिक्षण सिद्धांत में एक मौलिक समस्या पर विचार करते हैं: एक मनमाना बूलियन फ़ंक्शन सीखना जो अज्ञात सेट पर निर्भर करता है जिसमें n बूलियन चर में से k होते हैं। हम ऐसे फ़ंक्शंस को समान यादृच्छिक उदाहरणों से सीखने के लिए एक एल्गोरिदम देते हैं, जो लगभग (nk)ω/(ω + 1) समय में चलता है, जहाँ ω < 2.376 मैट्रिक्स गुणन का गुणांक है। इस प्रकार, हम उसी समय सीमा पर पहले बहुपद गुणन सुधार को प्राप्त करते हैं जो थकाऊ खोज के माध्यम से प्राप्त किया जा सकता है। हमारा एल्गोरिदम और विश्लेषण बूलियन फ़ंक्शंस की नई संरचनात्मक विशेषताओं का उपयोग करते हैं।