We provide a simple method and relevant theoretical analysis for efficiently
estimating higher-order lp distances. While the analysis mainly focuses on l4,
our methodology extends naturally to p = 6,8,10..., (i.e., when p is even).
Distance-based methods are popular in machine learning. In large-scale
applications, storing, computing, and retrieving the distances can be both
space and time prohibitive. Efficient algorithms exist for estimating lp
distances if 0 < p <= 2. The task for p > 2 is known to be difficult. Our work
partially fills this gap.

We show that information about social relationships can be used to improve
user-level sentiment analysis. The main motivation behind our approach is that
users that are somehow "connected" may be more likely to hold similar opinions;
therefore, relationship information can complement what we can extract about a
user's viewpoints from their utterances.

In this paper, we propose to (seamlessly) integrate b-bit minwise hashing
with linear SVM to substantially improve the training (and testing) efficiency
using much smaller memory, with essentially no loss of accuracy. Theoretically,
we prove that the resemblance matrix, the minwise hashing matrix, and the b-bit
minwise hashing matrix are all positive definite matrices (kernels).
Interestingly, our proof for the positive definiteness of the b-bit minwise
hashing kernel naturally suggests a simple strategy to integrate b-bit hashing
with linear SVM.

Estimating the p-th frequency moment of data stream is a very heavily studied
problem. The problem is actually trivial when p = 1, assuming the strict
Turnstile model. The sample complexity of our proposed algorithm is essentially
O(1) near p=1. This is a very large improvement over the previously believed
O(1/eps^2) bound. The proposed algorithm makes the long-standing problem of
entropy estimation an easy task, as verified by the experiments included in the
appendix.

This empirical study is mainly devoted to comparing four tree-based boosting
algorithms: mart, abc-mart, robust logitboost, and abc-logitboost, for
multi-class classification on a variety of publicly available datasets. Some of
those datasets have been thoroughly tested in prior studies using a broad range
of classification algorithms including SVM, neural nets, and deep learning.

In terms of the empirical classification errors, our experiment results
demonstrate:

Compressed Counting (CC), based on maximally skewed stable random
projections, was recently proposed for estimating the p-th frequency moments of
data streams. The case p->1 is extremely useful for estimating Shannon entropy
of data streams. In this study, we provide a very simple algorithm based on the
sample minimum estimator and prove a much improved sample complexity bound,
compared to prior results.