Dlaczego funkcja utraty 0-1 jest trudna do rozwiązania?

W książce Ian Goodfellow's Deep Learning napisano o tym

Czasami funkcja utraty, o którą tak naprawdę dbamy (powiedzmy, błąd klasyfikacji), nie jest funkcją, którą można skutecznie zoptymalizować. Na przykład dokładne minimalizowanie oczekiwanej straty 0-1 jest zazwyczaj trudne (wykładnicze w wymiarze wejściowym), nawet w przypadku klasyfikatora liniowego. W takich sytuacjach zwykle zamiast tego optymalizowana jest funkcja zastępczej utraty, która działa jak proxy, ale ma zalety.

Dlaczego strata 0-1 jest trudna do rozwiązania lub jak jest wykładnicza w wymiarach wejściowych?

Funkcja utraty 0-1 jest nie wypukła i nieciągła, więc nie można zastosować metod (sub) gradientowych. W przypadku klasyfikacji binarnej z separatorem liniowym tę funkcję straty można sformułować jako znalezienie która minimalizuje średnią wartość funkcji wskaźnika nad wszystkimi próbek. Jest to wykładnicze na wejściach, ponieważ ponieważ istnieją dwie możliwe wartości dla każdej pary, istnieją możliwe konfiguracje, aby sprawdzić$\beta$$\mathbf{1}(y_{i}\beta\mathbf{x}_{i} \leq 0)$$i$$2^{n}$$n$łączna liczba punktów próbki. Jest to znane jako trudne dla NP. Znajomość bieżącej wartości funkcji utraty nie daje żadnej wskazówki, w jaki sposób należy zmodyfikować obecne rozwiązanie w celu ulepszenia, ponieważ można by dowiedzieć się, czy dostępne byłyby metody gradientu dla funkcji wypukłych lub ciągłych.

Błąd klasyfikacji jest w rzeczywistości czasami możliwy do naprawienia. Można go skutecznie zoptymalizować - choć nie do końca - stosując metodę Neldera-Meada, jak pokazano w tym artykule:

https://www.computer.org/csdl/trans/tp/1994/04/i0420-abs.html

„Redukcja wymiarów jest procesem przekształcania wektorów wielowymiarowych w przestrzeń niskiego wymiaru. W rozpoznawaniu wzorów często jest pożądane, aby to zadanie było wykonywane bez znaczącej utraty informacji klasyfikacyjnych. Błąd Bayesa jest jednak idealnym kryterium do tego celu; wiadomo, że jest to niezwykle trudne w traktowaniu matematycznym. W związku z tym w praktyce zastosowano nieoptymalne kryteria. Proponujemy alternatywne kryterium oparte na oszacowaniu błędu Bayesa, które, miejmy nadzieję, jest bliższe kryterium optymalnemu niż obecnie stosowane kryteria Opracowano i wdrożono algorytm liniowej redukcji wymiarów oparty na tym kryterium. Eksperymenty wykazują jego lepszą wydajność w porównaniu z konwencjonalnymi algorytmami. ”

Wspomniany tutaj błąd Bayesa to w zasadzie strata 0-1.

Ta praca została wykonana w kontekście liniowej redukcji wymiarów. Nie wiem, jak efektywny byłby trening sieci głębokiego uczenia się. Ale chodzi o to, a odpowiedź na pytanie: strata 0-1 nie jest uniwersalna. Można go stosunkowo dobrze zoptymalizować dla przynajmniej niektórych rodzajów modeli.