💻 computer science

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

Dit artikel introduceert het openstaande probleem van de vraag of de inclusiediepte van patroontalen — een metriek voor de complexiteit van mentale veranderingen bij het leren van positieve data — berekenbaar is voor alle patronen en of een eenvoudige vermoedelijke formule een oplossing in polynomiale tijd mogelijk maakt.

Oorspronkelijke auteurs: Wei Luo

Gepubliceerd 2026-06-01

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Wei Luo

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme collectie strings (zoals woorden of codes) probeert te sorteren in verschillende dozen. Sommige dozen zijn heel algemeen en bevatten bijna alles, terwijl andere heel specifiek zijn en slechts enkele exacte items bevatten.

Dit artikel, geschreven door Wei Luo, is in essentie een detectiveverhaal over een specifiek type puzzel met deze "patroondozen". De auteur stelt twee grote vragen: Kunnen we altijd precies berekenen hoe specifiek een patroon is? en Is er een eenvoudige wiskundige formule om dit te achterhalen zonder miljoenen berekeningen uit te voeren?

Hier is een overzicht van de ideeën uit het artikel met behulp van eenvoudige analogieën:

1. De "Russische Nestpop" van Patronen

Het kernconcept wordt Inclusion Depth genoemd. Denk aan patroontalen als Russische nestpoppen (matroesjka's).

De grootste pop is een "universeel" patroon (zoals een leeg canvas dat van alles kan worden).
Binnen die pop kun je iets specifiekere patronen passen.
Binnen die weer specifiekere patronen, totdat je bij je uiteindelijke, zeer specifieke patroon komt.

De Inclusion Depth is simpelweg het aantal "stappen" of "lagen" dat je moet afleggen van de grootste, meest algemene pop naar je specifieke doelpop.

Het Voorbeeld:
Als je doelpatroon 0x11 is (waarbij x een variabele is die alles kan zijn), laat de auteur zien dat je een keten van 5 poppen kunt bouwen:

De grootste (alles mag).
Een iets kleinere.
Een middelgrote.
Een kleinere.
Jouw specifieke doel 0x11.

De "diepte" is hier 4 (het aantal stappen tussen de bovenkant en de onderkant).

2. De Grote Vraag: Is Er een Afkorting?

De auteur vraagt: Kunnen we een computerprogramma schrijven om deze stappen te tellen voor elk patroon?

Momenteel is het controleren of het ene patroon binnen het andere past bekend als een "nachtmerrie" voor computers (wiskundig gezien is het onbeslisbaar). De auteur vermoedt echter dat voor dit specifieke telprobleem wellicht een veel eenvoudigere manier bestaat.

De Hypothese van de "Magische Formule":
De auteur stelt een eenvoudige vergelijking voor die het hele puzzelstukje direct zou kunnen oplossen:

Depth = (2 × Lengte van Patroon) − (Aantal Unieke Variabelen) − 1

Denk er zo over na:

Lengte: Hoe lang de string is.
Variabelen: Hoeveel "wildcards" (zoals x1, x2) erin staan.

Als deze formule waar is, hoef je niet de nestpoppen één voor één te bouwen. Je telt gewoon de letters en de wildcards, voert ze in de formule in, en boem—je hebt het antwoord. Dit zou een moeilijke, trage berekening veranderen in een razendsnelle berekening.

3. Het Detectivewerk Tot Nu Toe

De auteur heeft deze "Magische Formule" getest op kleine patronen (korte strings).

Het Goede Nieuws: Voor korte patronen (tot 7 tekens lang) werkt de formule elke keer perfect.
Het Slechte Nieuws: De auteur kon geen langere patronen testen omdat de computerberekeningen te zwaar en traag worden.

De auteur vermoedt dat als de formule faalt, de "dader" een zeer lang patroon moet zijn (langer dan 7 tekens).

4. Waarom Is Dit Belangrijk?

Het artikel vermeldt dat dit niet alleen over wiskunde om de wiskunde gaat. Het heeft betrekking op "mind-change complexity" (complexiteit van het veranderen van de mening).

Stel je voor dat je een student bent die een regel leert.

Als de regel heel algemeen is, kun je misschien vaak het verkeerde raden voordat je het goed hebt.
Als de regel heel specifiek is, kun je het misschien snel doorhebben.

De "Inclusion Depth" meet hoe vaak je je gok zult moeten aanpassen voordat je het juiste patroon eindelijk hebt geleerd. Als we de diepte gemakkelijk kunnen berekenen (met de formule), kunnen we voorspellen hoe moeilijk een leerprobleem zal zijn en betere AI-leerlingen bouwen die geen tijd verspillen aan gokken.

Samenvatting

Het Doel: Een manier vinden om de "lagen van specificiteit" in een patroon te tellen.
De Hoop: Er is een eenvoudige wiskundige formule (gebaseerd op lengte en aantal variabelen) die het antwoord direct geeft.
De Status: De formule werkt voor kleine voorbeelden, maar de auteur heeft nog niet bewezen dat dit voor alle patronen geldt. Het artikel is een open uitnodiging aan andere wiskundigen om deze formule te bewijzen (of te weerleggen).

Technische Samenvatting: Het Berekenen van de Inclusiediepte van een Patroon

Probleemdefinitie
Deze notitie behandelt het probleem van het berekenen van de inclusiediepte van een patroontaal, een metriek die ontworpen is om de "mind-change complexiteit" te vatten die inherent is aan problemen van patroonidentificatie. De centrale vraag is of deze diepte berekenbaar is voor elk gegeven patroon en, specifiek, of deze een eenvoudige combinatorische karakterisering toelaat op basis van de structurele eigenschappen van het patroon.

Formeel: laat $X$ een verzameling variabelen zijn en $\Sigma$ een eindig alfabet met ten minste twee symbolen. Een patroon $p$ is een eindige, niet-lege sequentie over $X \cup \Sigma$ . De taal $L_\Sigma(p)$ bestaat uit alle grondstrings gegenereerd door elke variabele in $p$ te substitueren met een niet-lege string uit $\Sigma^+$ .

De inclusiediepte, aangeduid als $ID_\Sigma(p)$ , wordt gedefinieerd als de lengte van de langste strikte inclusieketen die de taal van het universele patroon $L_\Sigma(x_1)$ verbindt met de taal $L_\Sigma(p)$ . Bijvoorbeeld, als $p = 0x_11$ is over $\Sigma=\{0,1\}$ , dan is de inclusiediepte 4, wat overeenkomt met een keten van vier strikte inclusies van $L_\Sigma(x_1)$ naar beneden naar $L_\Sigma(0x_11)$ .

Methodologie en Conjecturen
Het artikel benadert de berekenbaarheid van de inclusiediepte door een directe combinatorische formule voor te stellen. De auteur stelt dat de inclusiediepte uitsluitend wordt bepaald door de lengte van het patroon ( $|p|$ ) en het aantal verschillende variabelen dat het bevat ( $\#var(p)$ ).

De primaire hypothese, Vraag 2, suggereert dat voor elk alfabet $\Sigma$ met $|\Sigma| \geq 2$ :
$ID_\Sigma(p) = 2|p| - \#var(p) - 1$

Als deze vergelijking standhoudt, impliceert dit de existentie van een lineair-tijd algoritme om de inclusiediepte te berekenen, waarmee aan Vraag 1 (het bestaan van een berekenbaar algoritme) in het positief wordt beantwoord.

Om de berekenbaarheid van de inclusiediepte te valideren, introduceert het artikel Conjectuur 1, die een noodzakelijke voorwaarde vaststelt voor patroominclusie. Het stelt dat als de taal van patroon $p$ een strikte deelverzameling is van de taal van patroon $q$ ( $L(p) \subset L(q)$ ), de volgende ongelijkheid moet gelden:
$2|p| - \#var(p) > 2|q| - \#var(q)$

De auteur merkt op dat de afhankelijkheid van het specifieke alfabet $\Sigma$ kan worden gereduceerd tot het geval waarbij $\Sigma$ precies twee symbolen bevat, aangezien inclusierelaties behouden blijven over deelverzamelingen van het alfabet.

Resultaten en Partiële Oplossingen
Het artikel levert geen formeel bewijs voor de conjecturen, maar biedt empirisch bewijs en theoretische context:

Onbeslisbaarheid Context: Er wordt erkend dat het algemene probleem van het beslissen van patroominclusie onbeslisbaar is. De auteur voert echter aan dat het berekenen van de inclusiediepte mogelijk geen oplossing vereist voor het algemene inclusieprobleem voor willekeurige paren.
Empirische Verificatie: Een exhaustieve berekening uitgevoerd door het programma van de auteur bevestigde dat de ongelijkheid in Conjectuur 1 geldt voor alle patronen met een lengte kleiner dan of gelijk aan 7.
Computationele Limieten: De verificatie voor patronen met een lengte groter dan 7 werd als computationeel onpraktisch beschouwd. Bij consequentie, indien een tegenvoorbeeld voor de conjectuur bestaat, moet dit een patroon betreffen met een lengte groter dan 7.

Significantie en Claims
De significantie van dit werk ligt in de poging om de kloof te overbruggen tussen de theoretische complexiteit van patroonidentificatie en praktische berekenbaarheid.

Mind-Change Complexiteit: De inclusiediepte is bedoeld om de mind-change complexiteit te kwantificeren van het identificeren van patronen gegeven initiële bewijslast.
Algoritmische Implicaties: Indien de voorgestelde combinatorische karakterisering (Vergelijking 1) bewezen wordt, zou dit de constructie van een lineair-tijd algoritme mogelijk maken om de inclusiediepte te berekenen.
Learner Constructie: Een positieve oplossing van de berekenbaarheidsvraag zou de berekening van mind-change grenzen voor patroonidentificatieproblemen mogelijk maken en de constructie van een uniform mind-change optimaal leerder faciliteren.

Het artikel concludeert door het probleem te kaderen als een open vraag, en nodigt uit tot verder onderzoek om ofwel de combinatorische karakterisering te bewijzen, ofwel een tegenvoorbeeld in langere patronen te vinden.