Analysis of Sampling Algorithms for Twitter

1 Introduction

With Twitter's rising popularity, the number of Twitter users and Tweets are on a steady upward climb. It has been observed that around 500 million Tweets are generated daily. Twitter data is interesting and important since its impact on applications ranging from public safety, voicing sentiments about events [Mejova et al., 2013], news broadcast, etc., is increasing day by day. The number of Tweets being so large means that there is a necessity to come up with strategies to deal with this data in a scalable fashion. One possible approach to deal with such large amounts of data is to sample the data and work with a subset of the original universe. Sampling Tweets has multiple uses. For example, extractive summarization of Tweets for human readers is essentially a sampling algorithm. Additionally, Twitter itself uses a 1% random sample in its API, which immediately raises questions such as: Can we produce representative samples using simple methods like random sampling? How many Tweets should we randomly sample so that the information contained in the universe is also contained in the sample? In this work, we propose different statistical properties to characterize the goodness of a random sample in the context of Twitter. We derive sufficient conditions on the number of samples needed in order to achieve the proposed goodness metrics. For theoretical analysis, we sample Tweets in a uniform random fashion with replacement.

Topic modeling in Twitter [Hong and Davison, 2010] is done using distributions over keywords which could include nouns like the names of personalities, places, events, etc. Twitter is also widely used to convey opinions or sentiments about these nouns. Motivated by this, we consider two statistical properties to quantify the representativeness of a sample. These are the frequency of occurrence of nouns and the conditional frequencies of sentiments, conditioned on each frequent noun. These frequencies constitute the conditional sentiment distribution of the noun. In order to compute this distribution, we assume that there are three possible sentiments for each Tweet-positive, negative or neutral. The conditional frequencies are computed as empirical frequencies as explained in later sections. In our theoretical analysis and experiments, we assume that a perfect parts of speech tagger [Bird et al., 2009] provides the information on whether a word is a noun or not. Similarly, we assume that our sentiment analysis algorithm accurately classifies the sentiment of each Tweet into one of the three categories.

An overview of our contributions is presented now. We theoretically derive sufficient conditions on the number of samples needed so that:

1. nouns that are frequent in the original universe are frequent in the sample, and infrequent nouns in the universe are infrequent in the sample.

b) the conditional sentiment distributions of frequent nouns in the universe are close to the corresponding conditional sentiment distributions in the sample.

1. the dominant sentiment conditioned on a noun is also dom-

inant in the sample.

The exact statements of these results will be made in later sections. Our bounds are attractive since they do not depend on the number of Tweets in the universe, and depend only on the maximum length of a Tweet which can be readily bounded. We evaluate our theoretical bounds by performing experiments with real Twitter data.

To the best of our knowledge, ours is the first work dealing with ideas of frequent noun mining, which is analogous to frequent itemset mining in the database literature. It is also the first work to deal with ideas of restoring sentiment distributions associated with frequent nouns and preserving dominant sentiments associated with any particular noun. So the articulation and theoretical treatment of these ideas in sampling Twitter data distinguish our work from the current literature. Our ideas and results would be of interest to data providers and researchers in order to decide how much data to use in their respective applications. They could be used as a simple first step in extractive summarization or opinion mining in order to save on computation, especially when Tweets spanning multiple days are to be analyzed.

In the next section we give a literature review, following which, we set up the problem and introduce mathematical notations in Section 3. Sections 4 and 5 are used to state our theoretical results on frequent noun mining and sentiment restoration respectively. We then show our simulations and experimental results with real Twitter data in Section 6. All the main proofs are in the Appendix.

2 RelatedWork

Summarization algorithms for Twitter aim to extract representative Tweets from a large universe for human consumption. These algorithms are closely related to document summarization methods [Nenkova and McKeown, 2012]. Extractive Tweet summarization algorithms have been studied in the literature by [Sharifi et al., 2010], [Yang et al., 2012], [Chakrabarti and Punera., 2011]. A graph based summarization algorithm for a small universe size of 1000 has been proposed in [Liu et al., 2012]. A comparison of various methods for summarizing Twitter data can be found in [Inouye and Kalita, 2011]. These existing Tweet summarization methods are often computationally expensive and would not scale to millions of Tweets, which is typical of the daily Tweet volume. Therefore, as mentioned previously, random sampling could serve as a first step before using any of these algorithms for human readable summaries, provided the random sample is representative of the universe.

There have been many papers that deal with the quality of samples given by Twitter API's free 1% sample. These papers are primarily empirical in nature. In [Morstatter et al., 2013] the authors compare the API's feed with the Tweets obtained from Firehose-which is also provided by Twitter, but contains all the Tweets instead of a sample. In [Ghosh et al., 2013], the authors empirically compare random sampling against sampling done with the help of human experts. In [Morstatter et al., 2014], the authors analyze the bias in Twitter's API without using the costly Firehose data. The effects of using multiple streaming APIs is considered by [Joseph et al., 2014]. As can be seen, there have been many papers on the empirical analysis of the quality of Tweets summaries and the Twitter API itself. It is also understood that random sampling preserves statistical properties of the universe. But to the best of our knowledge there has not been a treatment of the problem from our viewpoint of deriving conditions on sample sizes needed to produce representative samples, and ours is the first study to theoretically characterize the behaviour of random Tweet sampling.

3 ProblemFormulation

The set of Tweets that form our universe of Tweets is denoted by T. This set contains N Tweets, each of which can have a maximum of L words. From N Tweets, we uniformly and randomly sample K Tweets with replacement. The set of Tweets in the sample is denoted using S. Each Tweet is modelled as a bag of words. Moreover, we assume that each Tweet has an associated sentiment, which can be in one of three possible classes-positive, negative or neutral. Some notations used throughout the paper:

Similar notations are used for minus (negative) and neutral sentiments, where we replace p (plus) in the subscript with m and n to denote minus and neutral respectively. The ordered triple of (fw,p, fw,m, fw,n) forms the sentiment distribution conditional on noun w. As mentioned in the introduction, we derive sufficient conditions on the number of samples needed so that important statistical properties of the universe are retained in the sample with the desired probability. We now clarify two points related to our theoretical analysis.

Firstly, the sampling algorithm we use for analysis is a batch sampling method, which fixes a sample size and then does uniform random sampling with replacement. But when Twitter's API gives a 1% sample, it is very likely that it would perform sequential sampling, where each Tweet in the universe would be sampled one-by-one and independent of all other Tweets with probability 1%. We use batch sampling for analysis since the analysis is much cleaner than the case of sequential sampling. Experiments with real data suggest that the performance of both methods depend strongly only on the number of samples, and not on whether sampling is done in batch mode or in sequential mode.

Secondly, our sampling method is random and it may theoretically be possible to derive equations for the exact probabilities of the associated events as a function of K. But computing them and solving the resulting non-linear equations for the sufficient K would be very difficult. Doing this might give stronger bounds for K, but its infeasibility motivates us to derive sufficient conditions on K using bounds on the probabilities instead of the exact probabilities. The sufficient sample sizes would depend only on parameters that govern probabilistic goodness guarantees demanded by the application and not on N, which is an added benefit. In the next two sections, we describe the statistical properties that we want to retain, the associated probabilistic goodness guarantees, and state our results on the sample size bounds.

4 Sampling for θ-frequent Nouns

For a number θ ∈ [0, 1], a noun whose frequency in T is at least θ is said to be a θ-frequent noun. In this section, we derive a sufficient condition on the number of Tweets to be sampled in order to accomplish two goals. For some ϵ ∈ [0, 1], these two goals are:

• Nouns that occur with frequency more than θ in T occur with frequency more than (1 - ϵ/2)θ in S.
• Nouns that occur with frequency lesser than (1 - ϵ)θ in T occur with frequency less than (1 - ϵ/2)θ in S.

We declare a failure event to have occurred if after sampling K Tweets, the algorithm fails to accomplish any one of these two goals. This idea and the theoretical results that follow are very closely related to θ-frequent itemset mining in the database literature. Following the analysis in [Chakaravarthy et al., 2009], if noun w is θ-frequent, then

If noun w's frequency is lesser than (1 - ϵ)θ, we get

To bound the failure probability, we have to bound the probability of failure over all nouns. We can accomplish this using the union bound in conjunction with a bound on the number of nouns. If the dictionary contains M nouns, then the number of nouns in the Tweet universe is upper bounded by min{M,NL}. So we will get that the failure probability is upper bounded by h if

This bound depends on the number of nouns and on the size of the Tweet universe, whereas we would like to derive a bound that depends only on L, since L is easier to upper bound than M or N. In order to derive this bound, we use the results of [Chakaravarthy et al., 2009]. In this direction, we first derive a simple upper bound for the number of θ-frequent nouns.

Lemma 1. The number of nouns that occur with frequency at least θ is upper bounded by L/θ.

Proof. The total number of words ≤NL. A θ-frequent noun would consume at least Nθ words. So the number of θfrequent nouns cannot exceed L/θ.

Lemma 2. If the size of the sample obeys K ≥ 24 ϵ2(1-ϵ)θ (log 8L (1-ϵ)θh +5), then the probability of a failure is upper bounded by 4h for h < 1/4.

Proof. We omit the full proof here since it follows from the proof of Theorem 3.1 in [Chakaravarthy et al., 2009] and from Lemma 1.

5 Sampling for Sentiment Restoration

Since Twitter is used as an important medium for voicing opinions, it is important for the conditional sentiment distribution of nouns in the summary to be close to the corresponding distribution in the universe. For some λ ∈ [0, 1], we say that the sentiment distribution of word w is not restored if the following event occurs

We say that a failure occurs if even a single θ-frequent noun's sentiment distribution is not restored. We want to sample enough Tweets so that the probability of failure is bounded above by h ∈ [0, 1].

Theorem 1. If K ≥ log((hθ)/(6L)) log(1- θ + θ exp{-λ2 /3}) , then the probability of failure to restore sentiment is less than h.

In opinion mining, one may not want to guarantee that the entire distribution conditioned on noun w be restored. One may rather be interested to simply guarantee that the dominant sentiment in the universe also dominates in the sample. A sentiment is said to dominate if its frequency conditioned on w is higher than the other two conditional frequencies. For example, if noun w is such that fw,p > fw,m and fw,p > fw,n, then positive sentiment is said to be the dominant sentiment in the universe. The goal of dominant sentiment preservation is to sample enough Tweets so that this property is preserved with high probability in the sample as well i.e., f S w,p > f S w,m and f S w,p > f S w,n. For deriving the sufficient number of Tweets to guarantee this, we develop a preliminary result in Lemma 3. Let (X1,X2,X3) be jointly multinomial random variables with parameters (M, f1, f2, f3), where f1 + f2 + f3 = 1 and f1 > f2 > f3. Consider first

It can be shown that conditional on X2 = x2, X3 is binomial with parameters (M - x2, f ′3 = f3/(f1 + f3)).

We can use Lemma 3 with similar notations to derive a bound on the number of Tweets that are adequate to preserve the dominant sentiment for noun w. We relabel fw,p, fw,m and fw,n using fw,1, fw,2 and fw,3 such that they are ordered as fw,1 > fw,2 > fw,3. The same notation is followed for Kw,1, Kw,2 and Kw,3. Similarly, we use f ′w,3 = fw,3 fw,1+fw,3 and δw,3 = 1 2f ′w,3 - 1.

Theorem 2. For h ∈ [0, 1], the probability that noun w's dominant sentiment is not dominant in the sample is upper bounded by h if K ≥

6 Simulations and Experiments

6.1 Data Set Description

Using Twitter's free API, we created a data set based on certain important political events of 2014, which we call the PE-2014 data set. This is done by using a comprehensive vocabulary to filter and retain only those Tweets that pertain to certain political events. These Tweets form our Tweet universe with a volume of ∼ 200, 000 Tweets per day. Although this is substantially smaller than the total daily Tweet volume, it could still be too large a set for more sophisticated summarization algorithms, especially if we want to summarize Tweets from multiple days. Our simulation results are obtained over one day's worth of data (March 22, 2014).

6.2 Theoretical Bounds

To characterize the bounds given by our theoretical results, we need an estimate or an upper bound for L. For these results, we estimate L to be 33 words by going through the entire PE-2014 data set once. If going through the universal Tweet set once is too costly, then an upper bound for L would be 140, which is the maximum number of characters allowed per Tweet. Fig. 1 shows the number of samples needed to achieve the conditions in Lemma 2. While some of the sample sizes could be large, the values are still smaller and independent of the total daily Tweet volume. Fig. 2 shows the bound in Theorem 1 as a function of the probability of failure to restore the sentiment distribution of all θ-frequent nouns. This is plotted for different values of the deviation λ and θ. The values in Fig. 2 are much smaller that the values in Fig. 1. This is because in Theorem 1, we do not impose any conditions on the frequency of θ-frequent nouns in the sample. Therefore for these settings of θ, ϵ and λ, the sufficient condition on sample size for frequent noun mining is also sufficient for sentiment preservation. In [Riondato and Upfal, 2012], the authors derive bounds for frequent itemset mining in terms of the VC dimension. This could give us tighter bounds for frequent noun mining, but it is part of our future work.

The leftmost panel of Fig. 3 compares the theoretical bounds for dominant sentiment preservation (Theorem 2) and sentiment distribution restoration for a single noun. For the same failure probability, the bounds on the sample size for preserving the dominant sentiment are much smaller than the bound on the sample size for restoring the entire distribution. In the middle panel of Fig. 3, we compare the two cases of dominant sentiment preservation shown in the left panel. One would expect the case with fw,1 = 0.9, fw,2 = 0.06, fw,3 = 0.04 to have a smaller sample size bound as compared to fw,1 = 0.45, fw,2 = 0.35, fw,3 = 0.2, due to the closeness of frequencies in the latter case. This intuition is confirmed in the middle panel. It is also possible to encounter cases when the bounds for order preservation are larger than the bounds for distribution restoration as seen in the rightmost panel of Fig. 3. Since the conditional frequencies of the sentiments are very close to each other (fw,1 = 0.35, fw,2 = 0.33, fw,3 = 0.32), the number of samples needed to preserve their order exceeds the number of samples needed to restore their distribution for these parameters. In such cases though, preserving sentiment order may not be important since human users may conclude that no sentiment really dominates.

6.3 Experiments with Real Data

We measure the sample quality in terms of statistical properties and failure events related to the theoretical formulation, and compare themwith the theoretical results for a range of sample sizes. For identifying θ-frequent nouns, the error events measured over 100 Monte Carlo rounds are shown in the second column of Table 1. We measure the maximum deviation in sentiment for word w as

The third column of Table 1 shows the maximum deviation in Eq. 3, maximized over the θ-frequent nouns and averaged over 100 Monte Carlo rounds.

From the second column of Table 1, we infer that for θ = 0.1 and ϵ = 0.1 it would be sufficient to sample around

8000 Tweets in order to satisfy the θ-frequent noun mining condition for these parameters. In Lemma 2, the ϵ parameter, the constant factor, and the need to make infrequent nouns of the universe infrequent in the sample makes the theoretical bounds in Fig. 1 much larger than the ones needed in practise. Also, we see from the third column of Table 1 that it is enough to sample 2000 Tweets to achieve a mean maximum sentiment deviation of 0.0952 for θ = 0.1. These agree with the sufficient conditions in Theorem 1 and are quite close to the bounds shown in Fig 2. Table 2 shows that the number of errors in sentiment order preservation for three most frequent nouns is negligible. The last line is for a fourth noun whose sentiment order is intuitively hard to preserve.

6.4 Comparison with Sequential Sampling

In sequential sampling we go through the Tweets in the universe one-by-one and sample a Tweet independent of others with probability p. For the same data set, we perform sequential sampling with two different p values-0.01 and 0.02. For each value of p, we perform 100 Monte Carlo rounds and measure the same metrics as in batch sampling. These results are shown in Table 3. From this table, we see that the performance of sequential sampling and random sampling with replacement (shown in Table 1) are very similar, and are primarily influenced by the sample size alone.

7 Conclusion

In this work we have derived bounds on the number of random samples needed to guarantee statistically representative Tweet samples. Random sampling can be used as a first step before using other sophisticated algorithms to form human readable summaries or for mining social opinion. For example, if we want to find out Twitter sentiment for a keyword that we know is frequent in the universe, then we could run our sentime nt analysis tools on a much smaller random sample whose size does not depend on N. Therefore, using random sampling as a first step could provide significant computational savings for many such applications with practical accuracy requirements. Our experiments with real data confirm that the bounds agree with the sample sizes needed in practice. Our results would readily apply to frequent topic mining and restoring topic models represented as mixture distributions in order to sample a diverse set of Tweets. These ideas also easily extend to applications beyond Twitter to other short messages such as call center transcripts. The theoretical analysis of sequential sampling is part of our future work. Moreover, the bounds for frequent noun mining could be made tighter by using the VC dimension ideas from [Riondato and Upfal, 2012], which is also part of our future work.

8 Appendix: Proofs

8.1 Proof of Theorem 1

The event of the sentiment distribution of word w not being preserved is:

First consider the event {|f S w,p - fw,p| > λ} conditional on KSw. Conditional on a realization of KSw, KSw,p is a binomial random variable with parameters KSw and fw,p. So we can use Chernoff's bound [Chernoff, 1952] for binomial random variables to derive an upper bound on the probability of the event.

We can remove the conditioning by taking expectation over all possible realizations of KSw to get:

The expectation in the Eq. 5 is over the realizations of KSw. This expectation is the moment generating function of a binomial random variable with parameters (K, fw) evaluated at -λ2 /(3fw,p) [Papoulis and Pillai, 2002]. Using the union bound and adding the bounds for the three sentiments we have

P{Sentiment not preserved for noun w}

In order to bound the probability of failure, which is the probability that the sentiment distribution of at east one θ-frequent noun is not preserved, we again apply the union bound over all θ-frequent nouns. The function of fw on the R.H.S. of Eq. 6 decreases with fw. Since we have taken w to be θ-frequent, this expression is maximized by substituting θ in place of fw. Moreover, the bound on the number of θ-frequent nouns is L/θ, which gives the upper bound on the probability of failure to preserve sentiment for any θ frequent noun as (6L/θ)[1 - θ + θ exp(-λ2 /3)]K . So if K ≥ log((hθ)/(6L)) log(1- θ + θ exp{-λ2 /3}) then the probability of failure will not exceed h-proving Theorem 1.

8.2 Proof of Lemma 3

The application of Chernoff's bound to get Eq. 7 is possible since f1 > f3 resulting in f ′3 < 1/2. The marginal distribution of M - X2 is binomial with parameters (M, 1 - f2). Taking expectation w.r.t. X2, we get

By symmetry

Now we can use the union bound and write the probability that X1 is smaller than either X2 or X3 as

The bound in Eq. 8 can be further simplified by considering δ2 3 2+δ3 f ′3 . This is equal to f ′3 (2f ′3-1)(4f ′3+1) , which is a decreasing function of f ′3 if f ′3 < 1/2. This holds because we have taken f ′3 to be f3 f1+f3 and assumed that f1 > f3. Since f2 > f3, we have f ′2 = f2 f1+f2 > f3 f1+f3 = f ′3. Consequently, exp{- δ2 3 2+δ3 f ′3} > exp{- δ2 2 2+δ2 f ′2}. Now we can write the bound in Eq. 8 as

This concludes the proof of Lemma 3.

8.3 Proof of Theorem 2

We follow a similar proof by conditioning first on a realization of Kw. Conditioned on Kw, (Kw,1,Kw,2,Kw,3) are jointly multinomial with parameters (Kw, fw,1, fw,2, fw,3). From Lemma 3, we have

We average over Kw again whose marginal distribution is binomial with parameters (K, fw). This gives the probability generating function [Papoulis and Pillai, 2002].

So if

K ≥

then the probability of noun w's sentiment is not preserved is lesser than h. This proves Theorem 2.