2018-12 在职刷题保持状态， 每天1题+ML insights

Day49

Solved 243, 245, 256.

Day50

Solved 65.
Solved 69.

Solved 261 with union-find.

ML Reviewed:

Point estimates:
MLE -> Pros: efficient, consistent and invariant under re-parameterization(func of the estimate is still the MLE of that function.).
           Cons: Not unique, not sure about its uncertainty. Might overfit.
MAP->  Pros: Usually a convex combination of MLE and prior on theta hence approx. to MLE as samples->infy
                    Intepretable
                    Can avoid overfitting.
           Cons: Not invariant
                    Must assume prior on theta.
Bayesian inference:
->Major aspects of Beyesian
->Priors: Conjugate priors, Informative and uninformative priors.
->Naive Bayes (not necessarily a Bayesian method!):
---->argmax_y p(y|x) = p(x|y)p(y)/constant_proportionality, where p(x|y) = p(x|y,theta) and p(y) = p(y|theta)
---->Need to estimate theta first (MLE,MAP, etc)
---->Solve the optimization
Note: x = {x1,x2,x3,....}, we can assume different likelihood on p(x_{i}|y,theta) as they are conditionally indep.

Day51

Solved 148 with Mergesort.
Solved 19.

Solved 27.

Day52.

Solved 28 with KMP.Solved 29
Solved 35.

Day53

Solved 265. To achieve O(nk), the key idea is to keep record of min and second min costs and asscoiated colors of painting i-1 houses. For i-th house and j-th color, if min color for i-1 not equal to j, then use min otherwise use second min.
Solved 323. Union find.

Solved 636. Very confusing start and end time that have differernt meanings.

ML reviewed:


Model-based Bayesian inference. (Model is P(y|theta))

Conjugacy:

Conjugate priors of a likelihood function is the prior distribution that, once times with that likelihood function, resulting in a posterior distribution of same family as the prior

—>The beauty is, you can start with a conjugate prior, incorporate new data, update it to a posterior and then use it as the new prior.

—>This process can continue without introducing new difficulties.

Hierarchical Bayes:

Instead of assuming the prior, you can estimated them by introducing hyper priors of hyper parameter phi on these priors. Choosing hyperprior to be proper, nearly flat.


Predictive posterior:

One cool thing you can do with a full bayesian inference is to do prediction of  P (y_new|y) by integrating out the theta:

P(y_new|y) = inte P(y_new, theta|y) d(theta) = inte  P(y_new|theta)P(y|theta) d(theta)

First term is the model and second term is the product of  Beyesian inference (the posterior).

Bayesian vs Frequentist inference:

1.Bayesian believes data is fixed and our belief on the parameters to be random
2.Frequentist believes the data is random (and repeatedly sampling produce the same data as those observed) and parameter is fixed (i.e., there is one true parameter). No uncertainty on the parameter (confidence interval just gives an uncertainty about the “true” value not the parameter itself)

Day54

Solved 36.
Solved 405. Thought a much more complicated version of this problem to remove all nodes of given value in O(h).

Solved 706.

ML Reviewed:

Naive Bayes and auto clustering (class, model selection…many nicknames):

Irrespective of its name, Naive Bayes it actually more a frequentist method that solves the following
argmax_c P(c|x) = P(x|c)*P(c)/P(x)

it is really a MAP for c assuming coordinates of x conditionally independent on c.

Just like a MAP, need to do two things:
Assume some prior on P(c)
Adopt a model P(c|x) = P(c|x,theta) and estimate theta^ to approximate it with P(c|x, theta^)



Used it to do unsupervised clustering by assuming C = 1, …len(D) clusters. Assume uniform categorical prior on P(c). Just need to check P(C|x) and find C=C* that maximize the likelihood (in this case equal to posterior maximizer.)

This is actually a very common technique to perform model selection.

Day55

Solved 89

Solved 79

Solved 61

Day56

Solved 428.
Solved 611. Similar to threeSum

Solved 83

Day57

Solved 96
Solved 161
Solved 168.

Day58

Solved 163
Solved 171

Solved 179