collocation extraction is the task of extracting n-grams from text that would co-occur next to each other more often than chance.

A combination is a choice task which shows that order does not matter.

\begin{equation} \mqty(n \\k) = \frac{n!}{k!(n-k)!} = n! \times 1 \times \frac{1}{k!} \times \frac{1}{(n-k)!} \end{equation}

This could be shown as follows: we first permute the group of people \(n\) (\(n!\)); take the first \(k\) of them (only 1 chose); we remove the overcounted order from the \(k\) subset chosen (\(\frac{1}{k!}\)),; we remove the overcounted order from the \(n-k\) subset (\(\frac{1}{(n-k)!}\)).

combinator is a variable free programming language; it is a turing complete computational formalism.

• this is a language of functions
• it is extremely minimalist
  • clear away the complexity of a real language
  • allows for illustration of ideas

combinator

a combinator is a function with no free variables

Why do we care?

• no variables! its entirely compositional
• all computations are rewrite rules => making proofs like confluence, etc. easier
• its functional: we don’t reason about individual data accesses, which is a natural fit for bulk and parallel data
  • …variables are often a problem is parallel computation

Why do we not care?

Duplication is really hard in SKI; we had to use \(S\) and possibly a \(K\) to get multiple thing to be passed. This is basically the only way we can pass information around—we have to drill any data all the way down with \(S\) until you consume it