How many observations do I need to use Naive Bayes? My goal is to apply a Naive Bayes classifier to predict whether a user will like or dislike an item on a website based on a few attributes and his previous feedback.
The problem is that I don’t have a lot of feedback from each user. Usually 10 – 30 observations.  Is that enough for the algorithm to work? Is there a minimum sample size for applying Naive Bayes? 
 A: There is no specific threshold, just bear in mind that the more data you have, the more accurate your predictions will be. However, as long as you are more accurate than a random prediction (or predicting the average), your model provides you some actual insight. You can verify this cross validating your model.
We can have a look at what happens though. Say $Y_j$ is the binary output like/dislike the item $j$. Call $X_1...X_k$ the like/dislike he assigned to the $k$ items he saw. Call $K$ the total number of items. Now we can try to see "when does Naive Bayes "converges" ?" (in the sense that it produces low variance predictions)
$$p(Y_j \vert X_1, \dots, X_n) = \frac{1}{Z_j} p(Y_j) \prod_{i=1}^k p(X_i \vert Y_j)$$
You don't need to worry about $Z_j$ (constant, does not affect the prediction), or $p(Y_j)$ (I will assume you have enough data to estimate it). The critical part is therefore the estimation of $p(X_i \vert Y_j)$.
You have $N$ users, who each saw $k$ items ($k$ may not be constant but we are just interested in an approximation).
On the other hand, you have $K^2$ terms to estimate : $p(X_i \vert Y_j)_{i,j\in[1,K]}$.
Therefore, a first guess would be you need to have : $Nk>>K^2$.
This quickly becomes impractical. If $K=1000,k=10$ you need $N>100 000$ !
How to circumvent this? The idea would be to lower the dimension of the $X$'s to something of dimension $l$, so that you don't need $Nk>>K^2$ but $Nk>>Kl$.
You can do it using field knowledge: group the $X$'s using the fact that they are (say) books, jewels... To reduce the possible number of attributes. You are no longer estimating "the probability to like item $A$ knowing that you liked item $B$ and $C$" but you are estimating "the probability that like item $A$ knowing that you like blue items and jewels".
Restricted Boltzmann machines allow you to do this in an unsupervised fashion. There is a good introduction here : http://blog.echen.me/2011/07/18/introduction-to-restricted-boltzmann-machines/ with movies and possible underlying features.
Once $l$ is fixed, the number $N$ needs to grow linearly if the number of items grows linearly as well.
