Czym jest Efektywność algorytmiczna (algorithmic efficiency)?
Efektywność algorytmiczna to zdolność algorytmu do wykonywania zaplanowanego zadania przy możliwie najmniejszym zużyciu zasobów, najczęściej czasu procesora i pamięci operacyjnej. W kontekście uczenia maszynowego odnosi się także do optymalizacji liczby operacji arytmetycznych, ilości przesyłanych danych oraz zużycia energii podczas trenowania i wnioskowania modeli. Pojęcie to zakorzenione jest w analizie złożoności obliczeniowej zapoczątkowanej w latach 60. XX w. przez Jacka Edmondsa, Dona Knutha i Manuela Bluma, lecz zyskało nowe znaczenie wraz z dynamicznym rozwojem metod głębokiego uczenia.
Jak dokładnie działa Efektywność algorytmiczna (algorithmic efficiency)
W praktyce efektywność ocenia się za pomocą notacji złożoności obliczeniowej, na przykład O(n log n) dla sortowania przez scalanie. W systemach opartych na sieciach neuronowych mierzy się liczbę mnożeń i dodawań (FLOPs), czas treningu w godzinach GPU lub liczbę parametrów wymaganych do osiągnięcia danego progu dokładności. Optymalizacja może polegać na zmianie architektury, zastosowaniu kwantyzacji, kompresji, dzielenia obliczeń na równoległe lub wykorzystaniu bardziej inteligentnych metod próbkowania danych. Dzięki temu ten sam problem rozwiązuje się szybciej lub na sprzęcie o mniejszej mocy obliczeniowej.
Zastosowania w praktyce
Udoskonalona efektywność algorytmiczna ułatwia wdrażanie modeli na urządzeniach brzegowych, takich jak smartfony czy sterowniki przemysłowe, gdzie zasoby są ograniczone. Przykładem jest zastąpienie klasycznej, pełnej samo-uwagi w transformatorach mechanizmem sparse attention, co pozwoliło firmie OpenAI w 2020 r. trenować model GPT-3 przy mniejszym zapotrzebowaniu na pamięć niż wczesne rozwiązania. Podobnie w widzeniu maszynowym zastosowanie splotów FFT zmniejsza złożoność z O(k²) do O(k log k) względem rozmiaru jądra, umożliwiając szybsze przetwarzanie obrazów megapikselowych.
Zalety i ograniczenia
Największą korzyścią jest redukcja kosztów infrastruktury oraz emisji CO₂ podczas obliczeń, co przekłada się na łatwiejszą skalowalność projektów badawczych i komercyjnych. Należy jednak pamiętać, że zbyt agresywna optymalizacja może powodować utratę dokładności lub stabilności uczenia. Ponadto realny czas działania zależy od współdziałania z bibliotekami niskopoziomowymi oraz od efektywności pamięci podręcznych procesora lub GPU, czego nie zawsze odzwierciedla sama notacja O.
Na co uważać?
Projektując system, warto monitorować zarówno metryki obliczeniowe, jak i metryki biznesowe. Zdarza się, że model o mniejszej liczbie parametrów zużywa więcej energii przez niedostosowane operacje wejścia-wyjścia. Istotne jest też przestrzeganie zasad prawidłowej replikacji wyników: publikacje często prezentują przyspieszenia uzyskane na niestandardowym sprzęcie, co utrudnia porównanie z klasycznymi, szeroko dostępnymi metodami.
Dodatkowe źródła
Szczegółową analizę złożoności można znaleźć w klasycznej monografii Dona Knutha „The Art of Computer Programming”, dostępnej w syntetycznym omówieniu na stronie Wikipedia.
Rzeczywiste przykłady optymalizacji w głębokim uczeniu omawia artykuł „EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks” dostępny w repozytorium arXiv.
Metody redukcji złożoności samo-uwagi przedstawia publikacja „Longformer: The Long-Document Transformer” pod adresem arXiv.
