Naukowcy z arXiv opracowali formułę rekurencyjną, która drastycznie przyspieszsa obliczanie złożoności stochastycznej dla wektorów ze strukturą klastrów. Problem polegał na tym, że dotychczasowe podejście oparte na modelu Normalized Maximum Likelihood wymagało czasu wielomianowego, co czyniło go niepraktycznym dla większych zbiorów danych.
Nowa metoda zmienia to obliczeniowe wyzwanie w zadanie wykonalne w czasie liniowym. Kluczem jest efektywne obliczanie stałej normalizacyjnej z modelu NML za pomocą wprowadzonej formuły rekurencyjnej. To fundamentalne przyspieszenie ma znaczenie zarówno teoretyczne, jak i praktyczne.
Wynik ten ma bezpośrednie zastosowanie w klasteryzacji danych opartej na zasadzie Minimum Description Length - principium wyboru optymalnej liczby klastrów i struktury dla konkretnego zbioru danych. Algorytm liniowy zamiast wielomianowego otwiera nowe możliwości dla automatycznego określania najlepszej liczby klastrów bez konieczności empirycznej eksperymentacji czy arbitralnych założeń.