Probably Approximately Correct [BLOCK_TYPE CONTENT classical_pac/pac_basics_content]
Valiant-ის კითხვა (1984)
[BLOCK_TYPE CONTENT classical_pac/pac_basics_content]Leslie Valiant-მა დასვა მოჩვენებითად მარტივი კითხვა: რას ნიშნავს მანქანისთვის სწავლა? არა „შეუძლია მას დამახსოვრება?“ არა „შეუძლია მას იდეალურად წინასწარმეტყველება?“ ამის ნაცვლად: შეუძლია მას დაახლოებით კარგად სწავლა, მაღალი ალბათობით, სასრული ნიმუშიდან, პოლინომიურ დროში? [BLOCK_TYPE CONTENT classical_pac/pac_basics_content]
[BLOCK_TYPE CONTENT classical_pac/pac_basics_content]
ამ ჩარჩომ მას მოუტანა Turing-ის პრემია 2010 წელს და დააფუძნა გამოთვლითი სწავლის თეორია.
ორი სახელური
ε (ეპსილონი) — შეცდომის დასაშვები ზღვარი. დაახლოებით სწორი ნიშნავს, რომ შეცდომა ≤ ε. მცირე ε = უფრო მკაცრი სწავლება.
δ (დელტა) — ნდობის პარამეტრი. ალბათობით ნიშნავს წარმატების ალბათობას ≥ 1 − δ. მცირე δ = უფრო მაღალი ნდობაა საჭირო.
განმარტება
კონცეპტების კლასი C ითვლება PAC-სასწავლად, თუ არსებობს ალგორითმი, რომელიც ნებისმიერი განაწილების D და ნებისმიერი სამიზნე კონცეპტის c ∈ C-სთვის, m მაგალითის მიღების შემდეგ (რომლებიც გამოყვანილია D-დან და მონიშნულია c-ით), აბრუნებს ჰიპოთეზას h, რომელიც აკმაყოფილებს:
P[error(h) ≤ ε] ≥ 1 − δ
სადაც m პოლინომიურია 1/ε, 1/δ და კონცეპტის ზომის მიმართ.
In English: feed it enough examples & it gets close enough often enough, & 'enough' doesn't blow up exponentially.
სასრული ჰიპოთეზების სივრცის ნიმუშის სირთულე
თუ ჩვენი ჰიპოთეზების სივრცე H შეიცავს სასრულ რაოდენობას კანდიდატ ჰიპოთეზებს, კლასიკური ანალიზი გვაძლევს:
m ≥ (1/ε)(ln|H| + ln(1/δ))
წაიკითხეთ ეს ფორმულა როგორც ბიუჯეტი. ε-ს განახევრება ორჯერ ზრდის საჭირო ნიმუშების რაოდენობას. δ-ს განახევრება ამატებს მუდმივას. |H|-ს გაორმაგება ამატებს ln(2) ნიმუშს — ლოგარითმული მასშტაბირება, ლამაზად მოთვინიერებული ზრდა.
ჰიპოთეზის კლასისთვის ნიმუშის ზომის განსაზღვრა
სპამ-ფილტრი ირჩევს |H| = 1,000,000 კანდიდატი წესების სიმრავლეს შორის. გვინდა შეცდომა ε ≤ 0.05, ნდობით 1 − δ = 0.99 (ამიტომ δ = 0.01).
შატერირება და VC განზომილება
როდესაც ჰიპოთეზების სივრცე უსასრულო ხდება
ზღვარი m ≥ (1/ε)(ln|H| + ln(1/δ)) იშლება, როდესაც |H| = ∞. სასარგებლო ჰიპოთეზების კლასების უმეტესობა (ხაზოვანი კლასიფიკატორები ℝᵈ-ში, გადაწყვეტილების ხეები, ნერვული ქსელები) შეიცავს უსასრულო რაოდენობის კანდიდატებს. ვაპნიკმა და ჩერვონენკისმა ამ პრობლემას გამოსავალი მოუძებნეს დაახლოებით 1971 წელს უფრო მდიდარი სირთულის საზომით: VC განზომილება.
შატერინგი
ჰიპოთეზების კლასი H შატერინგს ახდენს n წერტილის სიმრავლეზე, თუ H-ს შეუძლია ამ n წერტილის ყველა შესაძლო მარკირების წარმოქმნა (ყველა 2ⁿ დიქოტომია). ხაზოვან კლასიფიკატორებს ℝ²-ში შეუძლიათ შატერინგი ნებისმიერი 3 წერტილისთვის ზოგად მდგომარეობაში: ამ 3 წერტილის 8 შესაძლო +/− მარკირებიდან თითოეულისთვის არსებობს ხაზი, რომელიც მათ სწორად ჰყოფს.
მაგრამ წრფივ კლასიფიკატორებს ℝ²-ში არ შეუძლიათ დაამსხვრიონ 4 წერტილი XOR კონფიგურაციაში. არცერთი სწორი ხაზი არ ჰყოფს დიაგონალურ წყვილს ანტი-დიაგონალური წყვილისგან.
VC განზომილება
VC(H) = უდიდესი n, რომლისთვისაც H ანადგურებს n-წერტილიან სიმრავლეს. 2D წრფივი კლასიფიკატორებისთვის: VC = 3. 2D-ში ღერძულად გასწორებული მართკუთხედებისთვის: VC = 4. W წონის მქონე ნერვული ქსელებისთვის: VC ≤ O(W² log W) (Bartlett & Anthony 1999).
შერჩევის სირთულე VC განზომილების მიხედვით
ჩაანაცვლეთ ln|H| ჩვენს PAC საზღვარში VC განზომილებით d:
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))
VC dimension მოქმედებს როგორც უსასრულო კლასის „ეფექტური სირთულე“. დაბალი VC dimension-ის მქონე ჰიპოთეზების კლასი განზოგადდება მცირე რაოდენობის მაგალითებიდან; მაღალი VC dimension-ის მქონე კლასი კი მეტ მონაცემს მოითხოვს.
VC Dimension როგორც ეფექტური ჰიპოთეზების რაოდენობა
ნერვულ ქსელს აქვს W = 10⁹ წონა. Bartlett-Anthony-ის შეფასებით, VC ≤ O(W² log W). დაახლოებით VC ≈ W² log₂ W.
რეალიზებადობის მოხსნა, ჰიპოთეზების პოსტერიორები
ორი მნიშვნელოვანი განზოგადება
კლასიკური PAC ვარაუდობს, რომ ჩვენი სამიზნე კონცეფცია c მდებარეობს ჩვენს ჰიპოთეზების კლასში H. რეალური მონაცემები შეიცავს ხმაურს, არასწორ ეტიკეტებს და კონცეფციებს, რომლებსაც ჩვენი კლასი ვერ წარმოადგენს. ამის მოსაგვარებლად არსებობს ორი გაფართოება.
აგნოსტიკური PAC
მოვიშოროთ ჩვენი ვარაუდი, რომ c ∈ H. ახლა ვეჯიბრებით კლასში საუკეთესო ჰიპოთეზას h* = argmin_{h ∈ H} risk(h). შეზღუდვის ფორმა იცვლება: იდეალურის ნაცვლად, ვუახლოვდებით H-ში საუკეთესო შესაძლო რისკს.
აგნოსტიკური შეზღუდვა: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ ნიმუშების რაოდენობით m = O(1/ε² × (VC(H) + log(1/δ))). აღნიშნეთ ε² ε-ის ნაცვლად მნიშვნელში: აგნოსტიკური სწავლისთვის იგივე სიზუსტის მისაღწევად მეტი ნიმუშია საჭირო.
PAC-Bayes (McAllester 1999)
ერთი ჰიპოთეზის არჩევიდან გადავდივართ ჰიპოთეზების განაწილების არჩევაზე. ვიწყებთ წინასწარ განაწილებით P. ვაკვირდებით მონაცემებს. ვიღებთ უკანა განაწილებას Q. PAC-Bayes შეზღუდავს მოსალოდნელ რისკს Q-ს ქვეშ:
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P) ზომავს, რამდენად შორს გადავიდა ჩვენი posterior ჩვენი prior-დან. ორი ინტერპრეტაცია:
1. შეკუმშვის ხედვა. Posterior, რომელიც ახლოსაა თავის prior-თან (მცირე KL), კარგად განზოგადდება — მცირე ინფორმაციული ღირებულება = მცირე განზოგადების ხარვეზი.
2. ბაიესური ხედვა. ძლიერი prior + სუსტი მონაცემთა განახლება = მჭიდრო საზღვარი; სუსტი prior + მძიმე მონაცემთა განახლება = უფრო ფართო საზღვარი.
რატომ არის PAC-Bayes მნიშვნელოვანი. ემპირიული PAC-Bayes საზღვრები (Catoni 2007, Dziugaite & Roy 2017) იძლევა რიცხვობრივად მნიშვნელოვან განზოგადების გარანტიებს რეალურ ნერვულ ქსელებზე, სადაც კლასიკური PAC საზღვრები ვაკუალურია. ისინი რჩებიან ჩვენს ყველაზე მჭიდრო თეორიულ ინსტრუმენტად ზედმეტად პარამეტრიზებული განზოგადებისთვის.
PAC-Bayes შეზღუდვის წაკითხვა
დავუშვათ, რომ ვწვრთნით ქსელს n = 50,000 მონიშნულ მაგალითზე. ვარჯიშის შემდეგ, ჩვენი პოსტერიორი Q წონებზე აქვს KL(Q‖P) = 200 ნატი გაუსის წინასწარი P-ის მიმართ. Q-ს ემპირიული რისკი არის 0.10. დავაყენოთ δ = 0.05.
ჭარბი პარამეტრიზაცია და ორმაგი დაღმართი
კლასიკური PAC-ის პროგნოზირებული კატასტროფა
კლასიკური PAC პროგნოზირებს: პარამეტრების რაოდენობა უფრო მეტია ვიდრე სემპლები = კატასტროფული გადაჭარბებული მორგება. სრულყოფილად სწავლობს სასწავლო მონაცემებზე, ტესტის მონაცემებზე კი შემთხვევით განზოგადებს. VC-ის საზღვარი პროგნოზირებს დამახსოვრებას სწავლის გარეშე.
თანამედროვე ნერვული ქსელები ჩვეულებრივ 10×-დან 1000×-მდე მეტ პარამეტრს შეიცავენ, ვიდრე სასწავლო სემპლებია, და მაინც კარგად განზოგადებენ. კლასიკური თეორიის მიხედვით ეს არ უნდა მომხდარიყო. მაგრამ მაინც ხდება.
U-მრუდი, რომელიც გვასწავლეს
კლასიკური bias-variance: მოდელის ტევადობის ზრდასთან ერთად სასწავლო შეცდომა მუდმივად მცირდება; ტესტის შეცდომა ჯერ მცირდება (ნაკლები underfit), აღწევს მინიმუმს, შემდეგ კი იზრდება (overfit). U-ფორმა, რომელსაც VC თეორია პროგნოზირებს.
რა ხდება სინამდვილეში — Double Descent
Belkin et al (2019) აჩვენეს, რომ ტესტის შეცდომა მიჰყვება კლასიკურ U-მრუდს ინტერპოლაციის ზღვრამდე (ტევადობა = ნიმუშების რაოდენობა), შემდეგ კი კვლავ ეცემა ამ ზღვრის მიღმა. მასიურად ზედმეტად პარამეტრიზებული მოდელები განაზოგადებენ უკეთესად, ვიდრე უბრალოდ საკმარისად დიდი მოდელები.
რატომ ვერ ხედავს კლასიკური PAC ეს
1. განაწილებისგან თავისუფალი დაშვება ზედმეტად პესიმისტურია. რეალურ მონაცემებს აქვს სტრუქტურა (დაბალი შინაგანი განზომილება, მანიფოლდის გეომეტრია). PAC საზღვრები მოქმედებს ყველაზე ცუდი შემთხვევის განაწილებებზე; რეალური განაწილებები იყენებენ სტრუქტურას, რომელსაც ასევე იყენებს SGD.
2. იმპლიციტური რეგულარიზაცია. SGD ზედმეტად პარამეტრიზებულ ქსელებზე პოულობს მინიმალურ-ნორმის ან მინიმალური სირთულის ინტერპოლირებულ გადაწყვეტებს, არა თვითნებურებს. კლასიკური თეორია ვარაუდობს ყველაზე ცუდ შემთხვევას ემპირიული რისკის მინიმიზატორისთვის; რეალური ალგორითმები ირჩევენ კეთილგანწყობილ გადაწყვეტებს.
3. ჰიპოთეზის კლასის განსაზღვრება არასწორია. SGD-ით შესწავლილი ეფექტური ჰიპოთეზის კლასი ბევრად უფრო მცირეა, ვიდრე ნომინალური წონების სივრცე. PAC-Bayes-ის პოსტერიორები ამას ასახავენ; VC განზომილება — არა.
თანამედროვე თეორიული მუშაობა (Bartlett, Long, Lugosi, Tsigler 2020 benign overfitting-ზე; Nakkiran et al 2020 double descent-ზე) ქმნის პოსტ-PAC განზოგადების თეორიას, რომელიც ითვალისწინებს ჩვენს ზედმეტად პარამეტრიზებულ რეჟიმს.
კლასიკური PAC-ის წარუმატებლობის დიაგნოსტიკა
კვლევითი ჯგუფი ავარჯიშებს 1 მილიარდ პარამეტრიან ქსელს 100 000 მონიშნულ მაგალითზე. კლასიკური PAC პროგნოზირებს ვაკუუმურ საზღვრებს. ემპირიულად, ტესტის სიზუსტე აღწევს 95%-ს.
Kaplan, Chinchilla და ავტომატური ზოგადი ინტელექტის ზომა [BLOCK_TYPE SECTION/STEP]
საზღვრებიდან ემპირიულ მასშტაბირების კანონებამდე
[BLOCK_TYPE SECTION/STEP]კლასიკური PAC თეორიულად პროგნოზირებს მონაცემთა ზომას და ცარიელი რჩება. ემპირიული მასშტაბირების კანონები მონაცემთა ზომას დაკვირვებიდან პროგნოზირებს და რეალურად მუშაობს. მათ შეცვალეს PAC ჩვენი პრაქტიკული ზომის განსაზღვრის ინსტრუმენტი დიდი მოდელებისთვის. [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE scaling_data_wall/scaling_content]
Kaplan et al (2020)
[BLOCK_TYPE scaling_data_wall/scaling_content]დანაკარგი მიჰყვება ძალის კანონს პარამეტრების N, მონაცემთა ტოკენების D და გამოთვლითი რესურსის C მიხედვით: [BLOCK_TYPE scaling_data_wall/scaling_content]
[BLOCK_TYPE scaling_data_wall/scaling_content]
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC [BLOCK_TYPE scaling_data_wall/scaling_content]
[BLOCK_TYPE scaling_data_wall/scaling_content]
პარამეტრების გაორმაგება ამცირებს დანაკარგს ფიქსირებული მულტიპლიკაციური ფაქტორით. მონაცემების გაორმაგება ამცირებს დანაკარგს სხვა ფიქსირებული ფაქტორით. ეს ექსპონენტები (αN, αD, αC) ზომავენ და პროგნოზირებენ frontier ქცევას მრავალი რიგის სიდიდეზე. [BLOCK_TYPE scaling_data_wall/scaling_content]
Hoffmann et al 2022 (Chinchilla)
Chinchilla-მ აჩვენა, რომ Kaplan-ის ექსპონენტები პარამეტრებს მონაცემებთან შედარებით ზედმეტად ანიჭებდა წონას. გამოთვლით-ოპტიმალური ტრენინგი მოითხოვს დაახლოებით 20 ტოკენს თითო პარამეტრზე:
D_opt ≈ 20 × N
GPT-3 (175B პარამეტრი) გაწვრთნილი იყო ~300B ტოკენზე — Chinchilla-ს გამოთვლებით მნიშვნელოვნად არასაკმარისად გაწვრთნილი. გამოთვლით-ოპტიმალურ 175B-პარამეტრიან მოდელს სჭირდება ~3.5 ტრილიონი ტოკენი.
The Data Wall
ჩვენი პარამეტრების რაოდენობის მასშტაბირება მოითხოვს ტოკენების რაოდენობის პროპორციულ მასშტაბირებას. საჯარო ვებ-კროული იძლევა დაახლოებით ~10¹³ სასარგებლო ტოკენს. ჰიპოთეტური 10¹⁵-პარამეტრიანი ავტომატიზებული ზოგადი ინტელექტი მოითხოვდა დაახლოებით ~2×10¹⁶ ტოკენს — სამი რიგით მეტი, ვიდრე ხელმისაწვდომი ვებ-მონაცემები.
ეს არის ჩვენი მონაცემთა კედელი. მასშტაბირების კანონები პროგნოზირებენ, რომ კორპუსის დეფიციტს შევხვდებით გამოთვლითი რესურსების დეფიციტამდე დიდი ხნით ადრე. სინთეტური მონაცემები, მულტიმოდალური კორპუსები (ვიდეო, აუდიო, სენსორული ნაკადები) და RL-გარემოდან მიზნად ისახავს ამ კედლის გადალახვას.
კლასიკური PAC გვეუბნებოდა (არასწორად), რომ გვჭირდებოდა 10²¹ ნიმუში. მასშტაბირების კანონები გვეუბნება (რეალობასთან კალიბრირებული), რომ გვჭირდება 2×10¹⁶. ორივე რიცხვი აღემატება ხელმისაწვდომ ტექსტს. დღეს ფრონტიერის მუშაობა ამ ხარვეზის შევსებას ებრძვის.
ავტომატიზებული ზოგადი ინტელექტის კორპუსის შეფასება
დავუშვათ, რომ ფრონტიერის ლაბორატორია გვთავაზობს 10¹⁴-პარამეტრიან მოდელს და ამტკიცებს, რომ ის მიაღწევს ავტომატიზებულ ზოგად ინტელექტს. ჩვენ გვინდა, რომ მისი სასწავლო კორპუსის ზომა განვსაზღვროთ Chinchilla-ს წესის მიხედვით.
თეორიული საზღვრებიდან წარმოების გაზომვებამდე
შეწყვიტეთ საზღვრების გამოთვლა; დაიწყეთ მათი გაზომვა
კლასიკური PAC საზღვრები ვაკუუმურია. PAC-Bayes საზღვრები მჭიდროა, მაგრამ დაშვებები ძნელად დასამოწმებელია. პრაქტიკული ალტერნატივა: გაზომეთ ε ემპირიულად თქვენს რეალურ განაწილებაზე და განაახლეთ ის სისტემის მუშაობისას.
იდეა 1 — გაშუქების გაკეთება როგორც ემპირიული PAC
სამიზნე make coverage გადაატარებს N შეკავებულ კითხვას თქვენს მოთხოვნის სისტემაში და გაზომავს ორ მაჩვენებელს:
- cache_hit_rate — წილი, რომელზეც თქვენმა სისტემამ იპოვა ცნობილი პასუხი
- i_dont_know_rate — წილი, რომელზეც თქვენმა სისტემამ პატიოსნად თქვა უარი
თითოეული გაზომვა = ბერნულის ცდა. დაკვირვებული რაოდენობებიდან გამოითვლება Wilson-ის ნდობის ინტერვალი ჭეშმარიტი მაჩვენებლისთვის. მაგალითი: N = 1000 მოთხოვნა, დაკვირვებული i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]. ზედა ზღვარი 0.226 ზუსტად იქცევა როგორც PAC ε δ = 0.05-ზე, რომელიც მიღებულია რეალური მონაცემებიდან რეალურ განაწილებაზე და არა ყველაზე უარესი შემთხვევის თეორიული ანალიზიდან.
კლასიკური PAC ლექსიკა გამოიყენება (ε, δ, ნდობა). განსხვავებული მექანიზმი (ბინომიალური კონცენტრაცია vs. VC თეორია). უფრო მკაცრი შედეგი, რადგან რეალური განაწილებები შეიცავს გამოსაყენებელ სტრუქტურას.
იდეა 2 — PAC-Bayes აუდიტი ფალსიფიკაციის მოვლენების მეშვეობით
თითოეული ფალსიფიკაცია (სისტემის პასუხი, რომელიც აშკარად არასწორია) განიხილება როგორც მტკიცებულება, რომელიც აახლებს პოსტერიორს ჭეშმარიტი შეცდომის მაჩვენებლის ε-სთვის:
1. აპრიორი: ε ~ Beta(α₀, β₀). აირჩიეთ სუსტი აპრიორი, მაგ. Beta(1, 1) = ერთგვაროვანი.
2. თითოეული მოთხოვნა იძლევა ბერნულის შედეგს: გაყალბებული (1) ან შენარჩუნებული (0).
3. აპოსტერიორი k გაყალბების შემდეგ n მოთხოვნაში: Beta(α₀ + k, β₀ + n − k).
4. აპოსტერიორის საშუალო: (α₀ + k) / (α₀ + β₀ + n) → ემპირიული გაყალბების მაჩვენებელი როცა n → ∞.
5. 95% სარწმუნო ინტერვალი ε-ზე მჭიდროვდება როგორც 1/√n.
რას გვაძლევს ეს
- რეალური სამყაროს ε₀ შეფასება ფაქტობრივი განლაგებიდან, არა ყველაზე ცუდი შემთხვევის თეორიიდან
- ნებისმიერ დროს მოქმედი სიგნალიზაცია: როდესაც პოსტერიორული სანდო ინტერვალი კვეთს კონტრაქტის ზღვარს, გვერდი ვინმეს [BLOCK_TYPE production_audit/audit_content]
- მონოტონური ნდობა: მეტი მოთხოვნის დაკვირვება → უფრო ვიწრო CI → უფრო ძლიერი გარანტია [BLOCK_TYPE production_audit/audit_content]
[BLOCK_TYPE production_audit/audit_content]
დაკავშირებული ტექნიკები: კონფორმული პროგნოზირება ონლაინ რეკალიბრაციით (Vovk), თანმიმდევრული ალბათობის თანაფარდობის ტესტები (Wald), ონლაინ PAC-Bayes (Haddouche & Guedj 2022). იგივე ოჯახი, სხვადასხვა მათემატიკური მექანიზმი.
Beta პოსტერიორის გამოთვლა ფალსიფიკაციებზე
ჩვენი გუნდი აწარმოებს დაფარვის აუდიტს წარმოების მოთხოვნის სისტემაზე. წინასწარი განაწილება ჭეშმარიტი შეცდომის მაჩვენებელზე ε: Beta(1, 1) (ერთგვაროვანი). 200 დამალულ მოთხოვნაზე დავაკვირდით 8 ფალსიფიკაციას.