Promoting Simple Agents: Ensemble Methods for Event-Log Prediction

Probleemstelling

In het domein van procesmining (process mining) is het voorspellen van de volgende activiteit in een stroom van gebeurtenislogs (event logs) een cruciale taak voor toepassingen zoals patiëntmonitoring, resource-allocation en het detecteren van bedreigingen. Hoewel complexe neurale netwerken (zoals LSTM en Transformer) vaak hoge nauwkeurigheid bieden, hebben deze modellen aanzienlijke nadelen in streaming-scenario's:

1. Hoge resource-vereisten: Ze vragen veel rekenkracht en geheugen, wat real-time verwerking van grote logs bemoeilijkt.
2. Instabiliteit bij venstergrootte: Vooral Transformer-modellen vertonen onstabiele prestaties afhankelijk van de gekozen venstergrootte (context size). Te kleine vensters missen belangrijke context, terwijl te grote vensters leiden tot overfitting of computationele inefficiëntie.
3. Complexiteit van ensemble-methoden: Traditionele ensemble-methoden (zoals stemmen van meerdere modellen) verbeteren de nauwkeurigheid, maar vereisen dat veel agents parallel draaien, wat de latentie en het geheugengebruik aanzienlijk verhoogt.

Het paper onderzoekt of lichtgewicht, automata-gebaseerde modellen (n-grams) in combinatie met slimme ensemble-strategieën kunnen concurreren met zware neurale netwerken, terwijl ze aanzienlijk minder resources verbruiken.

Methodologie

De auteurs vergelijken verschillende taalmodellen voor next-activity prediction:

• Basismodellen:

  • n-grams: Lichtgewicht modellen die de waarschijnlijkheid van de volgende activiteit baseren op de laatste $n-1$ activiteiten. Ze worden geïmplementeerd als Probabilistische Deterministische Eindige Automaten (PDFAs).
  • LSTM (Long Short-Term Memory): Een recurrente neurale architectuur die goed is in het vastleggen van langetermijnafhankelijkheden.
  • Transformer: Een architectuur gebaseerd op self-attention, die globale afhankelijkheden kan modelleren.

• Experimenteel Ontwerp:

  • De modellen worden getest op synthetische datasets (met specifieke patronen zoals periodieke tellingen en willekeurige patronen) om de impact van venstergrootte te isoleren.
  • Er wordt getest op vijf real-world datasets (o.a. Sepsis, BPI 2012/2013/2017/2018) met duizenden tot miljoenen gebeurtenissen.
  • Er wordt geëvalueerd op zowel nauwkeurigheid als computationele kosten (voorspellings- en trainingslatentie).

• De Nieuwe "Promotion Algorithm":
  Om de nadelen van traditionele ensemble-methoden (zoals Soft Voting en Adaptive Voting, waarbij alle agents parallel draaien) te omzeilen, stellen de auteurs een nieuwe methode voor:

  • Principe: In plaats van alle agents tegelijk actief te houden, draaien er slechts twee agents parallel tijdens de inferentie: een actieve agent ($M_i$) met een kleinere venstergrootte en een "wachter" ($M_{i+1}$) met een grotere venstergrootte.
  • Dynamische selectie: De wachter ($M_{i+1}$) wordt continu getest. Als deze gedurende een vooraf bepaald aantal opeenvolgende voorspellingen ($\tau$, de drempelwaarde) beter scoort dan de huidige actieve agent, wordt de wachter gepromoveerd tot de nieuwe actieve agent.
  • Voordeel: Dit reduceert de overhead drastisch ten opzichte van methoden waarbij alle modellen actief moeten zijn, terwijl het toch de robuustheid van een ensemble behoudt.

Belangrijkste Bijdragen

1. Stabiliteit van n-grams: Het paper toont aan dat n-grams, ondanks hun eenvoud, een zeer stabiele nauwkeurigheid behouden over een breed scala aan venstergroottes, in tegenstelling tot neurale netwerken die gevoelig zijn voor de keuze van de venstergrootte.
2. De Promotion Algorithm: Een innovatieve ensemble-methode die dynamisch schakelt tussen modellen tijdens de inferentie. Dit biedt de nauwkeurigheid van een ensemble met slechts een minimale toename in rekenkosten (slechts 2 actieve agents).
3. Empirisch Bewijs: Uitgebreide experimenten tonen aan dat deze aanpak concurrerend is met state-of-the-art neurale modellen, maar met veel lagere latentie en trainingskosten.

Resultaten

• Synthetische Data:
  • Bij deterministische patronen (zoals AAABBB) presteren n-grams en LSTM/Transformer gelijk goed, mits de venstergrootte correct is.
  • Bij willekeurige patronen vertonen Transformer-modellen een duidelijke afname in nauwkeurigheid bij grote venstergroottes (door attention-capaciteitsproblemen), terwijl n-grams robuuster zijn.
  • De Promotion Algorithm presteert vaak beter dan een enkel n-gram en komt in de buurt van of overtreft de LSTM, zonder de instabiliteit van de Transformer.
• Real-world Data:
  • LSTMs behalen over het algemeen de hoogste absolute nauwkeurigheid op complexe real-world datasets.
  • Echter, een enkel 5-gram model presteert zeer dicht bij de LSTM.
  • Ensemble-methoden (zowel Soft Voting als Promotion) overtreffen de individuele modellen. De Promotion Algorithm bereikt vergelijkbare nauwkeurigheid als Soft Voting, maar is aanzienlijk sneller in voorspellingstijd omdat het minder agents parallel hoeft te draaien.
  • Efficiëntie: De voorspellingslatentie van de Promotion-methode is veel lager dan die van traditionele ensemble-methoden en vergelijkbaar met of lager dan die van complexe neurale netwerken.

Betekenis en Conclusie

Dit paper is significant omdat het de perceptie uitdaagt dat complexe neurale netwerken (zoals Transformers) noodzakelijk zijn voor nauwkeurige streaming-predictie van proceslogs. De auteurs tonen aan dat:

1. Lichtgewicht modellen (n-grams) vaak voldoende zijn, vooral wanneer ze slim worden gecombineerd.
2. Ensemble-methoden effectief kunnen worden ingezet zonder de hoge kosten van parallelle inferentie van alle modellen, dankzij de Promotion Algorithm.
3. Deze aanpak biedt een praktische, schaalbare oplossing voor real-time procesmonitoring, waarbij de trade-off tussen nauwkeurigheid en computational cost optimaal wordt beheerd.

De toekomstige werkrichting omvat het automatiseren van de kalibratie van de drempelwaarde ($\tau$) en het uitbreiden van het algoritme met een "demotion"-mechanisme om om te gaan met concept drift (veranderingen in het procesgedrag over tijd).