Kiedy funkcję uczącą można zrealizować jako program komputerowy?
Computable Universal Online Learning” autorstwa Dariusza Kalocińskiego (IPI PAN) i Tomasza Steifera (IPPT PAN) została przyjęta do prezentacji na konferencji NeurIPS 2025, jednej z najważniejszych światowych konferencji poświęconych uczeniu maszynowemu i sztucznej inteligencji.
Autorzy podejmują w niej fundamentalne pytanie teorii uczenia maszynowego: kiedy funkcję uczącą można zrealizować jako program komputerowy? Badania dotyczą matematycznego modelu znanego jako uniwersalne uczenie online (ang. universal online learning), w którym funkcja ucząca ma popełniać jedynie skończoną liczbę błędów dla każdej realizowalnej sekwencji danych, bez wymogu istnienia wspólnego ograniczenia na liczbę błędów dla wszystkich takich sekwencji. Choć zarówno uczenie uniwersalne, jak i obliczalne były wcześniej badane, autorzy pokazują, że ich połączenie nie jest oczywiste. W szczególności dowodzą, że istnieją relatywnie proste klasy hipotez, które wprawdzie są teoretycznie wyuczalne, lecz nie da się ich nauczyć za pomocą funkcji realizowalnych przez program komputerowy. Wynik ten wskazuje na wyraźną lukę między teoretyczną możliwością uczenia a jego faktyczną realizacją algorytmiczną.
Analiza obejmuje również pełne charakteryzacje wariantu agnostycznego, w którym sekwencje danych mogą nie pochodzić z danej klasy hipotez, jak i uczenia właściwego, w którym funkcja ucząca zawsze zwraca hipotezę z analizowanej klasy. Wyniki wskazują również na istotne związki między wyuczalnością klas hipotez a ich strukturą topologiczną, oferując nowe spojrzenie na granice tego, co w uczeniu maszynowym może być formalnie zrealizowane przez algorytm.
Badania zostały przeprowadzone w ramach projektu pt. "Obliczalna teoria modeli i filozofia strukturalizmu matematycznego" finansowanego ze środków NCN Narodowe Centrum Nauki, nr 2023/49/B/HS1/03930.