04.10.2018: Wstęp

val T = "ALA ma kota. ALA ma psa. Ala ma kota i kanarka"
val t = T.toLowerCase
var G = t.filterNot(x=>".;".contains(x)).split("\\s+").map(x=>(x,1))
val A = G.groupBy(x=>x._1).mapValues(x=>x.length)
var X = A.toSeq
X.sortWith((x,y)=>x._2>y._2)

11.10.2018: Funkcje haszujące

1. Paradoks urodzinowy: $E[B_n] = \sqrt{\frac{\pi n}{2}} - \frac12 + O(n^{-1/2})$
2. Coupon collector problem: $E[L_n] = n \cdot H_n - 1$
3. Przykład uniwersalnej rodziny haszującej ze zbioru $\ZZ_p^n \to \ZZ_p$: $h_a(x) = \sum_{i=1}^{n} a_i \cdot x_i$, gdzie $a \in \ZZ_p^n$
4. Przykład k-niezależnej rodziny haszującej ze zbioru $\ZZ_p \to \ZZ_p$: $h_a(x) = \sum_{i=0}^{k-1} a_i \cdot x^i$, gdzie $a = (a_0,a_1,\ldots,a_{k-1}) \in \ZZ_p^k$. Do pokazania niezależności przydaje się znajomość wyznacznika macierzy Vandermonda.
5. Podstawowy model MAP-REDUCE: procesy typu MAPPER - funkcja haszująca - procesy typu REDUCER.
6. Mnożenie macierzy przez wektor przechowywany w pamięci:
   MAPPER $(i,j,a_{ij}) \to (i,a_{i,j}x_j)$,
   REDUCER: $(i,L) \to (i, sum(L))$
7. Word-count problem:
   MAPPER: $w_1 w_2 \ldots w_n \to (w_1,1), (w_2,1), \ldots, (w_n,1)$
   REDUCER: $(w,L) \to (w,L.length)$

val macierz = List(
  (1,1,2.0),
  (1,2,1.0),
  (2,1,3.0),
  (2,2,1.0)
)
import scala.collection.mutable.ListBuffer

def mapper(mat:List[(Int,Int,Double)],x:Array[Double]) : Map[Int,ListBuffer[(Int, Double)]] = {
  var B = ListBuffer[(Int,Double)]()
  def emit(keyVal:(Int,Double)) : Unit = {
    B += keyVal
  }
  for ((i,j,m) <- mat) {
    var b = (i, m*x(j-1))
    emit(b)
  }
  B.groupBy(t=>t._1)
}

def uruchom(X : Map[Int,ListBuffer[(Int, Double)]]) : Unit = {
  for ((key,v) <- X) {
    reducer(key, v.map(x=>x._2))
  }
}

def reducer(key:Int, L:ListBuffer[Double]) : Unit = {
  def emit(key:Int,value:Double){
    println(s"y${key} = ${value}")
  }
  emit(key,L.sum)
} 

 val X = mapper(macierz,Array(1.0,2.0))
 uruchom(X)

18.10.2018: Map-Reduce

1. Złożenie grafu skierowanego: graf jest reprezentowany przez listę par wierzchołków reprezentujących krawędzie:
   

   map (a,b) { emit(a->("to",b)); emit(b->("from",a)) }
   reduce(x->L) { 
     pogrupuj L: ["from" -> L1, "to" -> L2]
     forall(a <- L1; c <- L2)
       emit((a,c) -> (a,c))
   }
   

2. Obliczanie sumy, przekroju i różnicy zbiorów za pomocą map-reduce.
3. Operacje bazo-danowe. Join R(A,B) i S(B,C)

   map ("X", x, y) { if ("X" == "R") emit(y->(1,x)) else emit(x->(2,y)) }
   reduce(x->L) { 
     pogrupuj L: [1 -> L1, 2 -> L2]
     forall(a <- L1; c <- L2)
       emit((a, x, c) -> (a, x, c))
   }
   

4. Mnożenie macierzy kwadratowych $M = [m_{i,j}]$ i $N= [n_{i,j}]$ rozmiaru $n\times n$

   STEP I:
   map ("X", i, j, x) { if ("X" == "M") emit(j -> (1,i,x)) else emit(i->(2,j,x)) }
   reduce(x->L) { 
     pogrupuj L: [1 -> L1, 2 -> L2]
     forall((1,i,x) <- L1; (2,k,y) <- L2)
       emit((i, k) -> x*y)
   }
   STEP II : mapper = identity
   reduce ((i,k) ->L) {emit ((i,j) -> Sum(L))}
   

Indeks TF.IDF

1. $D_1, \ldots, D_m$ - zbiór dokumentów
2. $w_1, \ldots, w_n$ - zbiór słów występujących w dokumentach
3. $n_{i,j}$ = liczba wystąpień słowa $w_i$ w dokumencie $D_j$
4. $TF_{i,j} = \frac{n_{i,j}}{\sum_a n_{a,j}}$ (term frequency)
5. $IDF_i = \log_2\left(\frac{m}{|\{j: w_i \in D_j\}|}\right)$ (inverted document frequency)
6. $TF.IDF_{i,j} = TF_{i,j} \cdot IDF_i$

Similar items

1. Podobieństwo Jaccarda: $J(A,B)= \frac{|A\cap B|}{|A\cup B|}$
2. Dla $\Omega=\{1,\ldots, L\}$ , $A \subseteq \Omega$ i permutacji $\pi$ zbioru $\Omega$ określamy $$ m(\pi, A) = \min\{k: \pi(k) \in A\}~. $$
3. Twierdzenie: $\Pr_{\pi}[m(\pi,A)=m(\pi,B)] = J(A,B)$.
   Dowód tego twierdzenia powinniście znać.
4. wkrótce uzupełnię tutaj najważniejsze hasła....

22.11.2018: Filtry Blooma

1. Wzór na "false positive": $$\Pr[\mathrm{False Positive}] = \left(1-\left(1-\frac1m\right)^{kn}\right)^k ~,$$ gdzie: $m$ = rozmiar tablicy, $n$ = liczba wstawianych obiektów, $k$ = liczba funkcji haszujących
2. Tw. Dla ustalonych $m$ i $n$ liczba $k \approx \ln 2 \cdot \frac{m}{n}$ minimalizuje $\Pr[\mathrm{False Positive}]$
3. Orginalny artykuł Burtona Bloom'a z roku 1970: Bloom.pdf
4. Fajny artykuł Andrei Brodera and Michaela Mitzenmachera z roku 2005: im2005b.pdf
5. Zasada: jeśli używasz list lub zbiorów, a pamięć jest jest istotnym ograniczeniam oraz efekt fałszywych alarów nie jest istotnym problemem, to rozważ zastosowanie filtrów Blooma