# Uczenie PAC i wymiar VC

EN: **PAC learning and VC dimension** · id `pacvc` · aliases: PAC learning, probably approximately correct learning, uczenie PAC, VC dimension, wymiar VC, wymiar Vapnika-Czerwonenkisa

Path: [AI Atlas](https://aiatlasgraph.com/llms.txt) › [Fundamenty i rozumowanie](https://aiatlasgraph.com/t/foundations.md) › [Teoria uczenia statystycznego](https://aiatlasgraph.com/t/learningtheory.md) › Uczenie PAC i wymiar VC

## Description

- PL: Formalny model uczalności: z prawdopodobieństwem co najmniej 1−δ błąd hipotezy ≤ ε, przy liczbie próbek zależnej od wymiaru VC klasy.
- EN: Formal learnability model: with probability at least 1−δ the hypothesis error is ≤ ε, with sample size depending on the class's VC dimension.

## In one sentence

- PL: Sposób, by policzyć, ile przykładów potrzeba, żeby model z dużym prawdopodobieństwem mylił się tylko trochę.
- EN: A way to count how many examples are needed so a model is, with high probability, only slightly wrong.

## Problem it solves

- PL: Trudno ocenić z góry, czy zebrane dane wystarczą do nauczenia zadania, czy model tylko zapamięta przypadkowe szczegóły.
- EN: It is hard to judge in advance whether collected data suffices to learn a task or whether the model will memorise accidental details.

## What it does

- PL: Mierzy, ile różnych podziałów danych model potrafi odtworzyć; im bardziej giętki model, tym więcej przykładów musi zobaczyć.
- EN: It measures how many different splits of data a model can reproduce; the more flexible the model, the more examples it must see.

## Everyday example

- PL: Przed zbieraniem danych do wykrywania wadliwych części ktoś szacuje, że prosty model wystarczy na mniejszej próbce niż bardzo rozbudowany.
- EN: Before collecting data to spot faulty parts, someone estimates that a simple model will do with a smaller sample than a very elaborate one.

## This concerns you if you…

- PL: planujesz, ile danych zebrać do modelu
- PL: chcesz zrozumieć, czym grozi zbyt złożony model
- EN: plan how much data to collect for a model
- EN: want to understand the risk of an overly complex model

## Keywords

PAC learnability · VC dimension · sample complexity · shattering · agnostic PAC · uniform convergence · fundamental theorem of PAC learning · Rademacher complexity

## How it works

- PL: W klasyfikacji binarnej klasa jest uczalna w sensie PAC, gdy istnieje algorytm, który dla dowolnego rozkładu i wystarczającej liczby próbek i.i.d. zwraca hipotezę o błędzie ≤ ε z prawdopodobieństwem ≥ 1−δ. Wymiar VC to rozmiar największego zbioru punktów, który klasa potrafi rozbić na wszystkie sposoby; w tym ustawieniu skończony wymiar VC charakteryzuje uczalność PAC i agnostyczną uczalność PAC.
- EN: In binary classification, a class is PAC learnable when some algorithm, for any distribution and enough i.i.d. samples, returns a hypothesis with error ≤ ε with probability ≥ 1−δ. VC dimension is the size of the largest point set the class can shatter; in this setting finite VC dimension characterises PAC and agnostic PAC learnability.

## Limits

- PL: Ograniczenia są najgorszego przypadku i dla głębokich sieci o milionach parametrów dają liczby bez praktycznego znaczenia. Nie uwzględniają cech konkretnego rozkładu ani algorytmu optymalizacji.
- EN: Bounds are worst-case and for deep networks with millions of parameters yield practically meaningless numbers. They ignore properties of the specific distribution and of the optimisation algorithm.

## Key terms

- PL: **ε i δ**: Dopuszczalny błąd i dopuszczalna szansa, że uczenie się nie uda.
- PL: **rozbijanie (shattering)**: Zdolność modelu do odtworzenia każdego możliwego oznaczenia zbioru punktów.
- PL: **i.i.d.**: Przykłady losowane niezależnie z tego samego rozkładu.
- EN: **ε and δ**: Allowed error and allowed chance that learning fails.
- EN: **shattering**: A model's ability to reproduce every possible labelling of a point set.
- EN: **i.i.d.**: Examples drawn independently from the same distribution.

## Know first

- [Uczenie nadzorowane (Supervised learning)](https://aiatlasgraph.com/t/supervised.md)
- [Rozkłady prawdopodobieństwa (Probability distributions)](https://aiatlasgraph.com/t/distributions.md)

## Related topics

Untyped, symmetric "see also" links.

- [Walidacja krzyżowa (Cross-validation)](https://aiatlasgraph.com/t/crossval.md)

## Sources

- [Shalev-Shwartz & Ben-David · Understanding Machine Learning: From Theory to Algorithms](<https://www.cambridge.org/core/books/understanding-machine-learning/3059695661405D25673058E43C8BE2A6>) `shalev-bendavid-uml-2014` · by Shai Shalev-Shwartz, Shai Ben-David

---

AI Atlas revision 122 (2026-10-30) · HTML: https://aiatlasgraph.com/t/pacvc · index: https://aiatlasgraph.com/llms.txt · everything: https://aiatlasgraph.com/llms-full.txt · updated 2026-10-30