SU-CS161 OCT212025
Last edited: October 10, 2025Key Sequence
Notation
New Concepts
Important Results / Claims
Questions
Interesting Factoids
SU-CS229 OCT222025
Last edited: October 10, 2025Key Sequence
Notation
New Concepts
Important Results / Claims
Questions
Interesting Factoids
SU-CS254 MAR052025
Last edited: October 10, 2025Review! Probability
Let \(A_1 …, A_{M}\) be independent events, each with probability \(p\). Let \(T = \sum_{i=1}^{n} A_{i}\), meaning \(T \sim \text{Bin}\qty(n,p)\). \(\mu = \mathbb{E}\qty[T] = np\).
Two facts:
Markov bound
\(P\qty [X \geq k \mathbb{E}[x]] \leq \frac{1}{k}\)
;
Chebyshev’s inequality
\begin{equation} P\qty [T \not \in\mu \pm k \sigma] \leq \frac{1}{k^{2}} \end{equation}
Pairwise Independence
Gouldwasser-Sipsr
Given circuit \(C : \qty {0,1}^{n} \to \qty {0,1}\) and some parameter \(s\), there is an AM (one-round interaction) protocol: if \(\#c > 2s\), we will accept with probability \(\geq \frac{2}{3}\); if \(#c \leq s\), we will reject with probability \(\geq \frac{2}{3}\).
Universal Hash Family
Last edited: October 10, 2025\begin{equation} H = \qty {h: \qty {0,1}^{h} \to \qty {0,1}^{k}} \end{equation}
properties of pairwise independence:
- 1 wise independent: \(\forall y, \forall a\), \(P_{h \sim H}\qty [h\qty(y) = a] = 2^{-k}\)
- 2 wise independent: \(\forall y \neq y’\), \(P_{h \sim H}\qty [h\qty(y) = h\qty(y’)] = 2^{-k}\)
You will notice that this is not full randomness, just that there are some amount of randomness.
requirements
For all \(u_{i}, u_{j} \in U\) in the universe, \(n\) buckets in terms of desired randomness, with \(u_{i} \neq u_{j}\), then:
Basics of ML for 224n
Last edited: October 10, 2025Random thoughts as I scan through the book:
Central framing: learning as a means to generalize + predict
Key Tasks
- regression (predict a value)
- binary classification (sort an example into a boolean class of Y/N)
- multi-class classification (sort an example into multiple classes)
- ranking (sorting an object into relevant order)
Optimality of Bayes Optimal Classifier
If you have the underlying data distribution, we can classify \(y\) from \(x\) by choosing: