Matematyka w obrazkach #19 - Oko Mandelbrota

W cyklu "Matematyka w obrazkach" - nowe logo MathSpace.pl

Motywacja

Motywując postać nowego logo przytoczę cytaty, którymi posłużyłem się otwierając serię o "Geometrii fraktalnej" - wpis "Fraktalne oblicze natury".

"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

 

Pozdrowienia,

Mariusz Gromada

Egzotyczna hiperkula - czyli o pomiarach w przestrzeni wielowymiarowej

"Jak oczami wyobraźni zobaczyć 4 wymiary? - zapytano matematyka.
To proste - odpowiedział - wystarczy wyobrazić sobie n-wymiarów i podstawić n=4"
🙂

Hipersześcian i Hiperkula - rzut

Dzisiejszy wpis poświęcę pomiarom odległości, powierzchni i pojemności w przestrzeniach wielowymiarowych. N-wymiarowa przestrzeń euklidesowa dostarcza dosyć oczywistą metrykę - a przez to wydawałoby się - bardzo intuicyjną. To wrażanie jest jednak mylne, co łatwo pokazać analizując wpływ zwiększania liczby wymiarów na dokonywane pomiary. Jak w zależności od liczby wymiarów zmienia się powierzchnia i objętość kuli? Analogicznie - jak zmienia się maksymalna odległość pomiędzy wierzchołkami kostki? Obiecuję - odpowiedzi będą zaskakujące 🙂

Możesz mieć wrażenie, że to wyłącznie abstrakcyjne rozważania. Czy na pewno? Ja w zasadzie na co dzień analizuję Klientów opisanych szeregiem miar. Poszukiwanie podobieństw, skupień, segmentów czy "najbliższych sąsiadów" niemal w całości opiera się na wielowymiarowej metryce euklidesowej. Zapraszam do pogłębienia wiedzy w tym obszarze:-) Zapewniam - warto!

Przestrzeń kartezjańska \mathbb{R}^n

Przestrzeń euklidesowa R^n

Przestrzeń kartezjańska \mathbb{R}^n to przestrzeń współrzędnych rzeczywistych

(x_1, x_2, \ldots, x_n)\in\mathbb{R}^n

z określoną metryką

d(\mathbb{x},\mathbb{y})=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}

gdzie

\mathbb{x}=(x_1, x_2, \ldots, x_n)\in\mathbb{R}^n

\mathbb{y}=(y_1, y_2, \ldots, y_n)\in\mathbb{R}^n

Można powiedzieć, że metryka euklidesowa to pewna forma twierdzenia Pitagorasa.

Hipersześcian

Dla uproszczenia zdefiniujemy hipersześcian o długości boku a, którego jeden z wierzchołków to punkt 0, a inne wierzchołki składają się ze współrzędnych nieujemnych.

Hipersześcian o boku długości a to zbiór punktów

\mathbb{x}=(x_1, x_2, \ldots, x_n)\in\mathbb{R}^n

Spełniających zależność

\begin{cases}0\leq x_1\leq a\\0\leq x_2\leq a\\ \cdots\\0\leq x_n\leq a\end{cases}

Hipersześcian - wymiar od 1 do 4

Odcinek powstaje z "przesunięcia" punktu w dodatkowym nowym wymiarze. Kwadrat powstaje z odcinka poprzez "przesunięcie" odcinka w dodatkowym nowym wymiarze. Kostka powstaje z kwadratu poprzez przesunięcie kwadratu w dodatkowym nowym wymiarze. W tym postępowaniu uwidacznia się zależność rekurencyjna.

Hiperkula

Hiperkula to uogólnienie pojęcia kuli na n-wymiarów przy rozważaniu punktów w przestrzeni euklidesowej \mathbb{R}^n. Ponownie, dla uproszczenia, założymy, że środkiem kuli jest punkt 0.

Hiperkula o promieniu r to zbiór punktów

\mathbb{x}=(x_1, x_2, \ldots, x_n)\in\mathbb{R}^n

Spełniających zależność

d(0,\mathbb{x})=\sqrt{\sum_{i=1}^n x_i^2}\leq r

Hiperkula - wymiar od 1 do 4

Odcinek powstaje z "przesunięcia" punktu w dodatkowym nowym wymiarze. Koło powstaje z odcinka poprzez "przesunięcie" odcinka (jednocześnie odcinek zmienia długość) w dodatkowym nowym wymiarze. Kula powstaje z koła poprzez przesunięcie koła (jednocześnie koło zmienia promień) w dodatkowym nowym wymiarze. Ponownie w tym postępowaniu uwidacznia się zależność rekurencyjna, którą niebawem wykorzystamy.

Przydatna całka \displaystyle\int_{-r}^r\Big(r^2-x^2\Big)^y dx

Wszelkie niezbędne wzory będę wyznaczał korzystając z elementarnych całek. W okręgach, kołach, kulach często pojawiają się równania postaci (r^2-x^2)^y. Poniżej wyznaczę ogólny i pomocny wzór na całkę oznaczoną:

\displaystyle\int_{-r}^r\Big(r^2-x^2\Big)^y dx=\displaystyle\int_{-r}^r\Bigg[r^2\bigg(1-\Big(\frac{x}{r}\Big)^2\bigg)\Bigg]^y dx=

=r^{2y}\displaystyle\int_{-r}^r\bigg[1-\Big(\frac{x}{r}\Big)^2\bigg]^y dx=

={\scriptsize\begin{bmatrix}\frac{x}{r}=\sin t && t = \arcsin\frac{x}{r}\\x=r\sin t && t_{-r}=\arcsin\frac{-r}{r}=\arcsin(-1)=-\frac{\pi}{2}\\dx=r\cos t dt && t_r=\arcsin\frac{r}{r}=\arcsin(1)=\frac{\pi}{2}\end{bmatrix}}=

=r^{2y}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\Big(1-\sin^2t\Big)^y r\cos t dt=

=r^{2y+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y}t\cos t dt=

=r^{2y+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y+1}t dt

Teraz skorzystamy z poniższej formuły redukcyjnej

\displaystyle\int\cos^nxdx=\frac{1}{n}\cos^{n-1}x\sin x+\frac{n-1}{n}\displaystyle\int\cos^{n-2}xdx

Z wyprowadzeniem powyższego wzoru można zapoznać się np. w filmie "Calculus - Reduction Formula for Powers of Cosine".

Podstawiając otrzymujemy

\displaystyle\int_{-r}^r\Big(r^2-x^2\Big)^y dx=

=\frac{r^{2y+1}}{2y+1}\Bigg(\Big[\cos^{2y}t\sin t\Big]_{-\frac{\pi}{2}}^\frac{\pi}{2}+2y\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y-1}t dt\Bigg)=

={\scriptsize\frac{r^{2y+1}}{2y+1}\Bigg(\cos^{2y}\frac{\pi}{2}\sin\frac{\pi}{2}-\cos^{2y}\big(-\frac{\pi}{2}\big)\sin\big(-\frac{\pi}{2}\big)+2y\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y-1}t dt\Bigg)}=

=\frac{r^{2y+1}}{2y+1}\Bigg(0\cdot 1-0\cdot\big(-1\big)+2y\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y-1}t dt\Bigg)=

=\frac{2y}{2y+1}r^{2y+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y-1}t dt

Ostatecznie

{\small\displaystyle\int_{-r}^r\Big(r^2-x^2\Big)^y dx=\frac{2y}{2y+1}r^{2y+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2y-1}t dt}

Jest to wzór warty zapamiętania 🙂

Uogólnienie wzoru na objętość kuli

W uogólnieniu wzoru na objętość kuli n-wymiarowej pomaga zrozumienie zależności rekurencyjnej (pisałem o tym definiując hipersześcian i hiperkulę), dosyć oczywistej gdy się rozważa postać i objętość kuli krok po kroku, tzn. zaczynając od wymiaru 1, przechodząc przez wymiary 2 i 3.

Objętość kuli o wymiarze n = 1

Można powiedzieć, że kula o wymiarze 1 (czyli odcinek) powstaje z przesunięcia punktu (który ma wymiar 0), wzdłuż nowego wymiaru X w zakresie x\in[-R,R]

Kula - wymiar 1

{\Large V_R^{\dim 1}=2R}

Objętość kuli o wymiarze n = 2

Mając odcinek (kulę o wymiarze 1), przesuwając go wzdłuż nowego wymiaru X w zakresie x\in[-R,R], dostosowując jednocześnie jego długość (czyli promień kuli o wymiarze 1), otrzymujemy koło - tzn. kulę o wymiarze 2.

Kula - wymiar 2

V_R^{\dim 2}=\displaystyle\int_{-R}^R V_{r(x)}^{\dim 1}dx=

=\displaystyle\int_{-R}^R 2r(x)dx=2\displaystyle\int_{-R}^R \Big(R^2-x^2\Big)^\frac{1}{2}dx=...

Stosujemy wcześniej wyprowadzony wzór dla y=\frac{1}{2}

...=2\frac{2\cdot\frac{1}{2}}{2\cdot\frac{1}{2}+1}R^{2\cdot\frac{1}{2}+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2\cdot\frac{1}{2}-1}t dt=

=2\frac{1}{2}R^2\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^0t dt=

=R^2\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}dt=R^2\Big[t\Big]_{-\frac{\pi}{2}}^\frac{\pi}{2}=

=R^2\Big(\frac{\pi}{2}+\frac{\pi}{2}\Big)=\pi R^2

{\Large V_R^{\dim 2}=\pi R^2}

Objętość kuli o wymiarze n = 3

Procedura jest analogiczna. Przesuwając koło (czyli kulę o wymiarze 2) wzdłuż nowego wymiaru X w zakresie x\in[-R,R], jednocześnie zmieniając odpowiednio promień koła, otrzymujemy kulę o wymiarze 3.

Kula - wymiar 3

V_R^{\dim 3}=\displaystyle\int_{-R}^R V_{r(x)}^{\dim 2}dx=

=\displaystyle\int_{-R}^R \pi r^2(x)dx=\pi\displaystyle\int_{-R}^R \Big(\sqrt{R^2-x^2}\Big)^2dx=

=\pi\displaystyle\int_{-R}^R \big(R^2-x^2\big)dx=...

Jak widać jest to całka zupełnie elementarna, nie ma konieczności stosowania wcześniej wyprowadzonego wzoru. Ja to jednak uczynię aby potwierdzić, że poprzednio otrzymana formuła jest prawdziwa w każdym przypadku 🙂

Stosując elementarną całkę

...=\pi\Bigg(\Big[R^2x\Big]_{-R}^R-\Big[\frac{x^3}{3}\Big]_{-R}^R\Bigg)

=\pi\Bigg(\Big[R^2R-R^2(-R)\Big]-\frac{R^3-(-R^3)}{3}\Bigg)=

\pi\bigg(2R^3-\frac{2R^3}{3}\bigg)=\pi\bigg(\frac{6R^3}{3}-\frac{2R^3}{3}\bigg)=\pi\frac{4R^3}{3}

{\Large V_R^{\dim 3}=\frac{4}{3}\pi R^3}

Stosując wcześniej wyprowadzony wzór dla y=1

...=\pi\displaystyle\int_{-R}^R \big(R^2-x^2\big)^1dx=

=\pi \frac{2\cdot 1}{2\cdot 1+1}R^{2\cdot 1+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2\cdot 1-1}t dt=

=\pi \frac{2}{3}R^3\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos t dt=\pi \frac{2}{3}R^3\Big[\sin t\Big]_{-\frac{\pi}{2}}^\frac{\pi}{2}=

=\pi \frac{2}{3}R^3\Big(\sin\frac{\pi}{2}-\sin(-\frac{\pi}{2})\Big)=\pi \frac{2}{3}R^3\Big(1-(-1)\Big)=

=\pi \frac{2}{3}R^3\big(2\big)=\frac{4}{3}\pi R^3

{\Large V_R^{\dim 3}=\frac{4}{3}\pi R^3}

Objętość kuli o wymiarze n - uogólnienie

Na bazie przypadków 1, 2, 3 wymiarowych ujawniła się procedura rekurencyjna pozwalająca tworzyć hiperkulę wymiaru n z hiperkuli wymiary n-1. Zwyczajnie "przesuwamy" hiperkulę wymiaru n-1 w nowym wymiarze X w zakresie x\in[-R,R], dostosowując jej promień r(x)=\sqrt{R^2-x^2}, gdzie R jest niezmiennym promieniem hiperkuli.

{\small V_R^{\dim n}=\begin{cases}2R&\text{dla}\quad n=1\\ \displaystyle\int_{-R}^R V_{r(x)=\sqrt{R^2-x^2}}^{\dim n-1}dx&\text{dla}\quad n>1\end{cases}}

Objętość kuli o wymiarze n = 4

V_R^{\dim 4}=\displaystyle\int_{-R}^R V_{r(x)}^{\dim 3}dx=

=\displaystyle\int_{-R}^R\frac{4}{3}\pi r^3(x)dx=\frac{4}{3}\pi\displaystyle\int_{-R}^R \Big(R^2-x^2\Big)^\frac{3}{2}dx=...

Stosujemy wzór dla y=\frac{3}{2}

...=\frac{4}{3}\pi\frac{2\cdot\frac{3}{2}}{2\cdot\frac{3}{2}+1}R^{2\cdot\frac{3}{2}+1}\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^{2\cdot\frac{3}{2}-1}t dt=

=\frac{4}{3}\pi\frac{3}{4}R^4\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t dt=

=\pi R^4\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t dt=...

Całkę \displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t dt możemy oczywiście liczyć, ale łatwiej i szybciej zauważyć, że

\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t+\sin^2tdt=\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}dt=\pi

i że połowa tego "prostokąta" przypada dla \displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t dt, zatem

\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t dt=\frac{\pi}{2}

Podstawiając do

...=\pi R^4\displaystyle\int_{-\frac{\pi}{2}}^\frac{\pi}{2}\cos^2t dt=\pi R^4\frac{\pi}{2}=\frac{\pi^2}{2}R^4

{\Large V_R^{\dim 4}=\frac{\pi^2}{2}R^4}

Hiperkula wpisana w hipersześcian

Wyznaczyliśmy, że:

  • dla 1 wymiaru V_R^{\dim 1}=2R
  • dla 2 wymiarów V_R^{\dim 2}=\pi R^2
  • dla 3 wymiarów V_R^{\dim 3}=\frac{4}{3}\pi R^3
  • dla 4 wymiarów V_R^{\dim 4}=\frac{\pi^2}{2}R^4

5-ty i większy wymiar można wyznaczyć analogicznie, poniżej podam gotowe wzory opublikowane na Wikipedii.

  • dla 5 wymiarów V_R^{\dim 5}=\frac{8}{15}\pi^2R^5
  • dla 6 wymiarów V_R^{\dim 6}=\frac{\pi^3}{6}R^6
  • dla 7 wymiarów V_R^{\dim 7}=\frac{16}{105}\pi^3R^7
  • dla 8 wymiarów V_R^{\dim 8}=\frac{\pi^4}{24}\pi^8R^5
  • dla 9 wymiarów V_R^{\dim 9}=\frac{32}{945}\pi^4R^9
  • dla 10 wymiarów V_R^{\dim 10}=\frac{\pi^5}{120}\pi^2R^{10}
  • ...
  • dla n wymiarów V_R^{\dim n}=\frac{\pi^\frac{n}{2}}{\Gamma(\frac{n}{2}+1)}R^n

Jeśli krawędź n-wymiarowego hipersześcianu ma długość a, to jego objętość wynosi a^n. Promień hiperkuli wpisanej w hipersześcian będzie stanowił połowę długości krawędzi hipersześcianu, tzn. R=\frac{a}{2}.

Zadziwiające, objętość kuli wpisanej w hipersześcian "znika" wraz ze wzrostem liczby wymiarów, i ten zanik postępuje na prawdę szybko!!

Aby wyjaśnić ten fenomen należy zauważyć, że wraz ze wzrostem liczby wymiarów rośnie odległość "po przekątnej" do wymiarów, przy jednoczesnym zachowaniu odległości wzdłuż wymiarów. Maksymalna długość "przekątnej" w hipersześcianie jednostkowym (o krawędzi długości 1) będzie równa \sqrt{n}, gdzie n oznacza liczbę wymiarów. Wynika to bezpośrednio z zaaplikowania metryki do wierzchołków \mathbb{0}=(0,0,\ldots,0) i \mathbb{1}=(1,1,\ldots,1).

W konsekwencji objętość hipersześcianu kumuluje się w okolicach jego wierzchołków, zaś kula wpisana leży w jego środku stykając się ze wszystkimi jego ścianami.

Objętość hiperkuli jednostkowej

Kolejna ciekawostka kryje się w objętości hiperkuli jednostkowej (o promieniu 1). Okazuje się, że ta objętość jest najwyższa dla 5 wymiarowej przestrzeni.

Objętość hiperkuli jednostkowej - zależność od liczby wymiarów

Do liczby wymiarów n=5 objętość hiperkuli jednostkowej rośnie, w 5-tym wymiarze osiąga maksimum, powyżej 5-tego wymiaru objętość systematycznie spada, w granicy osiągając wartość 0.

Ciekawostka: jeśli rozważyć powierzchnię hiperkuli n-wymiarowej (czyli hipersfery n-1 wymiarowej) to powierzchnia będzie najwyższa dla hipersfery 6-wymiarowej, czyli hiperkuli 7-wymiarowej. Powyżej 7 wymiaru powierzchnia zaczyna spadać z granicą w nieskończoności równą 0.  Powierzchnię hiperkuli można wyznaczyć poprzez pochodną objętości względem promienia.

Na koniec

Przestrzenie wielowymiarowe, nawet te z bardzo intuicyjną metryką, skrywają wiele tajemnic. Dziś odkryliśmy tylko kilka 🙂 Mam nadzieję, że Wam się podobało!

Pozdrowienia,

Mariusz Gromada

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}

Funkcja f(x)=x^x i związek tetracji z liczbą e

Funkcja x^x

f(x)=x^x to podstawowy przykład funkcji na bazie tetracji.

Własności f(x)=x^x

  • f(x)=x^x jest określona na dodatnich liczbach rzeczywistych
  • 0^0 jest symbolem nieokreślonym, ale x^x\to 1 gdy x\to 0^+
  • f(x)=x^x posiada minimum e^{-\frac{1}{e}} w punkcie x=\frac{1}{e}
  • f(x)=x^x maleje w przedziale x\in(0, \frac{1}{e}), rośnie w przedziale x\in(\frac{1}{e},+\infty)
  • f^\prime(x)=x^x\big(\ln x+1\big)

Pochodna f(x)=x^x

Aby policzyć pochodną x^x wystarczy zastosować drobny trick na bazie własności logarytmu.

f(x)=x^x

x>0 oraz f(x)>0

\ln f(x)=\ln x^x=x\ln x

\Big(\ln f(x)\Big)^\prime=\Big(x\ln x\Big)^\prime

\frac{1}{f(x)}f^\prime(x)=x^\prime\ln x + x\Big(\ln x\Big)^\prime=\ln x + 1

f^\prime(x)=(x^x)^\prime

f^\prime(x)=f(x)\Big(\ln x + 1\Big)=x^x\Big(\ln x + 1\Big)

Bazując na rekurencyjnej definicji tetracji, korzystając z powyższego tricku, można wyznaczyć ogólną rekurencyjną formułę na pochodną tetracji n liczby x. Mając pochodną z łatwością wykazujemy większość podanych własności.

Nieskończona wieża wykładnicza i jeszcze silniejszy związek tetracji z liczbą e

{\Huge x^{x^{x^{x^{x^{\cdots}}}}}=?}

Problem zbieżności ciągu tetracji został rozwiązany już w XVIII wieku, a dokonał tego Leonhard Euler 🙂 Rozważmy granicę

\lim_{n\to\infty}{^{n}x}

zadając pytanie "dla jakich x>0 istnieje powyższa granica?"

Na potrzeby rozważań załóżmy, że taka granica istnieje i wynosi

\lim_{n\to\infty}{^{n}x}=y

Bazując na rekurencyjnej definicji tetracji otrzymujemy

y=\lim_{n\to\infty}{^{n}x}=\lim_{n\to\infty}x^{^{n-1}x}=

=x^{\lim_{n\to\infty}{^{n-1}x}}=x^y

Zatem, warunkiem koniecznym dla zbieżności ciągu tetracji jest

y=x^y

gdzie

\lim_{n\to\infty}{^{n}x}=y

Przekształcając y=x^y

y^{\frac{1}{y}}=(x^y)^{\frac{1}{y}}

otrzymujemy

x=y^\frac{1}{y}

Uwaga: nie jest to warunek dostateczny!

Twierdzenie Eulera o zbieżności ciągu tetracji: y=\lim_{n\to\infty}{^{n}x} istnieje i jest skończona wyłącznie jeśli x\in\Big[e^{-e},e^\frac{1}{e}\Big]. Zachodzi wtedy

y\in\Big[\frac{1}{e},e\Big]

dla

x\in\Big[e^{-e},e^\frac{1}{e}\Big]

Dowód powyższego twierdzenia wykracza poza objętość tego artukułu, zainteresowanych zapraszam do publikacji R. Arthur Knoebel , Exponentials Reiterated.

Tetracja - zbieżność

Na koniec niesamowita estetyka, która ujawnia się w nieskończonej wieży wykładniczej

W przedziale y\in\Big[\frac{1}{e},e\Big] leżą tylko dwie liczby całkowite: 1 i 2.

y=1 to x=1

y=2 to x=2^\frac{1}{2}=\sqrt{2}

Piękne - nieskończona tetracja \sqrt{2} daje w wyniku 2 🙂

Wieża potęgowa - Tetracja

Pozdrowienia,

Mariusz Gromada

 

 

 

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

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

W trakcie minionej nocy, około godziny 02:00, miałem nagły przebłysk 🙂 Prawdziwie magiczna chwila! 🙂 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 / Tips & Tricks na krzywych - 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) / Tips & Tricks na krzywych - 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 / Tips & Tricks na krzywych - 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