Zero Silnia - czyli dlaczego 0!=1?

Artykuł "Mnożenie liczb ujemnych - czyli dlaczego minus razy minus daje plus?" cieszy się ogromnym zainteresowaniem (np. w piątek 21.10.2016 został pobity rekord, mianowicie tylko w tym jednym dniu 350 unikalnych użytkowników zapoznało się z treścią wpisu). Będąc świadomym, że dla wielu z Was ważne jest zrozumienie motywacji stojącej za podstawowymi definicjami, postanowiłem rozpocząć nowy cykl "Dlaczego?". Nowa seria skupi się na powszechnie znanych zagadnieniach, których wyjaśnienie nie jest już takie oczywiste. 🙂 Dziś na tapetę idzie zero silnia! Przedstawię kilka argumentacji - w tym coś dla mniej i coś dla bardziej zaawansowanych! Będzie hardcorowo 🙂

Zero silnia równa się jeden / 0!=1

Silnia - definicja

W celu przypomnienia

n!=n\times (n-1)\times (n-2)\times \ldots \times 2\times 1

Przykłady

4!=4\cdot 3\cdot 2\cdot 1=24

3!=3\cdot 2\cdot 1=6

2!=2\cdot 1=2

1!=1

0!=??? - no właśnie 🙂 - do tego wrócę za chwilkę!

Silnia jako liczba permutacji

W uproszczeniu permutacja zbioru (mówimy o zbiorach skończonych) to funkcja wyznaczająca kolejność jego elementów. Np. {1,2,3,4}, {2,4,1,3}, {4,3,2,1} ... są różnymi permutacjami zbioru {1,2,3,4}.

W ogólnym przypadku - jeśli mamy do czynienia ze zbiorem n-elementowym otrzymujemy:

  • n sposobów wyboru elementu 1 (bo mamy do dyspozycji cały zbiór)
  • n-1 sposobów wyboru elementu 2 (bo pierwszy jest już wybrany, pozostało n-1)
  • n-2 sposobów wyboru elementu 3 (bo 2 pierwsze są już wybrane, pozostało n-2)
  • ...
  • n-(k-1) sposobów wyboru elementu k (bo k-1 pierwszych jest już wybranych, pozostało n-(k-1) )
  • ...
  • 2 sposoby wyboru elementu n-1 (bo n-2 elementy wybrano, pozostały wolne 2)
  • 1 sposób wyboru elementu n (bo n-1 elementów wybrano, pozostał wolny tylko 1)

i finalnie liczba różnych uporządkowań zbioru n-elementowego wynosi:

{\small n\times (n-1)\times (n-2)\times \ldots \times 2\times 1=n!}

Zatem interpretacja n! to liczba permutacji (czyli liczba różnych uporządkowań) zbioru n-elementowego.

No dobrze - ale jak to pomaga w ustaleniu 0! (zero silnia)? Przecież ciężko mówić o kolejności elementów zbioru pustego... Do tego wrócę również nieco później 🙂

Wariacja bez powtórzeń

Brrr - paskudna ta nazwa - ale ok - spróbujmy. Mówimy, że wybór dokładnie k-różnych elementów, zwracając uwagę na kolejność, ze zbioru n-elementowego, jest k-elementową wariacją bez powtórzeń zbioru n-elementowego. Przykłady różnych 3-elementowych wariacji bez powtórzeń zbioru {1,2,3,4,5} to: {1,2,3}, {3,2,1},{4,5,2},...

Liczbę V_n^k k-elementowych wariacji bez powtórzeń zbioru n-elementowego wyznaczymy na bazie:

  • n sposobów wyboru elementu 1
  • n-1 sposobów wyboru elementu 2
  • n-2 sposobów wyboru elementu 3
  • ...
  • n-(k-1) sposobów wyboru elementu k

i finalnie

{\large V_n^k}={\small n\times (n-1)\times (n-2)\times\ldots\times \bigg(n-(k-1)\bigg)}

ale

{\small n\times (n-1)\times (n-2)\times \ldots\times \big(n-(k-1)\big)}=...

={\small\frac{n\times (n-1)\times (n-2)\times \ldots\times \big(n-(k-1)\big)\times (n-k)\times \ldots \times 2\times 1}{(n-k)\times \ldots \times 2\times 1}}=...

...=\frac{n!}{(n-k)!}

Zatem

{\large V_n^k=}{\Large\frac{n!}{(n-k)!} }

0! = 1 (słownie: zero silnia równa się jeden)

Zauważmy, że n-elementowa wariacja bez powtórzeń zbioru n-elementowego jest w zasadzie jego permutacją, zatem liczba takich wariacji będzie równa liczbie permutacji, co zapisujemy:

{\large V_n^n=n!}

ale

{\large V_n^n=}{\Large \frac{n!}{(n-n)!}}={\Large \frac{n!}{0!}}

w konsekwencji

n!={\large \frac{n!}{0!}}

{0!\cdot n!=n!}

{\Large 0!=1}

Powyższe uzasadnia, że przyjęcie 0!=1 jest wygodne, gdyż zapewnia "spójność" podstawowych wzorów. Ale czy stoi za tym coś więcej?

!!! Dalsza część dla nieco bardziej zaawansowanych czytelników !!!

Funkcja jako odwzorowanie zbiorów

Funkcja "- schemat

Funkcja f:A\to B, gdzie dla każdego a \in A istnieje f(a)=b\in B wyznacza tak naprawdę relację pomiędzy elementami a i b. Przy takim podejściu możemy powiedzieć, że elementy a\in A oraz b\in B są w relacji f wtedy i tylko wtedy gdy f(a)=b.

Funkcja jako podzbiór iloczynu kartezjańskiego

Funkcję f:A\to B możemy potraktować jako podzbiór iloczynu kartezjańskiego zbiorów A i B, co symbolicznie zapiszemy f\subseteq A\times B

(a,b)\in f \subseteq A\times B \iff f(a)=b

Dobrym przykładem jest wykres funkcji rzeczywistej, który jest podzbiorem płaszczyzny.

Iniekcja - czyli funkcja różnowartościowa

Funkcja "1-1" różnowartościowa - Iniekcja

Iniekcja to inaczej funkcja różnowartościowa, tzn. funkcja f:A\to B jest różnowartościowa wtedy i tylko wtedy, gdy dla dowolnych elementów x,y\in A spełniony jest warunek

x\neq y \implies f(x) \neq f(y)

Surjekcja - czyli funkcja "na"

Funkcja "na" - Surjekcja

Surjekcja to taki przypadek funkcji f:A\to B, że każdy element zbioru B ma swój odpowiednik w zbiorze A. Formalnie zapiszemy to tak

{\large \displaystyle\forall_{b \in B} \quad\displaystyle\exists_{a\in A}\quad}f(a)=b

Bijekcja - czyli funkcja odwracalna (wzajemnie jednoznaczna)

Funkcja odwracalna "1-1" i "na" - Bijekcja

Bijekcja to funkcja f:A\to B, która jednocześnie spełnia warunek iniekcji oraz surjekcji, tzn. jest różnowartościowa oraz "na". Bijekcja jest funkcją odwracalną i wyznacza odwzorowanie wzajemnie jednoznaczne zbioru A na zbiór B (każdy element zbioru A jest jednoznacznie przypisany do elementu zbioru B, oraz każdy element zbioru B ma jednoznaczny odpowiednik w zbiorze A).

Bijekcja vs Permutacja

Permutacja jest funkcją zwracająca uporządkowanie zbioru, tzn. jeśli rozważamy n-elementowy zbiór {1, 2, ..., n} to permutacja będzie funkcją

p:\{1, 2, ..., n\}\to\{1, 2, ..., n\}

spełniającą warunek bijekcji. Pytając o liczbę permutacji możemy równoważnie pytać o liczbę różnych bijekcji z danego zbiory w samego siebie.

Funkcja pusta f:\emptyset\to B

Funkcją pustą nazywamy każdą funkcję, której dziedziną jest zbiór pusty.

f:\emptyset\to B

Wykres funkcji pustej jest zbiorem pustym, gdyż iloczyn kartezjański \emptyset\times B=\emptysetFunkcja pusta jest różnowartościowa, gdyż w dziedzinie (czyli w zbiorze pustym) nie istnieją takie dwa różne elementy, dla których wartość funkcji jest równa.

Funkcja pusta f:\emptyset\to \emptyset

Funkcja pusta f:\emptyset\to \emptyset jest bijekcją, gdyż nie istnieje element przeciwdziedziny (przeciwdziedzina jest zbiorem pustym) nie będący w relacji z elementem dziedziny. Zauważmy, że istnieje dokładnie jedna bijekcja f:\emptyset\to \emptyset, co wynika z faktu, że funkcja jest podzbiorem iloczynu kartezjańskiego dziedziny i przeciwdziedziny. W przypadku rozważanej funkcji pustej f:\emptyset\to \emptyset wspominany iloczyn kartezjański to zbiór pusty \emptyset\times\emptyset=\emptyset, który ma dokładnie jeden podzbiór - również zbiór pusty.

0! = 1 vs funkcja pusta f:\emptyset\to \emptyset

Pisałem wyżej, że liczbę permutacji zbioru n-elementowego można utożsamiać z liczbą bijekcji z tego zbioru w samego siebie. Tym samym permutacjom zbioru 0-elementowego odpowiadają bijekcje ze zbioru pustego w zbiór pusty - a taka funkcja jest dokładnie jedna! 🙂 Trochę abstrakcyjne, ale się zgadza 🙂

Funkcja Gamma (zwana również gammą Eulera) - czyli silnia dla liczb rzeczywistych i zespolonych

Funkcja Gamma - źródło Wikipedia

Funkcja Gamma jest funkcją, która rozszerza pojęcie silni na cały zbiór liczb rzeczywistych, a nawet zespolonych!

\Gamma(z)=\displaystyle\int_0^{+\infty}t^{z-1}e^{-t}dt

 Okazuje się (po scałkowaniu przez części), że

\Gamma(z+1)=z\cdot\Gamma(z)

oraz

\Gamma(1)=\displaystyle\int_0^{+\infty}e^{-t}dt=...

...=\displaystyle\int_{-\infty}^{0}e^{t}dt=...

...=[e^{t}]_{-\infty}^{0}=...

...=e^0-e^{-\infty}=1-0=1

 \Gamma(1)=1

Z powyższego wynika, że dla wszystkich całkowitych liczb n\geq 0 zachodzi

 {\Gamma(n+1)=n!}

 {\large0!=\Gamma(1)=1}

Kolejne bardzo ciekawe spostrzeżenie, że {0!} ma związek z funkcją eksponencjalną!!

Funkcja eksponencjalna

Zwięzek liczby e oraz silni jest nawet większy!

e=\displaystyle\sum_{n=0}^\infty\frac{1}{n!}=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\ldots

Obiecałem, że będzie hardcorowo - i było 🙂

Pozdrowienia,

Mariusz Gromada

Pierwsze urodziny MathSpace.pl

MathSpace.pl - pierwsze urodziny!

Pierwszy wpis pojawił się 20 października 2015.

Przez rok opublikowałem 57 artykułów, znaczna część zamieszczona w 6 seriach:

Każdego dnia blog odwiedza około 40-50 osób - to niezły wynik zważywszy na raczej niełatwą tematykę 🙂

Google docenił MathSpace.pl, w efekcie dla szeregu zapytań blog pozycjonowany jest bardzo wysoko.

Dziękuję! 🙂

Pozdrowienia,

Mariusz Gromada

Karl Weierstrass i Funkcja Weierstrassa - czyli geometria fraktalna (część 2)

Karl Weierstrass - źródło Wikipedia: https://pl.wikipedia.org/wiki/Karl_Weierstrass

Karl Theodor Wilhelm Weierstrass (1815 - 1897) niemiecki matematyk uznawany za "ojca współczesnej analizy matematycznej". Choć minęło już 17 lat, to nadal doskonale pamiętam pierwszy semestr studiów matematycznych i ekspozycję na podstawowe "bardziej abstrakcyjne" twierdzenia, w tym Twierdzenie Bolzano-Weierstrassa. Twierdzenie mówi, że "każdy rzeczywisty ciąg ograniczony zawiera podciąg zbieżny", i choć brzmi prosto i ogólnie, jest niezwykle przydatnym narzędziem dowodzenia innych wyników metodą nie-wprost (zgodnie ze schematem "załóżmy, że ... wtedy istnieje ciąg ograniczony, że ..., wtedy istnieje podciąg zbieżny, że ..., i z własności ... wynika sprzeczność z założeniem"). Pięknie to (i nie tylko to) wykładał Pan Prof. Dr Hab. Tadeusz Rzeżuchowski - wielkie dzięki Panie Profesorze!

Funkcja Weierstrassa

Większość matematyków z okresu XVIII i XIX wieku uważało, że wszystkie rzeczywiste funkcje ciągłe są różniczkowalne w znaczącej części swej dziedziny (poza zbiorem izolowanych punktów). Dosyć naturalny pogląd okazał się jednak fałszywy, co wykazał Weierstrass w 1872 roku, a wcześniej podejrzewali Bernhard Riemann oraz Bernard Bolzano (prawdopodobnie w roku 1830 Bolzano podał kontrprzykład, którego nie opublikował). Funkcja Weierstrassa jest przykładem rzeczywistej funkcji ciągłej nieróżniczkowalnej w całej dziedzinie (tzn. nie istnieje ani jeden punkt dziedziny, w otoczeniu którego funkcja zachowuje się "normalnie" - np. monotonicznie). Własność nietypowa, a nawet patologiczna! Jednak nie dla fraktali, zatem i nie dla otaczającej nas natury (analogia do nieintuicyjnej mechaniki kwantowej zaskakująco precyzyjnie opisującej rzeczywistość).

{\Large f(x)=\displaystyle\sum_{n=0}^\infty a^n\cos(b^n\pi x)}

gdzie

{\large 0<a<1\qquad ab>1+\frac{3}{2}\pi}

Warto zauważyć, że funkcję Weierstrassa można zapisać w postaci analitycznej (w uproszczeniu - podając wzór).

Funkcja Weierstrassa i fraktale

Poniżej wykres funkcji Weierstrassa na przedziale [-2; 2].

Funkcja Weierstrassa - By Eeyore22 (Own work) [Public domain], via Wikimedia Commons

Benoit Mandelbrot mawiał, że "fraktal to zbiór matematyczny (lub inny obiekt ) charakteryzujący się w każdej skali wysoką nieregularnością oraz dużą fragmentacją." W części pierwszej cyklu o "geometrii fraktalnej"odnosząc się do słów Mandelbrota, pisałem, że cechą fraktalną jest nietrywialna struktura obiektu w każdej skali - tzn. powiększanie ujawnia kolejne równie skomplikowane formy. Wspomniałem również o samo-podobieństwie - tzn. sytuacji, gdy w skład obiektu wchodzą jego "mniejsze" kopie. Wykres funkcji Weierstrassa zdaje się spełniać te kryteria - był to pierwszy odkryty fraktal!

Karl Weierstrass - ciekawostki

Weierstrass wykładał w Wałczu oraz w Braniewie. Wikipedia wymienia, że jego uczniami byli: Georg Cantor, Otto Holder, Georg Frobenius, Felix Klein, Hermann Minkowski.

 

Pozdrowienia,

Mariusz Gromada

Captured Response = ROC x apriori - czyli ocena jakości klasyfikacji (część 8)

W części #6 oraz części #7 cyklu "Ocena jakości klasyfikacji" przedstawiłem krzywą zysku (aka: Gain, Captured Response) oraz krzywą ROC. Dzisiaj skupię się na mało znanej, acz bardzo prostej i przydatnej, relacji pomiędzy tymi krzywymi - okazuje się bowiem, że wykresy są "niemal identyczne" 🙂

Captured Response vs ROC

Wzór łączący ROC z Captured Response

X_{cr}=Y_{roc}\times apriori+X_{roc}\times \Big(1-apriori\Big)

Y_{cr}=Y_{roc}

Geometryczne podobieństwo Captured Response i ROC

Odpowiednio spoglądając na umieszczone obok siebie wykresy ciężko odeprzeć wrażenie, że krzywe są bardzo podobne. Intuicja podpowiada, że mamy tu do czynienia z tymi samymi funkcjami, jedynie naszkicowanymi w nieco różnych układach współrzędnych.

Captured Response vs ROC

W obu przypadkach to "przestrzeń" pomiędzy modelem losowym i modelem idealnym definiuje odpowiedni układ współrzędnych, a różnica obecna w Captured Response powiązana jest z a-priori (CR jest zależna od a-priori, ROC nie zależy od a-priori). Idąc za kolejnym przeczuciem powiemy, że najprawdopodobniej dla tej samej wartości "Y" różnić się będą wartości "X" (ze względu na "ściśniecie" obecne w Captured Response).

Wzór na bazie proporcji - jedynie poglądowo

Uwaga: poniższe wyprowadzenie jest jedynie pomocnicze, nie stanowi wystarczającej argumentacji uzasadniającej "identyczność" krzywych Captured Response i ROC!!! Formalna argumentacja znajduje się w kolejnej sekcji.

Oznaczmy punkty (wykres powyżej):

B_{cr}=\Big(X_{cr}, Y_{cr}\Big) - punkt na krzywej Captured Response

B_{roc}=\Big(X_{roc}, Y_{roc}\Big) - punkt na krzywej ROC

Podążając za "głosem wewnętrznym" 🙂 napiszemy równość

Y_{cr}=Y_{roc}

oraz równość proporcji długości odcinków

{\Large\frac{a_{cr}}{a_{cr}+b_{cr}}=\frac{a_{roc}}{a_{roc}+b_{roc}}}

To pozwoli wyprowadzić formułę dla wartość X_{cr} w zależności od współrzędnych \Big(X_{roc}, Y_{roc}\Big).

Długość odcinka: a_{roc}=X_{roc}

Długość odcinka: a_{roc}+b_{roc}=Y_{roc} (wynika z pozycji punktu C_{roc}=C_{cr}).

Przechodzimy od wyznaczenia współrzędnych punktu A_{cr} leżącego na krzywej idealnej wykresu Capture Response.

Prosta "idealna" jest opisana równaniem: y={\Large\frac{x}{apriori}} dla x mniejszych od a-priori, zatem

x=y\times apriori

I dalej współrzędne

A_{cr}=\Big(Y_{cr}\times apriori, Y_{cr}\Big)=\Big(Y_{roc}\times apriori, Y_{roc}\Big)

Zaś współrzędne

B_{cr}=\Big(X_{cr}, Y_{cr}\Big)=\Big(X_{cr}, Y_{roc}\Big)

C_{cr}=\Big(Y_{cr}, Y_{cr}\Big)=\Big(Y_{roc}, Y_{roc}\Big)

W tej chwili przystępujemy do wyznaczenia długości odcinków

Długość odcinka: a_{cr}=X_{cr}-Y_{roc}\times apriori

Długość odcinka: a_{cr}+b_{cr}=Y_{roc}-Y_{roc}\times apriori=Y_{roc}\Big(1-apriori\Big)

Kilka ostatnich kroków

{\Large\frac{a_{cr}}{a_{cr}+b_{cr}}=\frac{a_{roc}}{a_{roc}+b_{roc}}}

{\Large\frac{X_{cr}-Y_{roc}\times apriori}{Y_{roc}\Big(1-apriori\Big)}=\frac{X_{roc}}{Y_{roc}}}

Mnożymy przez Y_{roc}

{\Large\frac{X_{cr}-Y_{roc}\times apriori}{1-aprior}}=X_{roc}

X_{cr}-Y_{roc}\times apriori=X_{roc}\times \Big(1-apriori\Big)

I finalnie

X_{cr}=Y_{roc}\times apriori+X_{roc}\times \Big(1-apriori\Big)

Y_{cr}=Y_{roc}

Wynik bardzo ciekawy - faktycznie wystarczy a-priori 🙂 Jednak to nie jest dowód, wyprowadzenie bazowało na intuicji ...

Pełny dowód na bazie macierzy błędu i prawdopodobieństw

Oś "Y" w przypadku ROC to True-Positive Rate, czyli

TPR={\Large\frac{TP}{TP+FN}}={\Large\frac{TP}{Faktyczne.P}}=P(1|1)

Macierz błędu

Z powyższego bezpośrednio wynika, że

Y_{cr}=Y_{roc}

Współrzędna "X" krzywej Captured Response to kwantyl bazy, tzn. gdyby założyć, że X% bazy klasyfikujemy pozytywnie, to dotrzemy do Y% frakcji targetu - zatem X_{cr} jest rozmiarem frakcji przewidywania pozytywnego. Rozważmy poniższy rozkład oceny modelem.

True-Positive, False-Positive, True-Negative, False-Negative vs ocena modelem

Przewidywanie pozytywne składa się z frakcji TP+FP, ale

Klasyf.P=TP+FP=...

...=TPR\times Faktyczne.P+FPR\times Faktyczne.N

P(klasyf=P)=...

...=TPR\times apriori+FPR\times (1-apriori)=...

...=P(1|1)P(1)+P(1|0)P(0)

Finalnie

X_{cr}=Y_{roc}\times apriori+X_{roc}\times \Big(1-apriori\Big)

Y_{cr}=Y_{roc}

Co z tego wynika?

  • Rozumiejąc relację pomiędzy krzywą ROC a krzywą Captured Response analiza modelu jest znacznie prostsza, szczególnie jeśli korzystamy z narzędzia, które prezentuje tylko jeden wariant krzywej (często ROC). Przy małych apriori oś "X" krzywej ROC można praktycznie uznać za oś "X" krzywej Captured Response. Przy większych apriori należy intuicyjnie przesuwać "X" w prawo aby z ROC uzyskać Captured Response.
  • Gini policzone na ROC oraz na CR (pamiętając o przestrzeni pomiędzy modelem losowym i modelem idealnym) bedą sobie równe.

Przykład działania wzoru

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Captured Response

Pozdrowienia,

Mariusz Gromada

Richard Feynman - Bo to jest tak, że ja muszę rozumieć świat

Richard Phillips Feynman (1915-1988) - amerykański fizyk teoretyk, niezwykle charyzmatyczna postać, nauczyciel, filozof, aktor, showman, laureat nagrody nobla z fizyki (1965 r. - tzw. diagramy Feynmana), osoba wyprzedzająca swoją epokę o całe dekady, również w kwestii nauk informacyjnych. Feynman przewidując, że klasyczne komputery nie będą w stanie rozwiązać wielu problemów, opracował podstawy komputerów kwantowych. Mistrz uwzględnienia innej perspektywy / innego punktu widzenia. Poniżej kilka cytatów autorstwa Feynmana wraz z wybranymi wywiadami / wykładami. Szczególnie polecam serię "Fun to imagine" zarejestrowaną przez BBC w roku 1983 - a najbardziej część "Why?" 🙂

Richard Feynman - źródło Wikipedia

"Widzisz tego ptaka? - mówił. - To gajówka Spencera (wiedziałem, że nie zna prawdziwej nazwy). - Widzisz, po włosku to jest Chutto Lapittida. Po portugalsku - Bom da Peida. Po chińsku - Chung-long-tah, a po japońsku - Katano Tekeda. Możesz poznać nazwy tego ptaka we wszystkich językach świata, ale kiedy już się ich nauczysz, nie będziesz miał o nim bladego pojęcia. Będziesz tylko wiedział, że ludzie w różnych miejscach świata tak go nazywają. Więc popatrzmy sobie na ptaszka i zobaczmy, co robi, bo to się właśnie liczy. (Bardzo wcześnie nauczyłem się, jaka jest różnica między poznaniem nazwy jakiegoś przedmiotu a wiedzą o nim)."

Richard Feynman

 

"Bo to jest tak, że ja muszę rozumieć świat."

Richard Feynman

 

"Jest coś niedobrego z ludźmi: nie uczą się przez zrozumienie, tylko jakoś inaczej, pewnie na pamięć. Ich wiedza jest taka krucha!"

Richard Feynman

 

"Temu, kto nie zna matematyki, trudno spostrzec głębokie piękno przyrody."

Richard Feynman

 

"Nauka to wiara w ignorancję ekspertów."

Richard Feynman

 

"Przecież myślenie to tak, jakby się mówiło do siebie, w środku."

Richard Feynman

 

"Nie wydaje mi się, by ten fantastycznie cudowny wszechświat, ta ogromna przestrzeń istniejąca przez tyle czasu oraz różne gatunki zwierząt, wszystkie te rozmaite planety i atomy z wszystkimi ich ruchami, i tak dalej, aby ten cały skomplikowany świat był jedynie sceną stworzoną po to, by Bóg mógł obserwować ludzi walczących o dobro i zło - a taki jest właśnie pogląd religijny. Ta scena jest zbyt duża jak na ten dramat. "

Richard Feynman

 

"Wydaje mi się, że znacznie ciekawiej jest żyć nie wiedząc, niż znać odpowiedzi, które mogą być błędne."

Richard Feynman

 

Pozdrowienia,

Mariusz Gromada

Receiver Operating Characteristic - Krzywa ROC - czyli ocena jakości klasyfikacji (część 7)

Receiver Operating Characteristic - Krzywa ROC - geneza nazwy

Termin "Krzywa ROC" wywodzi się z teorii detekcji sygnałów, której zadaniem jest odróżnienie sygnału będącego informacją (np. sygnały z maszyn / urządzeń elektronicznych, bodźce pochodzące z organizmów żywych) od wzorców przypadkowych nie zawierających informacji (szum, tło, aktywność losowa). Pierwsze wykorzystanie krzywej ROC datuję się na okres II Wojny Światowej. Po ataku na Pearl Harbor w 1941, USA zaczęły poszukiwać lepszej metody analizy sygnałów radarowych w celu zwiększenia wykrywalności Japońskich samolotów.

Receiver Operating Characteristic - Krzywa ROC - definicja

W statystyce matematycznej krzywa ROC jest graficzną reprezentacją efektywności modelu predykcyjnego poprzez wykreślenie charakterystyki jakościowej klasyfikatorów binarnych powstałych z modelu przy zastosowaniu wielu różnych punktów odcięcia. Mówiąc inaczej - każdy punkt krzywej ROC odpowiada innej macierzy błędu (zobacz tutaj) uzyskanej przez modyfikowanie "cut-off point" (zobacz tu). Im więcej różnych punktów odcięcia zbadamy, tym więcej uzyskamy punktów na krzywej ROC. Finalnie na wykres nanosimy TPR (True-Positive Rate - oś pionowa) oraz FPR (False-Positive Rate - oś pozioma).

c - punkt odcięcia

\quad c\mapsto \Big(x(c),y(c)\Big)=\Big(FPR(c),TPR(c)\Big)

Krzywa ROC - Receiver Operating Characteristic

Krzywa ROC, będąc funkcją punktu odcięcia, przedstawia zmienność TPR (miary pokrycia / wychwycenia klasy faktycznie pozytywnej) w zależności od FPR (poziomu błędu popełnianego na klasie faktycznie negatywnej). Jak zawsze chodzi o pewien kompromis, tzn. dobierając "cut-off" chcemy maksymalizować TPR "trzymając w ryzach" błąd FPR. Analiza relacji TPR(FPR) jest niezwykle przydatna, ale najpierw przypomnijmy kilka podstawowych definicji.

Krótkie przypomnienie podstawowych definicji

Macierz błędu

TPR, TNR, PPV, NPV

TPR True-Positive Rate (czyli czułość)

TPR=\frac{TP}{TP+FN}=P(pred=P|fakt=P)=

=P(pred=1|fakt=1)=P(1|1)

FPR False-Positive Rate (czyli 1-specyficzność)

FPR=\frac{FP}{FP+TN}=P(pred=P|fakt=N)=

P(pred=1|fakt=0)=P(1|0)=1-P(0|0)=1-TNR

Interpretacja ROC

ROC - Klasyfikator teoretycznie idealny + Klasyfikator losowy

Klasyfikator teoretycznie idealny reprezentowany jest przez punkt (0,1), natomiast klasyfikatory powstałe z modelu losowego "leżą" na prostej TPR=FPR.

Krzywa ROC - Interpretacja - Receiver Operating Characteristic

 

ROC - Punkt równowagi (czułość = specyficzność)

Punkt równowagi leży na przecięciu ROC z prostą TPR = 1-FPR = TNR i reprezentuje "cut-off" point, dla którego klasyfikator osiąga równowagę czułość = specyficzność.

Krzywa ROC - Punkt równowagi - Receiver Operating Characteristic

 

ROC - Współczynnik Giniego

Współczynnik Giniego to pole powierzani pomiędzy krzywą ROC dla badanego modelu oraz krzywą ROC dla modelu losowego w interpretacji procentowej do wartości 1/2 - czyli pola powierzchni dla klasyfikatora teoretycznie idealnego. Współczynnik Giniego jest doskonałą miarą jakości modelu i może być interpretowany jako % "idealności" danego modelu predykcyjnego.

Krzywa ROC - Współczynnik Giniego - Receiver Operating Characteristic

  • Im większy wskaźnik Giniego tym lepiej
  • Wartość wskaźnika Giniego nie zależy od apriori (teoretycznie), w praktyce trudniej o silny model jeśli apriori jest duże
  • Gini = 100% dla modelu teoretycznie idealnego
  • Gini = 0% dla modelu losowego

 

Pole powierzani pod krzywą ROC - AUC, AUROC

Tym razem wyznaczamy całość pola powierzchni pod wykresem ROC odnosząc wartość do analogicznego pola dla modelu idealnego - w tym przypadku pola kwadratu o boku 1. Interpretacja AUROC (Area Under the ROC) to prawdopodobieństwo, że badany model predykcyjny oceni wyżej (wartość score) losowy element klasy pozytywnej od losowego elementu klasy negatywnej.

Krzywa ROC - AUROC - Receiver Operating Characteristic

  • Im większy wskaźnik AUROC tym lepiej
  • Wartość AUROC nie zależy od apriori (teoretycznie), w praktyce trudniej o silny model jeśli apriori jest duże
  • AUROC = 100% dla modelu teoretycznie idealnego
  • AUROC = 50% dla modelu losowego
  • AUROC = 0% dla modelu idealnego klasy przeciwnej do pozytywnej

 

Ciąg dalszy nastąpi ...

Pozdrowienia,

Mariusz Gromada

Virtual Reality 3D Graphing Calculator na bazie mXparser

Virtual Reality 3D Graphing Calculator

W ostatnim czasie powstał bardzo ciekawy projekt edukacyjny o nazwie "Virtual Reality 3D Graphing Calculator", który umożliwia poznawanie matematyki poprzez zabawę i niemal fizyczną interakcję z wykresami różnych funkcji. Oprogramowanie powstało na bazie gogli wirtualnej rzeczywistości (Oculus Rift), sensora ruchu dłoni / palców (Leep Motion Controller) oraz parsera / silnika matematycznego mojego autorstwa (mXparser).

mXparser - mathparser.org

Autorem projektu są studenci z College of Coastal Georgia, inicjatywą opiekuje się German Vargas, Ph.D., Assistant Vice President for Academic Student Engagement, Associate Professor of Mathematics College of Coastal Georgia, One College Drive, Brunswick, GA 31520.

VR 3D Calculator można pobrać tutaj.

Poniżej również filmy prezentujące działanie kalkulatora.

Pozdrowienia,

Mariusz Gromada

Fraktalne oblicze natury - czyli geometria fraktalna (część 1)

Cykl poświęcony geometrii fraktalnej rozpoczynam od kilku genialnych cytatów oraz, idąc za radą Benoita Mandelbrota, koniecznie podając grafiki / wizualizacje / zdjęcia.

"Geometria fraktalna sprawi, że inaczej spojrzysz na świat. Ostrzegam - zgłębianie tej wiedzy wiąże się z niebezpieczeństwem. Ryzykujesz utratę części wyobrażeń z dzieciństwa - szczególnie tych dotyczących chmur, lasów, kwiatów, galaktyk, liści, piór, skał, gór, potoków, i wielu innych. Twoja interpretacja przyrody zmieni się całkowicie i na zawsze."

Michael F. Barnsley

 

"W kwestii fraktali zobaczyć znaczy uwierzyć"

Benoit Mandelbrot

 

"Fraktal to zbiór matematyczny (lub inny obiekt ) charakteryzujący się w każdej skali wysoką nieregularnością oraz dużą fragmentacją."

Benoit Mandelbrot

 

"Ostatnie lata rozwoju matematyki, fizyki, biologii, astronomii oraz ekonomii dostarczyły nowego sposobu rozumienia ciągle rosnącej złożoności natury. Ta nowa dziedzina nauki, nazywana teorią chaosu, pozwala dostrzec porządek oraz wzorce gdzie dawnej dominowała losowość, niekonsekwencja, nieprzewidywalność - w skrócie obserwowany był chaos."

James Gleick

 

Dla wielu termin fraktal kojarzy się z niezwykle pięknym zbiorem Mandelbrota, a wszystko za sprawą szeregu prostych programów komputerowych służących do jego wizualizacji. Jestem pewien, że znaczna część programistów rozpoczynała swoją przygodę z kodowaniem od programu generującego wspomniany zbiór - jednym z nich byłem ja! Dziś jednak nie będę skupiał się na osobie Benoita Mandelbrota - na to przyjdzie jeszcze czas. Zaznaczę natomiast, że był postacią o chyba największym wpływie na rozwój nowej dziedziny geometrii, geometrii przyrody.

Czym jest fraktal?

Nie istnieje jedna precyzyjna definicja fraktali. W zamian wymienia się cechy obiektów fraktalnych - najważniejsze to:

  • Samo-podobieństwo - tzn. w skład obiektu wchodzą jego "mniejsze kopie (lub przybliżone kopie)" - np. liść paproci.
  • Nietrywialna struktura w każdej skali - tzn. powiększanie ujawnia kolejne równie skomplikowane formy - np. drzewo, konary / gałęzie.
  • Niecałkowity (a nawet niewymierny) wymiar fraktalny - ten koncept wyjaśnimy szczegółowo później, chodzi np. o nieskończenie długą krzywą zamkniętą, która jest osadzona w ograniczonej przestrzeni (obiekt o typie "pomiędzy" linią a płaszczyzną)  - przykład rzeczywisty to chociażby linia brzegowa i pomiar jej długości - im  mniejsza skala pomiaru tym istotnie większy wynik.

Historia fraktali

Pierwsza część cyklu to jedynie wstęp - dlatego podaję główne nazwiska (w kolejności chronologicznej), które istotnie przyczyniły się do rozwoju geometrii fraktalnej. Są to wybitni matematycy i dlatego każdemu z nich poświęcę osobny wpis.

Fraktale w naturze - rośliny

Fraktale w naturze - rośliny

Fraktale w naturze - rośliny

Fraktale w naturze - krajobraz

Fraktale w naturze - krajobraz / góry

Fraktale w naturze - krajobraz / powierzchnia ziemi

Fraktale w naturze - biologia / ciało człowieka

Fraktale w naturze - ciało człowieka / płuca

Fraktale w naturze - ciało człowieka / oko

Fraktale w naturze - bilogia / kolonie bakterii

Fraktale w naturze - biologia / kolonie bakterii

Fraktale w naturze - biologia / kolonie bakterii

Fraktale w naturze - fizyka / materia / energia

Fraktale w naturze - fizyka / kryształ

Fraktale w naturze - ekonomia / wyładowanie elektryczne

Fraktale w naturze - astronomia / kosmologia

Fraktale w naturze - astronomia / galaktyka

Fraktale w naturze - astronomia / powierzchnia księżyca

Fraktale w naturze - ekonomia

Fraktale w naturze - ekonomia / trend

Fraktale w naturze - ekonomia / trend

Ciąg dalszy nastąpi ... 🙂

Pozdrowienia,

Mariusz Gromada