Tetracja i nieskończona wieża wykładnicza

Tetracja - definicja

Tetracja (wieża wykładnicza, super-potęgowanie, iterowane potęgowanie, 4 hiper-operator)

Tetracja to działanie dwuargumentowe definiowane jako wielokrotne potęgowanie elementu przez siebie.

Definicja: dla dowolnej liczby rzeczywistej a>0 i nieujemnej liczby całkowitej n\geq 0 tetrację n liczby a definiujemy jako:

{^{n}a}=\begin{cases}1&\text{dla}\quad n=0\\a&\text{dla}\quad n=1\\ \underbrace{a^{a^{\cdots^{a}}}}_{n}&\text{dla}\quad n>1\end{cases}

Przykłady

{^{3}2}=2^{2^2}=2^{(2^2)}=2^4=16

{^{4}2}=2^{2^{2^2}}=2^{(2^{(2^2)})}=2^{(2^{4})}=2^{16}=65536

{^{3}3}=3^{3^3}=3^{(3^3)}=3^{27}=7625597484987

{^{4}3}=3^{3^{3^3}}=3^{(3^{(3^3)})}=3^{(3^{27})}=3^{7625597484987}=\ldots liczba składająca się z 3638334640025 cyfr 🙂

Tetrację można wykorzystać do zapisu naprawdę dużych liczb, co dobrze obrazuje przykład {^{4}3}. Tetrację wygodnie jest również definiować w postaci rekurencyjnej.

Definicja rekurencyjna: dla dowolnej liczby rzeczywistej a>0 i nieujemnej liczby całkowitej n\geq 0 tetrację n liczby a definiujemy jako:

{^{n}a}=\begin{cases}1&\text{dla}\quad n=0\\a^{{^{n-1}a}}&\text{dla}\quad n\geq 1\end{cases}

Czytaj dalej

Matematyka w obrazkach #17 - Pitagoras vs Einstein

Po dłuższej przerwie zaczynam od czegoś lekkiego - dziś w cyklu "Matematyka w obrazkach" pojedynek geometrii euklidesowej ze szczególną teorią względności 🙂

Pitagoras vs Einstein

Ciekawostki o pewnych równoważnościach:

  • Twierdzenie Pitagorasa jest równoważne z V aksjomatem geometrii euklidesowej, (tzw. Postulatem Euklidesa, inaczej postulatem równoległości).
  • E=mc^2 wywodzi się ze szczególnej teorii względności opracowanej przez Alberta Einsteina przedstawiając dwa różne typy równoważności masy i energii:
    • Równoważność masy spoczynkowej i energii spoczynkowej.
    • Równoważność masy relatywistycznej i energii całkowitej.
  • Ogólna teoria względności jest uogólnieniem szczególnej teorii względności. Korzysta ona między innymi z metod geometrii nieeuklidesowej (np. stwierdzenie, że siła grawitacji wynika z lokalnej geometrii czasoprzestrzeni). Zatem, w pewnym sensie, powyższy pojedynek to starcie między geometrią euklidesową a geometrią nieeuklidesową 🙂

Pozdrowienia,

Mariusz Gromada

MathSpace.pl - kilkumiesięczna przerwa w publikacjach

Ostatni post opublikowałem w dniu 27.02.2017, był to wpis na temat wskaźnika Giniego. Minął już ponad kwartał i być może niektórzy z Was są zainteresowani "dlaczego chwilowo wyciszyłem swoją aktywność". Otóż - nie wyciszyłem 🙂 Poniżej wyjaśniam o co chodzi.

https://github.com/mariuszgromada

MathParser.org-mXparser - 2017 - commits - GitHub

 

MathParser.org-mXparser

Od ponad 3 miesięcy intensywnie rozwijam projekt MathParser.org-mXparser. Przez ten okres:

  • Przygotowałem release v.4.0.0: cała masa nowych funkcjonalności (w tym: operatory bitowe, notacja naukowa, wsparcie dla jednostek).
  • Przygotowałem release v.4.0.2: port biblioteki wspierając tym samym wiele nowych platform (.NET Core, .NET Standard, .NET PCL, Xamarin.iOS, Xamarin.Android).
  • Pracowałem nad wersją v.4.1-Aeries: głównie wsparcie dla innych (niż z podstawą 10) systemów numerycznych, ale również szereg nowych bardzo przydatnych rozszerzeń API (w tym: praca z wbudowanymi tokenami, rozpoznawanie prawdopodobnych typów dla tokenów niezdefiniowanych). Aeries jest już w 70% zrealizowane - potrzebuję jeszcze około 2 tygodni.

# SLOC

Linie kodu nie są jakimś super wskaźnikiem, ale nic lepszego w tej chwili nie mam. Poniżej tabelka "zmiany stanu" 🙂

# sloc - przed # sloc - obecnie
Java - src 17522 27905
Java - komentarze 9864 12809
C# - src 17605 28193
C# - komentarze 9778 12215

MathParser.org-mXparser w liczbach

  • Do dziś (11.06.2017) - około 12 tys. pobrań, 91 polubień / 24 forki na GitHub,
  • Średnio około 50 pobrań dziennie.
  • Do dziś (11.06.2017)  2351 plików na GitHub, które odnoszą się do mXparser.

Pozdrowienia,

Mariusz Gromada

Wskaźnik Giniego na bazie wartości oczekiwanej - czyli ocena jakości klasyfikacji (część 19)

W trakcie minionej nocy, około godziny 02:00, miałem nagły przebłysk 🙂 Jakoś tak, nie wiem dlaczego, przypomniałem sobie pewną zależność dla wartości oczekiwanej zmiennej losowej o wartościach nieujemnych. Zdałem sobie sprawę, że na tej podstawie, jestem w stanie opracować twierdzenie dotyczące wskaźnika Giniego (dla modelu predykcyjnego), dające elegancką postać oraz łatwe narzędzie jego estymacji. Wzór, który wyprowadziłem, bazuje na wartości oczekiwanej, dającej się z powodzeniem przybliżyć średnią (np. w SQL). Zaczynamy część #19 cyklu "Ocena jakości klasyfikacji", jest to "hardcorowy" wpis z serii "Tips & Tricks na krzywych" 🙂 Zapraszam!

Zmienna losowa reprezentująca rząd kwantyla (pozycję) elementu w populacji

  • Niech będzie dana zmienna losowa Q\in[0;1], której wartość reprezentuje rząd kwantyla odpowiadający danemu elementowi, gdzie porządek jest dany malejącą oceną modelem. Inaczej - Q to frakcja bazy.
  • Niech y\in\{0,1\} oznacza klasę faktyczną.
  • Rozważmy zmienne losowe: Q|y=1 oraz Q|y=0.
  • W częściach #13 oraz #14 wykazałem, że zmienne Q|y=1 oraz Q|y=0 są opisane funkcjami gęstości podanymi przez: lifty nieskumulowane odpowiednio dla klasy "1" oraz klasy "0".
  • Również w częściach #13 oraz #14 wykazałem, że zmienne Q|y=1 oraz Q|y=0 są opisane dystrybuantami podanymi przez: odpowiednio TPR dla klasy "1" oraz TNR dla klasy "0" (tam te funkcje nazywałem Captured Response).
  • W części #15 wykazałem, że wskaźniki Giniego, zdefiniowane osobno dla klasy "1" oraz klasy "0", są sobie równe - grafika poniżej.

Równość wskaźników Giniego

  • Również w części #15 pokazałem, że

Gini=\frac{2G_1}{1-apriori}=\frac{2G_0}{apriori}

  • Z powyższego, po drobnych przekształceniach

G_1=\frac{(1-apriori)\times Gini}{2}

G_0=\frac{apriori\times Gini}{2}

Wartość oczekiwana zmienne losowej o wartościach nieujemnych

Poniższą zależność pamiętam z analizy przeżycia, gdzie średnią długość przeżycia liczono jako całkę pod funkcją przeżycia 🙂 Każda funkcja przeżycia ma postać S(t)=1-F(t), gdzie F to pewna dystrybuanta.

Twierdzenie: Jeśli zmienna losowa X, o ciągłym rozkładzie, przyjmuje wartości nieujemne to:

EX=\displaystyle\int_0^\infty P(X\geq x)dx

Zakładając, że F jest dystrybuantą zmiennej X, bazując na ciągłości rozkładu, możemy zapisać

EX=\displaystyle\int_0^\infty \Big(1-F(x)\Big)dx

W takim przypadku wartość oczekiwana to pole powierzchni "nad" dystrybuantą ograniczone prostą o wartości 1.

Wskaźniki Giniego na bazie E(Q|y=1)

Załóżmy, że Q|y=1 ma rozkład ciągły, wtedy

E(Q|y=1)=\displaystyle\int_0^1\Big(1-TPR(q)\Big)dq

Wartość oczekiwana dla klasy pozytywnej

Ale

\displaystyle\int_0^1\Big(1-TPR(q)\Big)dq=\frac{1}{2}-G_1

Więc

E(Q|y=1)=\frac{1}{2}-G_1

Podstawiając

E(Q|y=1)=\frac{1}{2}-G_1=

=\frac{1}{2}-\frac{(1-apriori)\times Gini}{2}

E(Q|y=1)=\frac{1-(1-apriori)\times Gini}{2}

Przekształcając

2\times E(Q|y=1)=1-(1-apriori)\times Gini

(1-apriori)\times Gini=1-2\times E(Q|y=1)

Twierdzenie:

Gini=\frac{1-2\times E(Q|y=1)}{1-apriori}

Wow - wystarczy średni rząd kwantyla na targecie pozytywnym i apriori 🙂

Wskaźniki Giniego na bazie E(Q|y=0)

Załóżmy, że Q|y=0 ma rozkład ciągły, wtedy

E(Q|y=0)=\displaystyle\int_0^1\Big(1-TNR(q)\Big)dq

Wartość oczekiwana dla klasy negatywnej

Ale

\displaystyle\int_0^1\Big(1-TNR(q)\Big)dq=\frac{1}{2}+G_0

Więc

E(Q|y=0)=\frac{1}{2}+G_0

Podstawiając

E(Q|y=0)=\frac{1}{2}+G_0=

=\frac{1}{2}+\frac{apriori\times Gini}{2}

E(Q|y=0)=\frac{1+apriori\times Gini}{2}

Przekształcając

2\times E(Q|y=0)=1+apriori\times Gini

apriori\times Gini=2\times E(Q|y=0)-1

Twierdzenie:

Gini=\frac{2\times E(Q|y=0)-1}{apriori}

Wow - tym razem wystarczy średni rząd kwantyla na targecie negatywnym i apriori 🙂

Wniosek:

\frac{1-2\times E(Q|y=1)}{1-apriori}=\frac{2\times E(Q|y=0)-1}{apriori}

Przypadki graniczne

Gini dla modelu losowego powinien wynosić 0, a dla modelu teoretycznie idealnego oczekujemy wartości 1 - sprawdźmy.

Wartość oczekiwana dla przypadków skrajnych

Model losowy

  • E(Q|y=1)=0.5
  • E(Q|y=0)=0.5

Gini=\frac{1-2\times E(Q|y=1)}{1-apriori}=

=\frac{1-2\times 0.5}{1-apriori}=

=\frac{0}{apriori}=0 - jest ok 🙂

Gini=\frac{2\times E(Q|y=0)-1}{apriori}=

=\frac{2\times 0.5-1}{apriori}=

=\frac{0}{apriori}=0 - jest ok 🙂

Model teoretycznie idealny

  • E(Q|y=1)=\frac{apriori}{2}
  • E(Q|y=0)=\frac{aprior+1}{2}

Gini=\frac{1-2\times E(Q|y=1)}{1-apriori}=

=\frac{1-2\times\frac{apriori}{2}}{1-apriori}=

=\frac{1-apriori}{1-apriori}=1 - jest ok 🙂

Gini=\frac{2\times E(Q|y=0)-1}{apriori}=

=\frac{2\times\frac{aprior+1}{2}-1}{apriori}=

=\frac{apriori+1-1}{apriori}=1 - jest ok 🙂

Uwaga praktyczna

Jeśli model predykcyjny zwraca dużo nieunikalnych wartości, licząc rząd kwantyla, warto zastąpić go rzędem na bazie pozycji elementu - inaczej wyniki na bazie średniej mogą być nieprzewidywalne (szczególnie dla małych apriori). Wzory testowane na realnych danych 🙂

Pozdrowienia 🙂

Mariusz Gromada

TPR i FNR na bazie Liftu Skumulowanego - czyli ocena jakości klasyfikacji (część 18)

Część #18 cyklu "Ocena jakości klasyfikacji" to pogłębienie interpretacji krzywej Liftu Skumulowanego - mam wrażenie, że to już ostatni wpis z serii "Tips & Tricks na krzywych".

TPR (Captured Response) i FNR na bazie Liftu Skumulowanego

Dla modelu idealnego krzywa liftu skumulowanego przyjmuje następującą postać:

Lift.Skum(q)=\begin{cases}\frac{1}{apriori}&\text{dla}\quad q\leq apriori\\\frac{1}{q}&\text{dla}\quad q>apriori\end{cases}

q - kwantyl (rząd) bazy (malejąco względem oceny modelem)

Stosując technikę "przedłużania modelu idealnego", analogicznie do zastosowanej w części #17 "PPV i FDR na bazie TPR", tworzymy "skalę" umożliwiającą wyznaczenie TPR (True-Positive Rate) oraz FNR (False-Negative Rate).

TPR i FNR na bazie Liftu Skumulowanego

Zależności

TPR(q)=q\times Lift.Skum(q)=\frac{A}{B}

A=Lift.Skum(q)

B=\frac{1}{q}

Dowód: w części #11 "Captured Response vs Lift" pokazałem, że

\frac{CR(q)}{q}=Lift.Skum(q)

ale CR(q) to to samo co TPR(q) - różni się tylko nazwą 🙂

Nieco inny dowód podałem również w części #17 "PPV i FDR na bazie TPR"

PPV(q)=\frac{apriori\times TPR(q)}{q}

trochę przekształcając otrzymujemy

\frac{PPV(q)}{apriori}\times q=TPR(q)

Dalej wystarczy zauważyć, że

\frac{PPV(q)}{apriori}=Lift.Skum(q)

cbdo. 🙂

I ponownie - wydaje mi się, że analogicznie można naszkicować TNR oraz FPR - tylko tu analizując: klasyfikację do klasy negatywnej, krzywą Liftu Skumulowanego dla klasy "0" oraz "przedłużenie" modelu idealnego dla klasy "0" - wymaga sprawdzenia 🙂

Pozdrowienia,

Mariusz Gromada

PPV i FDR na bazie TPR (Captured Response) - czyli ocena jakości klasyfikacji (część 17)

W części #17 cyklu "Ocena jakości klasyfikacji" wydobędę kolejne informacje z krzywej Captured Response, która, na pierwszy rzut oka, prezentuje wyłącznie TPR (True-Positive-Rate). Kontynuuję zatem serię "Tips & Tricks na krzywych".

Prawdopodobieństwo skumulowane (PPV, PRECISION) na bazie TPR czyli Captured Response

Dla modelu idealnego krzywa Captured Response ma postać

Capt.Resp(q)=\begin{cases}\frac{q}{apriori}&\text{dla}\quad q\leq apriori\\1&\text{dla}\quad q>apriori\end{cases}

q - kwantyl (rząd) bazy (malejąco względem oceny modelem)

Rozważając "przedłużenie pierwszej części" definicji na cały odcinek [0;1] otrzymujemy "skalę", na bazie której łatwo wyznaczyć PPV (Positive Predicted Value) oraz FDR (False Discovery Rate).

PPV=\frac{TP}{TP+FP}

FDR=\frac{FP}{TP+FP}=1-PPV

TPR, TNR, PPV, NPV

Zależności

PPV(q)=\frac{apriori\times TPR(q)}{q}

FDR(q)=1-PPV(q)=1-\frac{apriori\times TPR(q)}{q}

q - cut-off jako kwantyl (rząd) bazy (malejąco względem oceny modelem)

PPV i FDR na bazie TPR - Captured Response

Dowód: zaczynamy od oznaczeń

  • N=N_1+N_0 - liczba obiektów w populacji: total, z klasy pozytywnej "1", z klasy negatywnej "0";
  • q - cut-off (jako kwantyl - a dokładnie jego rząd - względem malejącej oceny modelem);
  • [0,q] - klasyfikacja pozytywna;
  • (q,1] - klasyfikacja negatywna;
  • n_1 - true positive;
  • n_0 - false positive;
  • n=n_1+n_0
  • q=\frac{n}{N}
  • apriori=\frac{N_1}{N}

PPV(q)=\frac{n_1}{n}

A=TPR(q)=\frac{n_1}{N_1}

C=\frac{q}{apriori}=\frac{n}{N}\times\frac{N}{N_1}=\frac{n}{N_1}

\frac{A}{C}=\frac{n_1}{N_1}\times\frac{N_1}{n}=\frac{n_1}{n}

\frac{A}{C}=PPV(q)

\frac{A}{C}=TPR(q)\times\frac{apriori}{q}=\frac{apriori\times TPR(q)}{q}

PPV(q)=\frac{apriori\times TPR(q)}{q}

cbdo. 🙂

Wydaje mi się, że analogicznie można wyznaczyć NPV - tylko tu analizując: klasyfikację do klasy negatywnej, krzywą Captured Response dla klasy "0" (TNR) oraz "przedłużenie" modelu idealnego dla klasy "0" - sprawdzimy 🙂

Pozdrowienia,

Mariusz Gromada

"Sympatyczny" punkt przecięcia - czyli ocena jakości klasyfikacji (część 16)

Do napisania 16 części cyklu "Ocena jakości klasyfikacji" zainspirował mnie Kolega i dawny współpracownik! Michał - dzięki za "hint" 🙂 Dziś wskażę pewien sympatyczny punkt przecięcia, którego znajomość jest przydatna, a już z pewnością można "zaszpanować" 🙂 Wpis stanowi zdecydowane wzbogacenie serii "Tips & Tricks na krzywych".

Krzywe Captured Response (TPR) i prawdopodobieństwo skumulowane (PPV, Precision) przecinają się w punkcie a-priori 🙂

TPR vs Precision

Dowód: zaczynamy od oznaczeń:

  • N=N_1+N_0 - liczba obiektów w populacji: total, z klasy pozytywnej "1", z klasy negatywnej "0";
  • q - cut-off (jako kwantyl - a dokładnie jego rząd - względem malejącej oceny modelem);
  • [0,q] - klasyfikacja pozytywna;
  • (q,1] - klasyfikacja negatywna;
  • n_1(q) - true positive;
  • n_0(q) - false positive;
  • n(q)=n_1(q)+n_0(q)=q\cdot N

Wtedy

TPR(q)=CR_1(q)=\frac{n_1(q)}{N_1}=\frac{n_1(q)}{apriori\times N}

PPV(q)=P\big(~1~|~[0,q]~\big)=\frac{n_1(q)}{n(q)}=\frac{n_1(q)}{qN}

Porównując

PPV(q)=TPR(q)

\frac{n_1(q)}{qN}=\frac{n_1(q)}{apriori\times N}

Zakładając, że n_1(q)\neq 0

q=apriori

cbdo 🙂

Do czego "sympatyczny" punkt przecięcia może się przydać?

Znajomość punktu przecięcia może się przydać do weryfikacji poprawności analizowanych wykresów i ich spójności z założeniami. Przykładowo - jeśli analityk na jednym wykresie naniesie Captured Response wraz z modelem idealnym, następnie do wykresu doda p-ństwo skumulowane (czyli PPV), i jeśli te krzywe przetną się w innym punkcie niż "aprirori", to gdzieś mamy błąd! Być może prezentowane wykresy przedstawiają różne modele?

Pozdrowienia,

Mariusz Gromada

Matematyka w obrazkach #16 - Mathistopheles - Atraktor Lorenza :-)

Dziś, przeglądając Twittera, natknąłem się na profil @Mathistopheles - Thomas Oléron Evans. Zdjęcie profilowe jest genialne - wykonane na bazie Atraktora Lorenza - musiałem dodać do cyklu "Matematyka w obrazkach" 🙂 Równie ciekawe jest zdjęcie w tle 🙂

Atraktor Lorenza

Pozdrowienia,

Mariusz Gromada

Personalizowany kubek MathSpace.PL :-)

Kubek na bazie motywu "Matematyka w obrazkach #11 - Dobre argumenty to podstawa". Kubek wygląda świetnie 🙂

Personalizowany kubek MathSpace.PL

Personalizacja kubka

  • Imię / nick / ... w chmurce;
  • Dedykowany wzór / formuła w chmurce;

Jak otrzymać kubek?

Warunki, które musisz spełnić:

  • Polubienie profilu MathSpace.PL na Facebooku lub Twitterze lub subskrypcja newslettera;
  • Przesłanie wiadomości (Facebook, Twitter, mail) o chęci zamówienia kubka + opis personalizacji;
  • Zapoznanie się z procesem zamówienia kubka.

Jak wygląda proces zamówienia kubka?

  • Jestem autorem projektu + dokonuję wskazanej personalizacji;
  • Kubki zamawiam w Waszym imieniu poprzez fotokubek.net: kubek biały reklamowy 330 ml z nadrukiem;
  • Nie zarabiam na kubkach!!! Zamawiając poniesiesz opłatę zgodnie z cennikiem fotokubek.net + koszt wysyłki;
  • Otrzymujesz kubek, nie udostępniam projektu (graficznego) kubka;
  • Dodatkowe informacje w indywidualnej korespondencji.

Pozdrowienia,

Mariusz Gromada