by ·0 Comments

W części 4 cyklu „ocena jakości klasyfikacji” opisałem podstawowe statystyki w wariancie nieskumulowanym służące inspekcji modelu predykcyjnego. Nieskumulowane prawdopodobieństwo i nieskumulowany lift, choć bardzo przydatne na etapie budowy modelu (praca analityka), sprawdzają się nieco gorzej w kontaktach analityk – odbiorca biznesowy. Odbiorcę biznesowego zazwyczaj interesują informacje takie jak „do jakiej części zainteresowanych produktem dotrę?” lub „o ile skuteczniejsze jest targetowanie na bazie modelu?” (tu uwaga dla bardziej zaawansowanego czytelnika – celowo pomijam kwestie wpływu inkrementalnego – tzw. uplift będzie tematem przyszłych wpisów).

Założenia – przypomnienie

Podobnie do poprzednich część cyklu załóżmy, że rozważamy przypadek klasyfikacji binarnej (dwie klasy: „Pozytywna – 1” nazywana targetem oraz „Negatywna  – 0”). Załóżmy ponadto, że dysponujemy modelem predykcyjnym $p$ zwracającym prawdopodobieństwo $p(1|x)$ przynależności obserwacji $x$ do klasy „Pozytywnej – 1” (inaczej „P od 1 pod warunkiem, że x”). I jeszcze ostatnie założenie, wyłącznie dla uproszczenia wizualizacji – dotyczy rozmiaru klasy pozytywnej – tym razem ustalmy, że jest to 5%, inaczej, że prawdopodobieństwo a-priori P(1)=0.05.

Skumulowane prawdopodobieństwo i skumulowany lift – czyli o ile skuteczniejsze jest targetowanie na bazie modelu?

Pojęcie liftu dobrze jest utożsamiać z krotnością rozumianą jako „o ile razy częściej zaobserwuję target w grupie wybranej modelem w stosunku do wyboru losowego”. Interpretacja „krotnościowa” ma zastosowaniu zarówno do liftu skumulowanego i nieskumulowanego. Lift nieskumulowany powstaje na bazie obserwacji targetu w określonym przedziale estymowanego prawdopodobieństwa (np. pojedynczy centyl, pojedynczy decyl), natomiast lift skumulowany odnosi się do targetu analizowanego we wszystkich przedziałach estymowanego prawdopodobieństwa, które leżą „na lewo” od ustalonego puntu (czyli np. 20 pierwszych centyli, 2 pierwsze decyle).

Ideę liftu najlepiej obrazuje wykres prawdopodobieństwa i liftu:

  • Oś pozioma – frakcja bazy względem oceny modelem – czyli baza posortowana względem estymowanego prawdopodobieństwa (czasami mówimy również względem score) w porządku od wartości największej do najmniejszej.
  • Lewa oś pionowa – prawdopodobieństwo / target rate – częstość obserwacji targetu w określonym przedziale / przedziałach.
  • Prawa oś pionowa – lift – normalizacja do średniego target rate (dzielenie przez a-priori).

Model predykcyjny - Lift skumulowany

I tak – dla powyższego przykładu – mamy lift ponad 3 przy decyzji, że „cut-off point” umieszczamy dokładnie w 20 centylu. Ale zaraz – przecież na 10 centylu mamy lift ponad 4 – czyli lepiej? …

Krzywa zysku aka Gain Curve lub Captured Response – czyli do jakiej części zainteresowanych produktem dotrę?

… Rozwiązaniem powyższego dylematu jest analiza krzywej zysku. Krzywa zysku łączy w sobie ideę liftu wraz z „zasięgiem„ grupy. Przykładowo: z bazy 100 tys. klientów, w której 5 tys. zainteresowanych jest produktem, do kampanii wybrano 10 tys. Po realizacji komunikacji okazało się, że spośród 10 tys. zakupu dokonało 3 tys. klientów. I dochodzimy łatwo do definicji zasięgu jako pokrycia 3 tys. z 5 tys, czyli dotarcie do targetu na poziomie 3/5 = 60%.

Ideę zasięgu bardzo dobrze obrazuje wykres krzywej zysku:

  • Oś pozioma – tak jak dla liftu – frakcja bazy względem oceny modelem.
  • Oś pionowa – zasięg

Model predykcyjny - Krzywa zysku

Analizując powyższy przykład – zasięg na 10% to około 45%, na 20% to już około 65% – czyli „chyba warto się pochylić” 🙂 … cdn …

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·0 Comments

Cut-off point

W części 4 cyklu „Ocena jakości klasyfikacji” przedstawiłem podstawowe statystyki prawdopodobieństwa oraz liftu (w wersji nieskumulowanej) służące do inspekcji modelu predykcyjnego w zakresie siły separacji klas. W części 3 skupiłem się na koncepcji punktu odcięcia (cut-off point), który model predykcyjny (z ciągłą zmienną odpowiedzi) transformuje w klasyfikator. Dziś przybliżę strategie doboru punktu odcięcia, celowo pomijając aspekty techniczne związane z analityką predykcyjną – tym zajmiemy się w kolejnym odcinku (opisując skumulowane prawdopodobieństwo, skumulowany lift, krzywą zysku aka Gain Curve lub Captured Response oraz krzywą ROC).

Dobór punktu odcięcia – strategie (z którymi miałem do czynienia w pracy zawodowej)

  • Całkowicie biznesowa – metoda najprostsza, nadal popularna, jednak coraz rzadziej stosowana.
  • Wyłącznie analityczna – rzadko stosowane w biznesie, częściej widoczna pracach / badaniach naukowych.
  • Hybryda powyższych – wariant dziś preferowany przez różne jednostki CRM.

Dobór całkowicie biznesowy

Nadal częsta praktyka, która przy wnikliwej analizie okazuje się nie być najbardziej optymalną. W strategii „całkowicie biznesowej” dobór punktu odcięcia jest pochodną zasobów (np. dostępność / pojemność kanałów komunikacji). Przykładowo – współpracujemy z call center, które miesięcznie może zadzwonić do 100 tys. Klientów. W takiej sytuacji dosyć naturalnie powstaje potrzeba wybrania „100 tys. najlepszych Klientów” (najlepszych do danej akcji). Model predykcyjny posłuży więc do „posortowania” Klientów, a punkt odcięcia będzie zależny od wskazanej oczekiwanej liczby 100 tys. Problem ze strategią całkowicie biznesową polega na tym, że „najlepszy” mylony jest z „dobry”. Dodatkowo zdarza się, że siła modelu jest błędnie interpretowana jako zdolność do znalezienie większej liczby „dobrych” klientów – w rzeczywistości jest na odwrót – im lepszy model, tym mniejsze optymalne bazy. Równie istotna kwestia to skąd się właściwie wzięła liczba 100 tys?

Dobór wyłącznie analityczny

Dobór wyłącznie analityczny polega na optymalizacji błędów klasyfikacji – w nieco bardziej zgeneralizowanym podejściu optymalizuje się funkcję kosztu błędów (najczęściej jeśli koszty są mocno asymetryczne). Podejście analityczne jest zupełnie poprawna i uzasadnione, jednak w biznesie prawie nieobecne ze względu na brak uwzględnionego aspektu celu biznesowego, priorytetów, zasobów, itp.

Dobór analityczno-biznesowy

Dobór analityczno-biznesowy (jako połączenie powyższych strategii) najlepiej sprawdza się w sytuacji analizy szerszego portfela produktów (tzn. bazy i cut-off’y dobierane do różnych działań stanowią element realizacji szerszej polityki CRM). Zaczynamy od celów biznesowych, priorytetów, analizy zasobów, pojemności kanałów. Następnie weryfikujemy Klientów, ich potrzeby w kontekście możliwie wielu produktów. Ostatecznie – w wyniku kilku iteracji – dążymy do „zmapowania” segmentów Klientów na cele i zasoby, zawsze koniecznie modyfikując obie strony równania. Jest to trudne i wielowymiarowe zadanie, zadanie zawsze „niedokończone”, coraz bardziej opierające się na różnego rodzaju eksperymentach … ale o tym w kolejnych częściach cyklu …

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·3 komentarze

Dziś, w ramach cyklu „Matematyka w obrazkach”, chciałbym Wam zaprezentować „autorskie równanie” 🙂

$$\pi + e = \text{Sudoku}$$

Zależność powyższą „wyprowadziłem” wykorzystując bibliotekę „Janet Sudoku”!

PI + e Sudoku

Dodatkowo załączam wersję tekstową – przydatną jeśli zechcecie przeanalizować / rozwiązać łamigłówkę samodzielnie  (np. przy wykorzystaniu Janet Sudoku Solver’a).

<br />
# Pi + e = Sudoku</p>
<p>+-------+-------+-------+<br />
| . . 4 | 1 5 9 | 2 . . |<br />
| . 1 . | . . . | . 6 . |<br />
| 3 . . | . . . | . . 5 |<br />
+-------+-------+-------+<br />
| 4 . . | . 8 . | . . 3 |<br />
| . 8 . | 2 . 1 | . 5 . |<br />
| . . 3 | . 7 . | 8 . . |<br />
+-------+-------+-------+<br />
| . . 2 | . . . | 9 . . |<br />
| . . . | 3 . 7 | . . . |<br />
| 7 . . | . 9 . | . . 8 |<br />
+-------+-------+-------+</p>
<p># One line definition:<br />
# ..41592...1.....6.3.......54...8...3.8.2.1.5...3.7.8....2...9.....3.7...7...9...8<br />
# 004159200010000060300000005400080003080201050003070800002000900000307000700090008</p>
<p># Janet-Sudoku-v.1.1.1, 2016-04-19 22:28:15<br />

Janet Sudok

Pozdrowienia,
Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·0 Comments

Błądzenie losowe

Błądzenie losowe jest dosyć podstawowym przykładem procesu stochastycznego. Poniżej wykres 20 błądzeń losowych, każda ścieżka o długości 200. Wszystkie ścieżki rozpoczynają w tym samym punkcie, następnie w każdym kolejnym kroku podejmowana jest losowa decyzja odnośnie kierunku „dół / góra”. Każdy kierunek jest równo prawdopodobny, wybór kierunku w danym kroku nie zależy od decyzji dokonanych poprzednio.

Mariusz Gromada

Prawo iterowanego logarytmu

Można zauważyć, że ścieżki pozostają skupione wokół punktu początkowego, jednak średnia odległość od tego punktu rośnie wraz ze wzrostem liczby kroków – co ciekawe – odległość rośnie wolniej niż liniowo, rośnie zgodnie z $\sqrt{n}$. Ogólnie zespół twierdzeń rachunku prawdopodobieństwa opisujących rozmiar fluktuacji w błądzeniu losowym określa się mianem prawa iterowanego logarytmu.

Pozdrowienia,

Mariusz Gromada 

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·0 Comments

Dziś w cyklu „Matematyka w obrazkach” kalambur – zapraszam do komentowania 🙂

Rebus 01

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·0 Comments

Liczby naturalne $\mathbb{N}$

Podział liczb - #1

Początki matematyki to liczby naturalne $\mathbb{N} = \{1,2,3,\ldots\}$, czyli narzędzie służące do opisu liczności (np. trzy elementy) lub do podawania kolejności (np. trzecia osoba). Z biegiem czasu do liczb wprowadzono pierwsze działania – dodawanie i mnożenie. Z łatwością można wykazać, że liczby naturalne są zamknięte ze względu na dodawanie i mnożenie – jednak nim przejdziemy dalej – wyjaśnię w kilku słowach co to tak naprawdę oznacza.

Zamkniętość zbioru ze względu na działanie

Rozważmy dowolny zbiór $A$ oraz dwuargumentowe działanie $a*b$ określone na elementach $a, b \in A$.

Mówimy, że zbiór $A$ jest zamknięty ze względu na działanie $*$ jeśli dla dowolnych $a, b \in A$ istnieje $c \in A$, że $c=a*b$.

Inaczej mówiąc, zbiór jest zamknięty ze względu na dane działanie jeśli wszystkie możliwe wyniki wskazanego działania (na elementach rozważanego zbioru) są również elementami tego zbioru. W analogi do dodawania i mnożenia liczb naturalnych możemy stwierdzić, że suma dwóch liczb naturalnych jest liczbą naturalną, a w konsekwencji mnożenie dwóch liczb naturalnych daje także wynik w liczbach naturalnych.

$$\Big(\mathbb{N}, +, \times\Big)$$

Wraz z rozwojem matematyki wprowadzano kolejne działania, które ujawniły „niekompletność” zbioru liczb naturalnych.

Liczby całkowite $\mathbb{Z}$ jako „domknięcie” odejmowania „-„

Podział liczb - #2

Wprowadzenie odejmowania pokazało, że liczby naturalne nie są zamknięte ze względu na to działanie. Dla wielu liczb naturalnych wynik odejmowania jest liczbą naturalną, jednak istnieje równie wiele przykładów uzasadniających wniosek przeciwny, np.:

$$2-5 = -3 \notin \mathbb{N}$$

Uzupełniając liczby naturalne o liczby do nich przeciwne oraz 0 otrzymujemy liczby całkowite $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ zamknięte również ze względu na odejmowanie.

$$\Big(\mathbb{Z}, +, \times,-\Big)$$

Liczby wymierne $\mathbb{Q}$ jako „domknięcie” dzielenia $\frac{\cdot}{\cdot}$

Podział liczb - #3

Liczby wymierne wyrażając proporcję (stosunek) pomiędzy wielkościami powstają z ilorazu dwóch liczb całkowitych.

Każdą liczbę wymierną można zapisać jako ułamek, tzn. $\mathbb{Q}=\Big\{\frac{m}{n}:m,n\in\mathbb{Z},n\neq 0\Big\}$ gdzie $m, n$ są liczbami całkowitymi, a $n$ jest różne od 0.

I choć dla części liczb naturalnych ich iloraz jest również liczbą naturalną (np. 10 / 2 = 5), to istnieje równie wiele przypadków sytuacji odwrotnej, np.

$$\frac{1}{5}\notin\mathbb{Z}$$

Liczby wymierne są zamknięte ze względu na iloraz (z pominięciem 0 – gdyż dzielenie przez 0 nie jest określone).

$$\Big(\mathbb{Q}, +, \times,-, \frac{\cdot}{\cdot}\Big)$$

Liczby algebraiczne jako „częściowe domknięcie” pierwiastkowania $\sqrt{\cdot}$ i potęgowania ${m}^{n}$.

Podział liczb - #4

Już Pitagoras potrafił wykazać że długości przekątnej jednostkowego kwadratu nie da się wyrazić jako stosunku ówcześnie znanych liczb. Z twierdzenia Pitagorasa łatwo zapisujemy

$$x^2=1^2+1^2$$

$$x^2=2$$

$$x=+/-\sqrt{2}\notin\mathbb{Q}$$

Pierwiastek z liczby 2 nie jest liczbą wymierną, podobnie jak i $\sqrt{3}$, $\sqrt{5}$, … Zapiszmy nieco ogólniej

$$x^2-2=0$$

Zatem pierwiastek z liczby 2 jest zerem wielomianu (pierwiastkiem wielomianu) o wymiernych współczynnikach.

Liczby algebraiczne, zdefiniowane jako rozwiązania wielomianów o wymiernych współczynnikach, są pierwszym etapem „domknięcia” liczb wymiernych.

Liczby rzeczywiste $\mathbb{R}$ jako granice ciągów liczb wymiernych.

Podział liczb - #5

Liczby wymierne (nawet rozszerzone o liczby algebraiczne) nie są zupełne.

Zbiór nazywamy zupełnym jeśli w zbiorze istnieje granica każdego ciągu spełniającego warunek Cauchy’ego.

Wykres ciągu Cauchy’ego Wykres ciągu Cauchy’ego – źródło wikipedia.org

Mówimy, że ciąg spełnia warunek Cauchy’ego, jeśli dla ustalonej dowolnie małej liczby, pomijając skończoną liczbę elementów ciągu, „odległość” pomiędzy pozostałymi dowolnymi dwoma elementami ciągu nie przekracza ustalonej wartości.

Dobrym i bardzo znanym przykładem jest ciąg definiujący podstawę logarytmu naturalnego

$$a_n=(1+\frac{1}{n})^n$$

Każdy element ciągu jest liczbą wymierną, gdyż powstaje z mnożenia liczb wymiernych. Ciąg ten spełnia warunek Cauchy’ego, jest zbieżny, jednak jego granica nie istnieje w liczbach wymiernych.

$$\lim a_n=e\notin\mathbb{Q}$$

Liczba e nie jest liczbą wymierną, nie jest również liczbą algebraiczną, Liczba e jest przykładem kolejnej klasy liczb „uzupełniających braki” w liczbach wymiernych.

Liczby nienależące do zbioru liczb wymiernych, które są granicami ciągów liczb wymiernych spełniających warunek Cauchy’ego, nazywamy liczbami niewymiernymi.

Niektóre z liczb niewymiernych są liczbami algebraicznymi (np. $\sqrt{2}$), jednak znaczna ich większość to liczby przestępne, czyli takie, które nie są pierwiastkiem żadnego wielomianu o współczynnikach wymiernych.

$$\Big(\mathbb{R}, +, \times,-, \frac{\cdot}{\cdot}, \lim \Big)$$

Liczby zespolone jako „domknięcie” pierwiastkowania $\sqrt{-1}$

Podział liczb - #6

Świat szedł do przodu, matematyka odkrywała kolejne wzory opisujące rzeczywistość. W XVI wieku ponownie napotkano problem „niezupełności” liczb i działań. Trudność pojawiła się w momencie wyprowadzania wzoru na pierwiastki wielomianu stopnia 3. Każdy wielomian stopnia 3 ma przynajmniej jedno miejsce zerowe, jednak okazało się, że konstrukcja wzoru podającego te pierwiastki wymaga założenia istnienia wartości $\sqrt{-1}$. Tak powstały liczby zespolone, których znaczenie jest dużo bardziej głębokie niż wartość $\sqrt{-1}$ oraz wzory Cardano dla równań sześciennych. Liczby zespolone to całkowicie nowy wymiar liczb, wymiar ukryty, mimo wszystko pojawiający się w niemal każdej empirycznej dziedzinie nauki z fizyką na czele…

… ale o tym w kolejnej części cyklu…

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·21 komentarzy

Minus razy minus daje plus

Z pewnością każdy wie, że wynikiem mnożenia liczb ujemnych jest liczba dodania. Formułka „minus razy minus daje plus” była nam wtłaczana do głów w trakcie wczesnych lat szkolnych. Nauczyciele zapomnieli jednak wyjaśnić dlaczego tak właśnie jest, oraz przybliżyć motywację matematyków definiujących arytmetykę liczb ujemnych.

Mnożenie jako skrócone dodawanie

Mówi się, że mnożenie to skrócone dodawanie, co jest w zupełności prawdą i, przy ograniczeniu do liczb całkowitych, faktem dosyć oczywistym.

$$3\times 4 = 3 + 3 + 3 + 3 = 4 + 4 + 4 = 12$$

Mnożenie jest przemienne i rozdzielne względem dodawania

Te dwie fundamentalne własności mnożenia zapisujemy jako

przemienność $a\times b = b\times a$

przykład $3\times 4 = 4\times 3=12$

rozdzielność $a\times (b+c)=a\times b + a\times c$

przykład $3\times 4 = 3\times (1+3) = 3\times 1 + 3\times 3 = 3 + 9 = 12$

Mnożenie liczb ujemnych z punktu widzenia matematyka

Matematycy, definiując arytmetykę liczb ujemnych, chcieli zachować spójność z już rozwiniętą arytmetyką liczb dodatnich i zera. Opierając się na interpretacji skróconego dodawania łatwo uzasadniamy następujące:

$$-3\times 4 = (-3)+(-3)+(-3)+(-3)=-12$$

„Dodając dług do długu” otrzymujemy większy dług – intuicyjne. Teraz wykorzystując przemienność mnożenia otrzymujemy:

$$4\times (-3)=-3\times 4=-12$$

W tym momencie z intuicją już trochę trudniej, natomiast spójność została zachowana. Czas przejść do meritum – tzn spróbujmy odpowiedzieć na pytanie:

$$-3\times (-4)=?$$

Do rozwiązania powyższego zastosujemy trick na bazie rozdzielność mnożenia względem dodawania.

$$-3\times 0=0$$

$$-3\times 0=-3\times(-4+4)=0$$

$$-3\times(-4+4)=-3\times (-4)+(-3)\times 4=0$$

$$-3\times(-4)+(-12)=0$$

$$-3\times(-4)=12$$

Powyższe z intuicją nie ma nic wspólnego, jednak jest spójne, tzn. na bazie arytmetyki liczb dodatnich i zera, przemienności mnożenia, rozdzielności mnożenia względem dodawania, jesteśmy w stanie uzasadnić dlaczego mnożenie liczb ujemnych musi być liczbą dodatnią.

Mnożenie liczb ujemnych jako zmniejszenie straty

Załóżmy, że mnożymy dwie liczby, gdzie interpretacja pierwszej to wartość zysku bądź starty, natomiast znaczenie drugiej to zwielokrotnienie (zwiększenie / zmniejszenie) pierwszej wartości. W takiej sytuacji mnożenie dwóch liczb ujemnych oznacza zmniejszenie straty, czyli łączny efekt dodatni działania.

Interpretacja zmniejszenia straty

Powyższe wyjaśnienie można określić mianem intuicyjnego 🙂

I na koniec film od Mathologer’a wyjaśniający powyższy problem (materiał, na którym wzorowałem powyższy wpis).

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·1 Comment

W części 1 wpisu na temat Spirali Ulama zaznaczyłem, że efekt wizualnego ułożenia liczb pierwszych na diagonalach spirali kwadratowej jest konsekwencją głównie dwóch własności:

  1. Na przekątnych są albo same liczby parzyste, albo same liczby nieparzyste, zatem tylko diagonale z liczbami nieparzystymi będą agregować liczby pierwsze;
  2. Niektóre diagonale zagęszczają bardziej liczby pierwsze niż inne, co wynika z zależności pomiędzy przekątnymi i funkcją kwadratową oraz faktem, że niektóre funkcje kwadratowe generują więcej liczb pierwszych niż inne.

Dzisiejszy tekst poświęcę przybliżeniu własności nr 2.

Wielomiany i rekurencja

Funkcja kwadratowa i rekurencja

Dla wielomianów możemy zawsze podać ich postać rekurencyjną, Jest to własność mało znana, jednak dosyć prosta w uzasadnieniu. Pokażę to na przykładzie funkcji kwadratowej, jednocześnie wzbogacając cykl „Zabawy z rekurencją” 🙂

$$f(x) = ax^2+bx+c$$

Rozważmy następnie równanie

$$f(x+1)=f(x)+Bx+C$$

Podstawiając i upraszczając…

$$a(x+1)^2+b(x+1)+c=ax^2+bx+c+Bx+C$$

$$ax^2+2ax+a+bx+b+c=ax^2+bx+c+Bx+C$$

$$2ax+a+b=Bx+C$$

$2a=B$    oraz    $a+b=C$

otrzymujemy

$a=\frac{B}{2}$    oraz    $b=C-a$

Następnie analizując $f(1)$ mamy

$f(1)=a+b+c$    zatem    $c=f(1)-a-b$

$$c=f(1)-a-(C-a)=f(1)-C$$

Wniosek: jeśli znana jest relacja rekurencyjna $f(x+1)=f(x)+Bx+C$ oraz znamy wartość $f(1)$ to jesteśmy w stanie jednoznacznie wskazać równanie kwadratowe $ax^2+bx+c$ spełniające daną zależność rekurencyjna, gdzie

$a=\frac{B}{2}$,    $b=C-a$,    $c=f(1)-C$

Uogólnienia dokonujemy na bazie dwumianu Newtona

$$(x+1)^n = {n\choose 0}x^n+{n\choose 1}x^{n-1}+{n\choose 2}x^{n-2}+\ldots+{n\choose {n-1}}x+{n\choose n}$$

Funkcja kwadratowa i linie proste / przekątne na spirali Ulama

Poniżej spróbuję pokazać w jaki sposób „nawijanie prostej na kwadrat” sprawia, że parabole w efekcie otrzymują kształt linii prostych.

Przykład 1 – Pionowa prosta

Spirala Ulama - równanie prostej 1

Zapisujemy zależność rekurencyjną

$$f(1)=4$$

$$f(2)=f(1)+1+2+3+3+2$$

$$f(3)=f(2)+2+3+5+5+3$$

$$\ldots$$

$$f(n+1)=f(n)+n+2n+(2n+1)+(2n+1)+(n+1)$$

$$f(n+1)=f(n)+8n+3$$

Teraz, korzystając z wyprowadzonego wcześniej wzoru, wyznaczamy współczynniki a, b, c funkcji kwadratowej spełniającej $f(n+1)=f(n)+8n+3$.

$a=\frac{8}{2}=4$,    $b=3-4=-1$,    $c=4-3=1$

$$f(n)=4n^2-n+1$$

Dla testu czy wszystko jest ok sami podstawcie $n=1,2,3\ldots$

Przykład 2 – Przekątna (linia diagonalna)

Spirala Ulama - równanie prostej 2

Ponownie zapisujemy zależność rekurencyjną, tym razem nieco prostszą.

$$f(1)=3$$

$$f(2)=f(1)+2+2+3+3$$

$$f(3)=f(2)+4+4+5+5$$

$$\ldots$$

$$f(n+1)=f(n)+n+2n+2n+(2n+1)+(2n+1)$$

$$f(n+1)=f(n)+8n+2$$

Korzystając ze znanego wzoru wyznaczamy a, b, c dla $f(n+1)=f(n)+8n+2$.

$a=\frac{8}{2}=4$,    $b=2-4=-2$,    $c=3-2=1$

$$f(n)=4n^2-2n+1$$

Przykład: funkcja $n^2+n+41$ generująca liczby pierwsze

Wielomian $n^2+n+41$ jest funkcją „często generującą” liczby pierwsze. W tym przypadku dla każdego $n=0,1,\ldots,39$ wynik jest zawsze liczbą pierwszą. Poniżej tabela prezentująca zestawienie dla $n$ z zakresu od $0$ do $100$.

n n^2+n+41 Czy liczba pierwsza?
0 41 1
1 43 1
2 47 1
3 53 1
4 61 1
5 71 1
6 83 1
7 97 1
8 113 1
9 131 1
10 151 1
11 173 1
12 197 1
13 223 1
14 251 1
15 281 1
16 313 1
17 347 1
18 383 1
19 421 1
20 461 1
21 503 1
22 547 1
23 593 1
24 641 1
25 691 1
26 743 1
27 797 1
28 853 1
29 911 1
30 971 1
31 1033 1
32 1097 1
33 1163 1
34 1231 1
35 1301 1
36 1373 1
37 1447 1
38 1523 1
39 1601 1
40 1681 0
41 1763 0
42 1847 1
43 1933 1
44 2021 0
45 2111 1
46 2203 1
47 2297 1
48 2393 1
49 2491 0
50 2591 1
51 2693 1
52 2797 1
53 2903 1
54 3011 1
55 3121 1
56 3233 0
57 3347 1
58 3463 1
59 3581 1
60 3701 1
61 3823 1
62 3947 1
63 4073 1
64 4201 1
65 4331 0
66 4463 1
67 4597 1
68 4733 1
69 4871 1
70 5011 1
71 5153 1
72 5297 1
73 5443 1
74 5591 1
75 5741 1
76 5893 0
77 6047 1
78 6203 1
79 6361 1
80 6521 1
81 6683 0
82 6847 0
83 7013 1
84 7181 0
85 7351 1
86 7523 1
87 7697 0
88 7873 1
89 8051 0
90 8231 1
91 8413 0
92 8597 1
93 8783 1
94 8971 1
95 9161 1
96 9353 0
97 9547 1
98 9743 1
99 9941 1
100 10141 1

Po więcej przykładów odsyłam do artykułu „Prime-Generating Polynomial”.

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·24 komentarze

W 1963 polski matematyk Stanisław Ulam uprzyjemniał sobie czas spędzany w trakcie „bardzo długiego i bardzo nudnego” wykładu. Rekreacja polegała na takim wypisywaniu kolejnych liczby naturalnych 1, 2, 3, …, aby finalny kształt utworzył „spiralę kwadratową” . Poniżej przykład dla pierwszych 49 liczba naturalnych, spirala oczywiście nie kończy się na 49, chodzi jedynie o zobrazowanie zasady.

Spirala Ulama

W kolejnym kroku na tak przygotowanej „tablicy” Ulam oznaczył wszystkie liczby pierwsze

Spirala Ulamanastępnie usuwając pozostałe.

Spirala UlamaW tym momencie jego oczom ukazał się niezwykle ciekawy i nieznany dotąd wzór – tendencja do układania się liczb pierwszych na „przekątnych / liniach diagonalnych”. Lepiej to obrazuje spirala wygenerowana dla znacznie większego zakresu liczb.

Spirala Ulama

Każdy z Was może wygenerować podobną spiralę używają np. tego generatora.

Spirala Ulama i parzystość / nieparzystość liczb

Nietrudno zauważyć, że na liniach diagonalnych leżą albo same liczby parzyste, albo same liczby nieparzyste. Liczby pierwsze, poza 2, są nieparzyste – zatem nic dziwnego, że układają się na przekątnych reprezentujących liczby nieparzyste. Zaskakujące jest natomiast to, że niektóre diagonale zawierają ich znacznie więcej niż inne.

Spirala Ulama i wielomiany kwadratowe

Badania nad spiralą Ulama pokazały, że wzory przez nią ujawnione mają związek z generację przez niektóre funkcje kwadratowe nienaturalnie dużej liczby liczb pierwszych (ang. prime-rich quadratic polynomials), tzn. dla niektórych $f(x)=ax^2+bx+c$ „nienaturalnie” często $f(n)$ jest liczbą pierwszą dla $n\in\mathbb{N}$. Diagonale mogą być reprezentowane przez wielomiany stopnia 2, co wyjaśniam na poniższym schemacie.

Spirala Ulama i wielomiany stopnia 2

Przeczytaj również:

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

by ·0 Comments

W cyklu „Matematyka w obrazkach” tym razem graficzny sposób wyznaczenia pewnej całki oznaczonej.

Matematyka w obrazkach - całka sin^2(x)

Pozdrowienia,
Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa