Oracle Polynomial Time, Space Complexity, Approximation Algorithms and PCP Theorem

Key Sequence

Notation

New Concepts

Important Results / Claims

Questions

Interesting Factoids

“regularization”: removing columns (i.e. explicitly making things roughly degenerate to fit more generally)

“tall full-rank matrix” (i.e. let \(A\) be \(m \times n\), such that \(m \geq n\)).

Solving such full-rank linear systems—

\begin{equation} Ac = b \implies U \Sigma V^{T} c = b \implies \Sigma \qty(V^{T}c) = U^{T} b \end{equation}

We can now solve this above by simply dividing by the nonzero singular values of each row (since we are full rank, this is true). The last equations are zero.

model function, nearest neighbor method, data interpolation, overfitting and underfiting, regularization

noise vs. features

If you know a property of the underlying distribution, noise and the important underlying feature could look very similar (think a sinusoid vs. just Gaussian noise).

learning

learning is the practice of training a system to do something….

knowledge based system

A John McCarthy-esque learning system using knowledge: 1) knowledge base, with explicit facts with experts and 2) an inference engine, a way to reason and generate new facts.