Suppose you have dataset \(\qty(x^{1}, y^{1}) …, \qty(x^{n}, y^{n})\), where \(y^{(j)} \in \qty {1,2,3,4}\).

We can learn a model of this

\begin{align} \max_{\theta} L\qty(\theta) &= \prod_{i=1}^{n} p\qty(y^{(i)} \mid x^{(i)}; \theta) \\ &= \prod_{i=1}^{n}\theta_{1}^{1\qty {y_{i} = 1}} \dots \theta_{4}^{1\qty {y_{i} = 4}} \end{align}

the derivative ends up being nice.

Derivation

Consider a multinomial distribution in 4 elements. Let’s write this in terms of a n exponential family. Consider:

\begin{equation} \begin{cases} T\qty(1) = \mqty(1 & 0 & 0) \\ T\qty(2) = \mqty(0&1&0) \\ T\qty(3) = \mqty(0&0&1) \end{cases} \end{equation}

Consider:

\begin{equation} T\qty(n) = 2 T\qty(\frac{n}{2}) + n \end{equation}

We can get the recurrence relation.

guess the answer

We can try to expand the middle by plugging stuff in:

• \(T\qty(n) = 2T\qty(\frac{n}{2}) +n\)
• \(T\qty(n) = 2\qty(2 T\qty(\frac{n}{4})+ \frac{n}{2}) + n\)
• \(T\qty(n) = 4T\qty(\frac{n}{4}) + 2n\)
• …

We can guess the pattern by staring at it: \(T\qty(n) = 2^{j} T\qty(\frac{n}{2^{j}}) + j\cdot n\) is true for all \(j\).

Suppose \(j= \log \qty(n)\) (that’s where \(T\qty(n)\) disappears), \(T\qty(n) = n\qty(\log \qty(n) + 1)\).

requirements

• \(h\qty(x)\) the predictor function
• \(x,y\), the samples of data

definition

\begin{equation} J\qty(\theta) = \frac{1}{2} \sum_{i=1}^{n}\qty(h_{\theta }\qty(x^{(i)}) - y^{(i)})^{2} \end{equation}

see also example: gradient descent for least-squares error.

additional information

“why the 1/2”?

Because when you take \(\nabla J\qty(\theta)\) you end up with the \(\frac{1}{2}\) and the \(2\) canceling out.

probabilistic intuition for least-squares error in linear regression

Assume that our dataset \(\qty(x^{(i)}, y^{(i)}) \sim D\) has the following property: “the true \(y\) value is just our model’s output, plus some error.” Meaning:

Suppose you have a dataset of two features, you can write a predictor \(h\qty(x)\) in:

\begin{equation} h\qty(x) = \theta_{0} + \theta_{1} x_{1} + \theta_{2} x_{2} \end{equation}

This is a smidge unwieldy, because we have to keep tacking up \(\theta\) terms with an exception whenever we have new features. So, a trick, is that we set \(x_0 = 1\). This yields equivalently…

definition

\begin{equation} h\qty(x) = \sum_{j=0}^{m} \theta_{j} x_{j} = \theta^{T} x \end{equation}

A general recurrence relation solution formula. It’s a generalization of the “tree” method in example 1.

intuition

Every Recursion Theorem problem has a struggle between most work sitting at the “bottom” of the tree (number of subproblems explode, \(a > b^{d}\)) vs most work sitting at the “top” of the tree (problem lower in the tree are smaller, \(a < b^{d}\)).

constituents

Consider:

• \(a\): number of subproblems
• \(b\): input size shrink
• \(d\) need to do \(n^{d}\) work to merge subproblems

Suppose \(a \geq 1, b> 1\), and \(d\) are constants. Suppose \(T\qty(n) = aT\qty(\frac{n}{b}) + O\qty(n^{d})\), we then have: