Jacek Cichoń

Katedra Podstaw Informatyki ● WIT ● PWr
Strona główna Moje zajęcia

Big Data

Wykład przeznaczony jest dla studentów stopnia studiów informatycznych na Wydziale Podstawowych Problemów Techniki. Odbywa się w środy w godz. - (sala C-16/D3.2). Na stronie tej znajdziesz informacje o zasadach zaliczenia, realizowanym materiale, literaturze oraz listę zadań.

Koniec strony

Zasady zaliczania kursu

Zaliczenie kursu odbędzie się na podstawie zaliczeń laboratoriów (ustalicie zasady z doktorem Dominikiem Bojko) oraz kolokwium zaliczeniowym, które odbędzie się na ostatnim wykładzie.
Do indeksu zostanie wam wpisana ocena wyznaczana za pomocą następującego wzoru: $$ \begin{cases} \max\{K,\frac{K+L}{2}\} &: K\geq 3\\ 2.0 &: K=2.0\end{cases} $$

$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\NN{\mathbb{N}} $

Zagadnienia omówione na wykładzie

02.03.2023: Wstęp

Indeks TF.IDF

  1. $\mathcal{D}=\{d_1, \ldots, d_m\}$ - zbiór dokumentów
  2. $\Omega = \{w_1, \ldots, w_n\}$ - zbiór słów występujących w dokumentach
  3. $TF(w,d)$ = (liczba wystąpień słowa $w$ w dokumencie $d$)/(liczba wszystkich słów w dokumencie $d$)
    (term frequency)
  4. $IDF(w,\mathcal{D}) = \log_2\left(\frac{|\mathcal{D}|}{|\{d\in\mathcal{D}: w \in d\}|}\right)$ (inverse document frequency)
  5. $TF.IDF(w,d,\mathcal{D}) = TF(w,d) \cdot IDF(w,\mathcal{D})$

Licznik Morrisa

  init:: C = 0
  onInc:: if (random() < (1/2)^C) then C = C+1
  onGet:: return (2^C - 1)
Twierdzenie: Niech $C_n$ oznacza wartość zmiennej C po $n$ wywołaniach funkcji onInc(). Wtedy $$ E[2^{C_n}] = n+1 $$ Wniosek: Zmienna losowa $\hat{n} = 2^C - 1$ jest nieobciążonym estymatorem liczby $n$.

09.03.2023: MOM trik

  1. Koncentracja zmiennej losowej $\hat{n}^+ = \sum_{i=1}^{k} \hat{n}_i$
  2. Własności mediany
  3. Koncentracja zmiennej $$ \hat{n}^{++} = \textrm{median}(\{\hat{n}^+_1, \ldots,\hat{n}^+_l\})$$
  4. MOM trick = Median Of Means Trick: mamy algorytm A który szacuje szukaną wartość z dokładnością $\epsilon$ z prawdopodobieństwem $\geq \frac34$; przekształcamy go w algorytm zwracający szukaną wartość z tą samą dokładnością ale z prawdopodobieństwem $\geq 1 - \delta$: powtarzamy A $O(\log(1/\delta))$ i zwracamy medianę.

16.03.2023: Funkcje haszujące - I

  1. Rolling has hashing
  2. Uniwersalne rodziny haszujące
  3. Filtry Blooma
Do przeczytania: A. Broder and M. Mitzenmacher Network Applications of Bloom Filters: A Survey.

23.03.2023: Streaming - I

  1. Rodziny $k$ - uniwersalne funkcji haszujących
  2. Przykład k-niezależnej rodziny haszującej ze zbioru $\ZZ_p \to \ZZ_p$: $$h_{\vec{a}}(x) = \sum_{i=0}^{k-1} a_i \cdot x^i~,$$ gdzie $\vec{a} = (a_0,a_1,\ldots,a_{k-1}) \in \ZZ_p^k$.
    Skorzystaliśmy ze wzoru interpolacyjnego Lagrange'a.
  3. Algorytm R Vittera
  4. Tw. Algorytm R generuje próbkę zgodnie z rozkładem jednostajnym.
  5. Niech $L$ będzie momentem zmiany w algorytmie $R$. Niech $N$ będzie momentem następnej zmiany. Wtedy $$ \Pr[N\leq L + k] = \frac{k}{L+k}~. $$

30.03.2023: Godziny dziekańskie

13.04.2023: Streaming - II

  1. Optymalizacja algorytmu Vittera
  2. Sliding window: algorytm Bravermana

20.04.2023: Streaming - III

  1. Łańcuchy Markowa
  2. Diabelskie schody
  3. Metoda Bojko

27.04.2023: Locality sensitive hashing

  1. Przestrzenie metryczne
  2. Transformacje metryk: nakładanie funkcji wklęsłych; twierdzenie Steinhausa.
  3. Odległość Jaccarda: $d_J(A,B) = \frac{|A\triangle B|}{|A\cup B|}$
  4. Podobieństwo Jaccarda: $J(A,B) = \frac{|A\cap B|}{|A\cup B|}$
  5. Min-hash: $\mathrm{minHash}(A,h) = \min\{h(a): a\in A\}$
  6. Tw (na razie bez dowodu): Jeśli $\mathcal{H}$ jest niezależną rodziną funkcji haszujących, to $$\Pr_{h\in\mathcal{H}}[\mathrm{minHash}(A,h) = \mathrm{minHash}(B,h)] = J(A,B)$$
Strona główna Moje zajęcia