Machine Learning and Algorithms

NP, NP-complete and NP-hard

2010-05-01T14:35:00.000-07:00

If a problem can be verified in polynomial time, then it's in the NP class. Another definition: if the language of a problem can be accepted by some polynomial-bounded non-deterministic Turing machine. If the language can be accepted by some polynomial-bounded deterministic Turing machine, then it's in P. Thus, P \in NP.

Apparently finding the solution itself can be hard, although the verification is often trivial.

Reducibility: If A reduces to B in polynomial time. B can be harder? At least as hard.
like SAT <=p 3SAT. 3SAT is harder. If we can solve 3SAT, we solve all SAT problems.

If all problems in NP can be reduced to A, then A is NP-hard. A doesn't have to a NP problem. So there are some NP-hard problems that are not in NP? If we solve a NP-hard problem, we solve all NP problems, including those NP-complete ones.

Seems not all NP-hard problems are equally hard. Those are not in NP are harder?

If we can show a problem is in NP, and it's NP-hard, then it's a NP-complete problem. seems NP-Complete are the hardest problems in NP? And also are all NP-complete problems equivalent?

So next mission for scientist: find one NP-complete problem and solve it!

Expectation Maximization

2010-04-25T15:49:00.001-07:00

EM algorithm is a way of optimization that deals with hidden data. It consists of two steps:

1. Expectation: fill-in the hidden values so the function (e.g. likelihood) can be computed.
2. Maximization: maximize the function above

K-means:
choose some seed centers

classify: assign each point's membership. (M)
recenter: recalculate the center. (E)

k-means optimizes \min_mu \min_C \sum_i |\mu_C(i) - x_i|^2. C(i) is membership center for point x_i. \mu_j is the center for class j. k-means converges because it increases this function in each iteration (or it stops increasing when converged)

Gaussian Mixture:

choose some seed center. so we know which point comes from which component \mu

if we know \mu for each point, then the likelihood can be computed! (E)
then maximize it! (M) we will get a set of new \mu. Google to find the updating rule.

GMM is soft clustering since each point belongs to some component only with a probability. K-means is hard clustering.

EM actually maximizes the lower bound of the marginal likelihood.

Chengxiang Zhai has a nice article on EM's application to language modeling.

Logistic Regression vs. Gaussian Naive Bayes

2010-04-22T22:32:00.000-07:00

P(Y=1|X) = 1 / 1+exp(w_0+\sum(w_i X_i))
P(Y=0|X) = exp(w_0+\sum(w_i X_i)) / 1+exp(w_0+\sum(w_i X_i))

log(P(Y=0|X)/P(Y=1|X)) = w_0 +\sum(w_i X_i). So LR has a linear decision boundary.

It's easy to show that LR and GNB

LR doesn't require independence assumption, while Naive Bayesian does. When the data assumption doesn't hold, LR often outperforms GNB.

When feature space's assumption holds, LR and NB learn an identical classifier when # training examples approaches infinity.

GNB converges towards it asymptotic accuracy faster than LR:
When dataset is small, GNB > LR
When dataset is big, LR > GNR

LR estimates P(Y|X) directly, hence discriminative. NB estimates P(X|Y) and P(Y), hence generative.

We use MLE to estimate parameters of GNB, but why use gradient to LR? Because we don't want to assume GNB's feature independence.

Overfitting

2010-04-22T21:14:00.000-07:00

Overfitting refers to the behavior when the model learned has a very poor representation of the original underlying function, i.e. it becomes so complicated, even fits the outliers, and doesn't generalize, e.g. to work well on other datasets.

Typically the more parameters the model has, the better it fits the training data, thus overfitting occurs. However, overfitting problems becomes less severe as the size of the data set increases since the larger data set is, the more complex model we can afford. Regularization is one way of control overfitting.

Overfitting problem is a general property of maximum likelihood, and Bayesian approach can effectively avoid overfitting.

MLE vs. MAP vs. biased estimator

2010-04-20T13:50:00.000-07:00

MLE: you maximize p(x_1,x_2,...x_n)
MAP: you maximize p(u|x_1,x_2,...,x_n)

Mean:


\mu =

for Gaussian,



\mu_{\tiny MLE} = \frac{\sum(x_i)}{N}
\sigma_{\tiny MLE}^2 = \frac{\sum(x_i - \mu_{MLE})^2}{N}

Unbiased estimator:

if expected value of the estimate == true value



E[\mu_{\tiny MLE}] = \frac{E[\sum(x_i])}{N}=\frac{\sum(E[x_i])}{N}=\mu.  YES
E[\sigma_{\tiny MLE}] NO

Relevance Feedback

2010-04-19T18:37:00.000-07:00

In a document retrieval system, when user issues an initial query, the list of documents system returns often consists of relevant and irrelevant documents. After user provides some feedback on the retrieval relevance, explicitly or implicitly, system is able to return a better list of documents by formulating a new query, with most relevant ones ranked first and irrelevant on the bottom.

The theory is try to maximize the similarity between query and relevant documents, while minimizing the similarity between query and irrelevant documents.

How to generate a new query: 1. add new terms. 2. reweight query terms.



q = \arg max_q [sim(q,C_r)-sim(q,C_nr)]

Rocchio algorithm is an example of incorporating feedback to the modified query. The effect is to move query towards the centroid of relevant documents, and move away from the centroid irrelevant documents.

Users are often reluctant to provide feedback to prolong the search interaction. Pseudo-feedback

strange C problem

2010-04-10T18:52:00.000-07:00

void foo() {
int tmp = 1;

int tmp;
}

See if it compiles.

For me, no warning. no error. no nothing. but also no object file generated. doesn't gcc check symbol table for duplicate definition?

Perimeter of a triangle inscribed in a circle

2010-04-01T23:14:00.000-07:00

is not fixed. Consider the easy cases of a right triangle with each corner being 60 degrees and the one with one side going through the center of the circle

Mahalanobis distance

2010-02-21T17:22:00.000-08:00

Wikipedia: It is a useful way of determining similarity of an unknown sample set to a known one. It differs from Euclidean distance in that it takes into account the correlations of the data set and is scale-invariant, i.e. not dependent on the scale of measurements.

For


 x= (x_1, x_2, x_3, ..., x_N)^T

, and covariance matrix S,



D_m(x) = \sqrt{(x-\mu)^TS^{-1}(x-\mu)}


d(x,y)=\sqrt{(x-y)^TS^{-1}(x-y)}

Some ways of inserting Latex code in your apps

2010-02-21T17:18:00.000-08:00

test


\int_{0}^{1}\frac{x^{4}\left(1-x\right)^{4}}{1+x^{2}}dx
=\frac{22}{7}-\pi

Entropy

2010-02-13T00:14:00.000-08:00

[Wikipedia]: Shannon's entropy represents an absolute limit on the best possible lossless compression

for a fair coin X: p(head) = p(tail) = 0.5.

H(X) = -2*0.5*log(0.5) = 1.

when it's not fair, let's say p(head) = 0.6, then

H(X) = -0.6*log(0.6)-0.4*log(0.4) = 0.97

The more even the distribution is (uncertainty is high), the more bits needed for encoding.

#include

int main(int argc, char* argv[]) {

if(argc <>

printf("entropy filename\n");

exit(0);

}

char* fn = argv[1];

FILE* fp = fopen(fn,"r");

char line[255];

float c;

float e = 0.0f;

if(fp != NULL) {

while(fscanf(fp,"%f", &c)!=EOF) {

printf("%f\n",c);

e += c*log(c)/log(2);

}

close(fp);

printf("Entropy:%f\n", 0-e);

}

return 0;

}

Freecell: probability of having no valid move at start

2009-11-15T23:29:00.000-08:00

I love FreeCell crazily. When the game begins, you get 8 columns of cards. The only rule to move a card onto top of another one is that the numbers on two cards are continuous. It's possible that all of the numbers on 8 top cards are not continuous to each other so you have to move some to the free decks. How likely this is to happen?

In practice not very likely. I have played a few hundred games and it didn't happen to me.

BTW, finding a solution to a FreeCell game is NP-complete (according to Wikipedia), but generally one can finish it within a few minutes. Again it shows NP-complete problems are not that hard to solve in practice.

Why chomp() doesn't work under Windows?

2009-06-16T23:45:00.000-07:00

No doubt that chomp() is frequently used in all kinds of Perl scripts. Today, I spent a few seconds on a Perl script file which is to eliminate all the illegal chars of a XML files, expecting to get the work done soon. It wasn't, however. The code looked extremely plain and straightforward, but it simply refused to work. Soon I realized that I was working under Windows - literally the first time I wrote a Perl script under Windows! The problem was EOL, the End-Of-Line mark. While LF('\n') is sufficient to make a new line under *nix, Windows needs CR+LR("\r\n") to separate paragraphs. Here is what I use now:

while($line = <FILE>) {
$line =~ s/\r\n$//;
//do your work
}

Hope this helps.

Business

2008-12-19T20:49:00.000-08:00

I have always been thinking of starting some online business, or online service. Actually, a website. A website of ...

2008-06-05T12:19:00.000-07:00

Naive Bayes:

Semi-supervised:

use integers
when use unlabeled data, we can make the new label fraction
choose top-k

Topic Modeling

2008-06-05T10:22:00.001-07:00

Questions

2008-06-05T10:05:00.000-07:00

thick line: less expressive

Probability

2008-06-05T10:01:00.000-07:00

Bayesian probability
Naive Bayes classifier
LDA
LSI
pLSI
matrix factorization
PLSA

Generative Model & Discriminative Model

2008-06-05T09:56:00.001-07:00

Generative Model
You know P(X|Y) -> You can generate some data according to the likelihood. You classify by P(Y|X) \prop P(X|Y)P(Y)

Discriminative Model
You only know P(Y|X) -> You classify the data directly without knowing the data likelihood