constituents

• \(x \in \qty {0,1}^{m}\) for \(m\) features
• \(y \in \qty {0,1}\) for labels
• \(\phi_{j|y=1}\), for \(p\qty(x_{j} = 1 | y=1)\)
• \(\phi_{j|y=0}\), for \(p\qty(x_{j} = 1 | y=0)\)
• \(\phi_{y}\), for \(p\qty(y=1)\), the “cost prior”

assumption

ASSUME: features in \(x\) are conditionally independent given \(y\)

That is, we assume that:

\begin{align} p\qty(x|y) &= p\qty(x_1, x_2, \dots, x_{1000} | y) \\ &= p\qty(x_1|y) p\qty(x_2|y, x_1) p\qty(x_3|y, x_1, x_2) \dots p\qty(x_{1000}|y, x_1, \dots, x_{999}) \end{align}

Key Sequence

Notation

New Concepts

• multi-variant Gaussian density
• Generative Learning Algorithm

Important Results / Claims

• applying Bayes rule to make prediction makes the sigmoid function

Generative and Discriminate Algorithm

Discriminative Algorithm

Learns \(p\qty(y|x)\), or better yet just \(h\qty(x) \in \qty {0,1}\).

“what’s the distribution over labels”

Generative Algorithm

Learns \(p\qty(x|y)\) as well as a “class prior” \(p\qty(y)\). To make classification decisions, you apply Bayes rule. THINK: Naive Bayes.

Bogo sort!

Consider an algorithm that randomly shuffles the list, check if the list is sorted, and return.

additional information

Expected Running Time

The expected running time is the number of iterations (\(n!\), in expectation) times the time per iteration (\(n\)).

So the expected running time is \(O\qty(n n!)\).

Worst Case Running Time

Infinite (i.e. if randomness is fixed it will take forever).

Some Expectations of Bogo Sort Characteristics

Let \(X_{i} = 1\) if \(A\) is sorted after iteration \(i\), \(0\) otherwise. Assuming distinct entries, then \(\mathbb{E}[X_{i}] = \frac{1}{n!}\) (because your list has \(n\) things, so the chance of any given shuffling being sorted is \(\frac{1}{n!}\).)

how many times do you have to do the trial to get at least one success

constituents

• \(p\) is the probability of one individual success
• \(x\) is the number of trials

requirements

\begin{equation} P(X = x) = \qty(1-p)^{x-1} p \end{equation}

which represents the probability of getting a success on the \(x\) trial

additional information

\begin{equation} \mathbb{E}[X] = \frac{1}{p} \end{equation}

A Las Vegas algorithm is a randomized algorithm that always works and its probably fast.

(This is as opposed to monte-carlo algorithm, which is always fast and probably works.)