extfieldsofstudy:
Computer Science
Mathematics

text:
Unifying Human and Statistical Evaluation for Natural Language Generation

How can we measure whether a natural language generation system produces both high quality and diverse outputs? Human evaluation captures quality but not diversity, as it does not catch models that simply plagiarize from the training set. On the other hand, statistical evaluation (i.e., perplexity) captures diversity but not quality, as models that occasionally emit low quality samples would be insufficiently penalized. In this paper, we propose a unified framework which evaluates both diversity and quality, based on the optimal error rate of predicting whether a sentence is human- or machine-generated. We demonstrate that this error rate can be efficiently estimated by combining human and statistical evaluation, using an evaluation metric which we call HUSE. On summarization and chit-chat dialogue, we show that (i) HUSE detects diversity defects which fool pure human evaluation and that (ii) techniques such as annealing for improving quality actually decrease HUSE due to decreased diversity.

Introduction
Generating text is a core part of many NLP tasks such as image captioning (Lin et al., 2014), opendomain dialogue , story generation (Roemmele, 2016), and summarization (Nallapati et al., 2016). However, proper evaluation of natural language generation has proven difficult (Liu et al., 2016;Novikova et al., 2017;Chaganty et al., 2018). A good evaluation metric should not only capture the quality of generation, but also the diversity of generation, which is especially crucial for creative, open-ended tasks like dialogue or story generation.
Human evaluation, which is often viewed as the gold standard evaluation, captures quality but fails to capture diversity. As an example, for language modeling, a model that directly plagiarizes sentences from the training set would pass the human quality bar but would have zero generalization ability and thus have inadequate diversity. On the other hand, statistical evaluation-i.e., perplexity on a reference test set-captures diversity, as it ensures a model must assign reasonable probability to novel sentences, but perplexity provides an inadequate measure of quality (Theis et al., 2015). For example, modifying a perfect model by removing its ability to generate even a single test sentence results in infinite perplexity even though the model is still near-perfect. Automatic metrics such as BLEU (Papineni et al., 2002) and ROUGE (Lin and Rey, 2004) capture quality better than perplexity but still correlate poorly with human evaluation and fail to capture diversity (Novikova et al., 2017;Chaganty et al., 2018).
Existing approaches to combining statistical and human evaluation have been ad-hoc, leading to misleading performance measures. A common approach is to measure diversity through the perplexity of a probabilistic model and quality through human evaluation on beam-searched outputs. This gives the illusion that a single model is high-quality and diverse, while the reality is that it shows we can have either a diverse model (when sampling from the distribution used to compute perplexity) or a high-quality model (when beamsearching).
In this paper, we define the idealized evaluation metric as twice the error of the optimal discriminator for classifying sentences as coming from the reference distribution or the model (Section 2). If a model generates gibberish (low quality), the optimal discriminator can classify these accurately as coming from the model. If the reference distribution contains sentences the model cannot generate (low diversity), the optimal discriminator can classify these accurately as coming from the reference.
Unfortunately, the optimal discriminator is unavailable. Human discriminators cannot capture diversity effectively, and learned discriminatorse.g., from a Generative Adversarial Network (Goodfellow et al., 2014) or one trained on human judgments (Lowe et al., 2017)-are too unreliable to use for rigorous evaluation.
Our key result (Section 3) is based on the observation that the optimal classifier depends only on two numbers: the probability of a sentence under the model and the probability under the reference distribution. The former can be computed directly from the model, and we show that the latter can be well-approximated by human judgment scores. The resulting two-dimensional space is illustrated in Figure 1. We apply a simple k-nearest neighbor classifier in this space and define Human Unified with Statistical Evaluation (HUSE) as twice the leave-one-out error of this classifier.
We apply HUSE to four natural language generation tasks (Section 5): language modeling, chitchat dialogue, story generation, and summarization. First, we show that human evaluation alone is insufficient to discriminate model generations from the references, leading to inflated estimates of model performance. In contrast, HUSE is able to reveal deficiencies of current models. We also show that common techniques for improving sample quality such as annealing actually increase distinguishability between the model and reference due to losses in diversity.

Optimal Discriminator
Consider a natural language generation task where the model is given a context x (e.g., a dialogue history) drawn from some prior p(x) and must output a distribution over possible sentences p model (y | x). We define an idealized evaluation metric based on whether p model is close to a reference distribution p ref , which is generally human-generated. 1 Specifically, consider a random variable y drawn from either the reference or the model based on an indicator z ∼ Bernoulli 1 2 : (1) Define L * to be twice the lowest possible error over any discriminator f that attempts to determine z based on x and y: Obstacles. Unfortunately, L * is unattainable because it requires computing the optimal discriminator. In the spirit of the Turing Test, we could consider using the error rate of a human discriminator f hum instead, often considered the gold standard for evaluation. However, while humans might have knowledge of p ref , they do not have full knowledge of p model and thus would have difficulties determining which sentences a model cannot generate. As a concrete example, suppose p ref placed a uniform distribution over some set S. Without knowledge of p model the most sensible discriminator is to predict z = 1 (reference) when y ∈ S. This discriminator achieves the same classification error of 0.5 for both the perfect model p model = p ref and one which can only return a single y ∈ S. We could try to reveal p model to humans by showing multiple samples simultaneously, but this is expensive and, as we will later see, unnecessary.
Another option is to learn f over an expressive class of functions such as neural networks on data sampled from p model and p ref . This is analogous to learning the discriminator in a Generative Adversarial Network (GAN) (Goodfellow et al., 2014) or learning an evaluation metric from human judgments (Lowe et al., 2017). However, as (x, y) are high-dimensional objects, training a good classifier is extremely difficult (and perhaps not significantly easier than solving the original generation problem). Indeed, learned evaluation metrics do not generalize very well (Lowe et al., 2017;Chaganty et al., 2018). Unlike these approaches which seek to replace human evaluation, our focus will instead be on combining human and automatic statistical evaluation to estimate the optimal classifier error.

Human Unified with Statistical Evaluation (HUSE)
Our key result is that the optimal discriminator depends on (x, y) only through a two-dimensional sufficient statistic (Section 3.1), motivating an approximation which we call HUSE (Section 3.2). For any feature map φ that maps (x, y) to φ(x, y) ∈ R d , define the evaluation score L(φ) to be twice the error rate of the optimal discriminator that depends on (x, y) only through φ: Note that the evaluation score L(φ) given by a feature map φ optimizes over all functions that depend on φ (3). Thus, the more information φ contains, the lower L(φ) is. This has two implications: First, any feature map φ yields an (optimistic) upper bound on L * (2), meaning that L(φ) might be able detect when a model is poor but cannot certify that it is good. Second, adding features to φ can only improve this bound.

Two features suffice
Let us consider the following two-dimensional feature map: From the arguments above, it is clear that L(φ opt ) ≥ L * , but perhaps more surprisingly, we actually have equality: Proposition 1. The two-dimensional feature map φ opt achieves the optimal discriminator score: L(φ opt ) = L * .
Proof We compute the true posterior over z given x, y. Since p(z = 1) = p(z = 0) = 1 2 , p(y | x, z = 1) = p ref (y | x) and p(y | x, z = 0) = p model (y | x), by Bayes' rule: The optimal discriminator simply predicts z = 1 if p ref (y | x) > p model (y | x) and z = 0 otherwise. In other words, the decision boundary is given by More generally, we can obtain this equality with a wider class of φ. It will hold exactly for any invertible transformation of φ opt (Appendix Corollary 1), and approximately for any φ which has high mutual information with φ opt (Appendix Theorem 1). This means that we can substitute p ref with noisy, possibly un-normalized estimates and still obtain accurate estimates of L * .

HUSE features
While we can directly compute p model (y | x) for many probabilistic models, is not computable. However, the wisdom of the crowds (Surowiecki, 2004;Ungar et al., 2012) suggests that pooling together the judgments of many humans can often produce surprisingly reliable estimates of real-world probabilities such as p ref (y | x), even if no individual human is particularly reliable. With this motivation, we ask Amazon Mechanical Turk workers to rate a sentence from 1-5 based on how "typical" it is as a way to estimate p ref (y | x). (see Appendix A.3 for more details). We define HJ(x, y) to be the average response over 20 crowdworkers. Figure 2 shows that for a language modeling task on the Reddit corpus, 3 HJ(x, y) strongly correlates with the actual log-frequency of y in the corpus. The high correlation suggests that human judgments HJ(x, y) are a good surrogate for log p ref .
In addition, we found that rather than using the model probability p model (y | x) directly as a feature, normalizing by sentence length len(y) yielded lower (tighter) scores. We therefore define the HUSE features as follows: (HJ) of the "typicality" of a sentence y correlates strongly (r = 0.92) with its frequency in the corpus, suggesting that HJ is a good surrogate for log pref.
Error bars at the 90% confidence interval. and define the (population) HUSE score as L(φ huse ).

Guarantees derived from HUSE
We now show that the HUSE score satisfies two nice properties: (i) HUSE does at least as well as human evaluation and (ii) a low HUSE score is sufficient to show that a model is far from the reference distribution.
To show (i), consider a feature map that only includes human evaluation: Because φ huse also incorporates human evaluation, L(φ huse ) is always tighter (lower) than the human discriminator error L(φ hj ): Proposition 1 (Relationship between HUSE, human evaluation, and optimal scores).
Furthermore, the main difference between L(φ huse ) and L * is that the former uses HJ(x, y) and the latter uses p ref . But as we argued using Figure 2, HJ(x, y) is strongly correlated with p ref , and good approximations to p ref provide approximation guarantees for L(φ huse ) (Appendix Theorem 1).

Evaluating models with HUSE
In this section, we show how we can estimate the error rate L(φ) from finite data (Section 4.1). We then show how the HUSE estimate (L(φ huse )) can be decomposed into a score that measures quality (HUSE-Q) and a score that measures diversity (HUSE-D), which allows us to study qualitydiversity tradeoffs (Section 4.2).

Learning a discriminator
For any feature map φ, we show how to produce an estimate of L(φ). Fix n contexts x 1 , . . . , x n . First, we draw n examples y 1 , . . . , y n from the reference distribution p ref (y | x), which are usually human-generated sentences from a test set. We also draw n examples y 1 , . . . , y n from the model p model (y | x) we wish to evaluate. Next, for each of the 2n examples (x, y), we compute the feature map φ(x, y), which might involve evaluating the model probability p model (y | x) as well as collecting human judgments HJ(x, y) from crowdworkers.
Finally, we compute the leave-one-out error of a classifier that tries to predict whether a given example (x, y) comes from the reference distribution (z = 1) or the model (z = 0).
The classification problems for HUSE are twodimensional, which allows us to accurately estimate error rates using a k-nearest neighbors classifier. We opt to use nearest neighbors classifiers as they are simple, require no training, and can asymptotically capture arbitrary continuous decision boundaries. Specifically, we set k = 16 and define neighbors using L 2 distances over the feature vectors φ(x, y) scaled componentwise to have unit variance. The overall procedure for computing the estimateL(φ) is formally defined in Algorithm 1.

Quality-diversity decomposition
We now define the (empirical) HUSE score using the feature map φ huse : We define the quality component of HUSE (HUSE-Q) similarly using human judgments alone: Since humans can detect quality defects in a model, any increase in error from removing p model must come from a model's lack of diversity. Therefore, we define the diversity component (HUSE-D) as follows: (9) which implies the decomposition (1−HUSE-D)+ (1 − HUSE-Q) = 1 − HUSE. As long as the discriminators are non-degenerate (obtaining better performance than chance and HUSE > HUSE-Q), all scores are contained in [0, 1]. Here, HUSE-D = 1 implies that the model suffers no diversity defects, while HUSE-D = 0 indicates that the examples could be discriminated perfectly due to a lack of diversity.

Experimental setup
We use HUSE to evaluate three different types of single-sentence natural language generation tasks: (i) unconditional and high entropy (language modeling); (ii) conditional and high entropy (story generation, chit-chat dialogue); and (iii) conditional and low entropy (summarization). We show that HUSE provides a direct and interpretable measure of diversity on high-entropy tasks, while also serving as a useful model diagnostic on lowentropy ones.
The four tasks along with the datasets and models are as follows: • Summarization: Giganews story to headline dataset and the pre-trained model from Gehrmann et al. (2018). The dataset consists of 3.8 million news story-headline pairs. Examples from this dataset are shown in Table 2.
• Story generation: Last sentence generation for ROC stories (Mostafazadeh et al., 2016) consisting of 96,198 examples of partially written four-sentence stories as input, and a single sentence which completes the story as the target. We use a standard OpenNMT model with global attention (Klein et al., 2017).
• Language modeling: One billion word benchmark pre-trained language model from . The task consists of generating a single sentence from the one billion word newswire text distribution.
• Chit-chat dialogue: Two-turn chit-chat dialogue dataset consisting of 37.3 million comment-response pairs from Reddit (Appendix A.4). Comments are generally short (5-15 tokens) and cover a single topic (e.g. given "wow how did i not notice that", the response is "you were focusing on other things its understandable"). We train a convolutional model using fairseq (Gehring et al., 2017).
For all the tasks, we train neural models and evaluate their diversity-quality tradeoffs as we change the decoding scheme for generation. Our primary evaluation concerns diversity trade-offs involving temperature annealing which is a generation technique applicable to any probabilistic model that generates words sequentially. In temperature annealed models, we sample a word w proportional to p 1/t (w) where p is the model probability of w given previous words and t is the temperature parameter. We excluded beam search since it qualitatively behaves similarly to temperature annealing with low temperatures and HUSE ≈ 0 due to beam search being extremely under diverse.
As a non-neural baseline, we also consider retrieval based models based on Apache solr on a few tasks. For this approach, we retrieve the single most relevant response from the training set using the BM25 similarity metric on inputs. Such models are known to perform well in tasks with complex outputs such as program generation (Hayati et al., 2018;Hashimoto et al., 2018) and style transfer .
For cost reasons, we did not measure certain combinations of task and generation mechanisms. We did not measure retrieval for chit-chat dialogue, as we observed its outputs were lower quality than a low-temperature neural model. We also did not anneal language models, as the generation quality from the language model was already high, and our goal was to show that they achieved high HUSE. Our set of measurements, while not comprehensive, generally covers the available qualitydiversity tradeoffs for conditional tasks.

Summarization
Story generation Chit-chat dialogue LM t = 1.0 t = 0.7 t = 1.0 Retrieval t = 1.0 t = 0.  Table 1. Performance achieved by the best models on the four tasks, as measured by overall goodness-of-fit (HUSE), sample quality (HUSE-Q) and diversity (HUSE-D). The scale for HUSE and HUSE-Q ranges from 0.0 (completely distinguishable from reference) to 1.0 (indistinguishable from reference) where the implied classification error is HUSE/2. HUSE-D may exceed 1.0 with small sample sizes when HUSE-Q > HUSE.

Figure 3. Tradeoffs between HUSE-D and
HUSE-Q. Points are models and color indicates task. Neural models (circle) generate using temperature annealing (point labels indicate temperature). Models closer to the top right are superior, and gray diagonal lines indicate equivalent HUSE. A shaded region for a task indicates models which are strictly dominated (worse HUSE with the same HUSE-D-HUSE-Q proportion). Annealing can trade-off between diversity and quality but cannot easily increase the underlying model performance (HUSE).
Finally, we collect human judgments HJ(x, y) as per Section 4.1 where we query 20 Amazon Mechanical Turk crowdworkers for typicality ratings on 100 reference and 100 model sentences. Since our models generate UNK (unknown and out-of-vocabulary) tokens, we instructed crowdworkers to treat UNK tokens as rare, but appropriate words for the context.

Overall results
The HUSE scores across the four tasks vary widely. Table 1 shows that single-sentence language models are nearly indistinguishable, with HUSE = 0.86 and implied discriminator error of 43%.
In contrast, both summarization and dialogue are highly distinguishable (HUSE ≈ 0.5) with relatively low quality when sampled from t = 1.0. Human evaluation alone (HUSE-Q) would suggest that using temperature annealing (t = 0.7) to emphasize high-probability outputs substantially improves the model (HUSE-Q goes from 0.58 to 0.92 for summarization and 0.56 to 0.92 for dialogue). However, we find that this increase in sample quality comes at the cost of diversity (HUSE-D goes from 0.95 to 0.34 for summarization and 1.0 to 0.57 for dialogue). Examining the achievable HUSE and diversity tradeoffs in Figure 3 shows that mechanisms such as annealing which improve sample quality actually degrade HUSE due to severe losses in diversity.
We find that all generation schemes and models are inadequate for story generation on ROC stories. The original model (t = 1.0) is very easily distinguishable by a human (HUSE-Q = 0.15), corresponding to a discriminator error of 7%. The retrieval models can improve this to HUSE-Q = 0.47, but this comes at the expense of diversity.
Finally, we observe that directly sampling from the model (t = 1.0) is always diverse. This suggests that human evaluation is an appropriate evaluation for generation systems that are directly sampled (rather than beam-searched).

Model error analysis with HUSE
Since HUSE is estimated from a two-dimensional classification problem, we can directly visualize the classification problem to understand defects in both model quality and diversity. Figure 4 shows both reference points φ huse (x i , y i ) (blue squares) and model points φ huse (x i , y i ) (red circles) for the summarization task. The shaded areas indicate the decision boundary of the 16-nearest neighbor classifier.
At temperature t = 1.0, we find that the classification boundary is mostly horizontal, implying that human judgment alone can distinguish model outputs from references. There is a cluster of sentences with high HJ and high p model which are essentially indistinguishable. Examining the samples in this top-right region reveals that these are news stories with short headlines such as "Nadal pulls out of Sydney International" which can be T=1.0 T=0.9 T=0.7 Figure 4. The two-dimensional classification problem in Algorithm 1 on the summarization task with different softmax temperatures (three panels). Each point represents a reference sentence φhuse(xi, yi) or model-generated sentence φhuse(xi, y i ). The color denotes the source of the sentence (z), shading is the classification confidence of the nearest neighbor classifier.
reliably generated even at t = 1.0. However, the model frequently generates low quality samples that can easily be distinguished such as "two new vaccines in the poor countries were effective against go-it-alone study says" (Table 2). At lower temperatures of t = 0.9 and t = 0.7, the boundary shifts towards becoming diagonal. Although the distribution is no longer directly separable on human judgment, the two distributions are clearly separable with the inclusion of p model .
Using Figure 4, we can identify individual examples which were correctly and incorrectly classified based on p model and HJ. Table 2 shows examples of both quality failures and diversity failures identified by HUSE. For example, the "diversity failure" table shows that the summarization model (t = 0.7) has an extremely low probability of generating some reference sentences ("NFL's bills shake up front office") and is thus underdiverse. Closer examination of the model shows that the probability of generating "front office" is low, since it is an unusual way to refer to the president and general manager. Improving these models on the diversity failures will require that the model understand more subtle paraphrases. We can also identify model successes, where the model outputs are indistinguishable from the reference in terms of quality ("Agassi bows out of Australian Open after injury"), and the model assigns high probability to the reference ("Agassi withdraws from Australian Open").

HUSE stability
Since HUSE depends on human crowdworker annotations, one might ask if it is possible to reduce either the number of annotated examples, or number of distinct crowdworkers for each example. We show that for low-quality models, substantially fewer annotations are needed.   (Figure 5, left) is often sufficient to give accurate estimates of HUSE. Next, we find that the necessary number of crowdworkers per example depends heavily on the task. Easily distinguishable tasks (story generation), require only 10 crowdworkers, while less distinguishable tasks (summarization) require more than 20 crowdworkers to obtain accurate estimates.

Related work
The current state of NLG evaluation. Existing approaches to NLG evaluation use a hodgepodge mix of quality and diversity measures. Out of the 26 NLG papers at ACL 2018, six perform only human evaluation, fourteen measure human evaluation and a diversity metric such as perplexity or n-gram diversity, and six do not evaluate using human judgments.
While perplexity and n-gram counts can in principle evaluate diversity, their practical implementations suffer from serious drawbacks. When human evaluation and perplexity are both evaluated, they are almost always done on separate Quality failure log pmodel HJ

Context:
Two new vaccines have been shown effective against rotavirus, which is responsible for a half-million infant deaths in poor countries each year, research studies published Wednesday said.

Model
Two new vaccines in the poor countries were effective against go-it-alone study says -2.3 2.6 Reference New vaccines for key <UNK> virus shown effective -4.0 4.3

Diversity failure
Context: The Buffalo Bills sacked Tom Donahoe as president and general manager on Wednesday, fulfilling expectations of a shake-up after another failure to make the National Football League playoffs.

Model
Bills sack <UNK> as president GM and general manager -0.9 4.3 Reference NFL's Bills shake up front office.

Model is indistinguishable
Context: US veteran and eight-time Grand Slam winner Andre Agassi has withdrawn from this month's Australian Open due to a nagging ankle injury, his management team announced Thursday.

Model
Agassi bows out of Australian Open after injury. -1.4 5.3 Reference Agassi withdraws from Australian Open. -0.3 4.9 Table 2. Example reference and model outputs (capitalization added for readability) corresponding to Figure 4 (summarization task) that were shown to crowdworkers (left column). Crowdworkers were shown samples from the model (including the <UNK> token) and returned human judgments (right column). Using human judgments and the model probability ,  models-human evaluations are done on beamsearched output, while perplexity is computed on the softmax outputs. This makes it appear as if the models can simultaneously generate high quality outputs while also being diverse, when in fact they can only be one at a time based on whether they sample or run beam search. On the other hand, n-gram diversity was proposed by Li et al. (2016) to identify models with the generic utterance problem where models repeat phrases such as 'I don't know'. Unfortunately, n-gram diversity is computed across contexts by counting the number of unique n-grams generated, and so does not measure a model's ability to generate multiple valid utterances at any single context. In particular, a model which only outputs a single memorized utterance per context (e.g., via memorization or retrieval) can still have high n-gram diversity as long as the memorized sentences differ across contexts.
Finally, all existing diversity measures are computed separately from human evaluation. This results in two incomparable evaluation metrics, which prevent us from reasoning about tradeoffs between diversity and quality. In contrast, HUSE allows us to make precise statements about the tradeoffs between model quality and diversity because it is a single metric which decomposes into diversity and quality terms.
Related evaluations of diversity. The importance of diverse responses has previously been acknowledged for summarization (Nenkova et al., 2007) and information retrieval (Clarke et al., 2008). Our work differs in considering a single evaluation measure that captures quality and diversity applicable to any generation task.
Automated metrics based on n-gram overlap such as BLEU, METEOR, ROUGE (Papineni et al., 2002;Lavie and Denkowski, 2009;Lin and Rey, 2004) work well for machine translation but do not generalize well to domains with a diverse spectrum of correct responses. While variants (Sun and Zhou, 2012;Shima and Mitamura, 2011) have adapted such metrics to high entropy generative environments, they are still significantly inferior to the human judgments they attempt to mimic. Caccia et al. (2018) recently examined the diversity and quality tradeoffs for different language model architectures on synthetic datasets. However, as their approach relies on measuring loglikelihoods under both the model and reference distributions, it cannot be applied to real data where p ref is unavailable. Our main conceptual contribution overcomes this by showing that HJ is an acceptable proxy for p ref . Sajjadi et al. (2018) also examines diversity and quality (which they call precision and recall) in the context of generative image models. However, they rely on assuming that p ref and p model can be estimated accurately using the Fréchet Inception Distance (FID) (Heusel et al., 2017). HUSE avoids such assumptions and instead directly leverages human judgments, resulting in a simple and reliable metric more suitable for use as a gold-standard.
Estimating optimal classification error. Evaluating a model by estimating its optimal classification error has been considered by several earlier works (Olsson et al., 2018;Kannan and Vinyals, 2016;Li et al., 2017;Bruni and Fernandez, 2017;Bowman et al., 2016). However, these methods have focused on classifying sentences directly, which is quite challenging to do reliably. Existing adversarial evaluation methods do not yet reliably outperform human classification (Kannan and Vinyals, 2016;Bruni and Fernandez, 2017). We propose the use of both human evaluation and model probabilities as part of the adversarial evaluation framework, and demonstrate that the resulting classifier reliably outperforms humans and captures both the sample quality and diversity of a model.
Distributional divergence estimation. Our proposed evaluation metric is closely related to the total variation distance which has been studied extensively in the distribution testing literature. It is known that total variation distance estimates have pessimistic minimax estimation rates in high dimensions (Balakrishnan and Wasserman, 2017). Our work overcomes this by utilizing p model and an estimate of p ref . Other approaches to distributional testing include the maximum mean discrepancy (MMD) and Wasserstein distances, but these approaches require knowledge of a ground truth metric or kernel space (Tolstikhin et al., 2016;Singh et al., 2018). Although such divergences are easier to estimate than the total variation distance from samples, the implied convergence rates are still too slow to be practically useful.

Discussion
In this paper, we demonstrate that the current gold standard of human evaluation does not penalize under-diverse models. To remedy this, we propose HUSE, a general purpose evaluation strategy which can be applied to any model for which we can calculate a model's sampling probabilities. HUSE is an upper bound on the optimal classification error of distinguishing reference and modelgenerated text, and never does worse than human classification. HUSE leverages both model probabilities and human judgments, ensuring that models which do well on the metric are both highquality and diverse.
Our work can be viewed as a "superhuman version" of the classic Turing Test (Turing, 1950). Instead of relying on just a human classifier, we approximate the optimal classifier, which can utilize information about the model in addition to the reference. We also modify the classification problem and seek to identify whether a sample comes from a (potentially superhuman) reference distribution, rather than the human distribution. These two changes lead to tractable, rigorous estimators which can quantify tradeoffs between model quality and diversity on a wide range of generation tasks. y∈S b y be the aggregated probabilities. On S, the optimal discriminator should return z = 0 (model). This is an error when z = 1, which occurs with probability 1 2 A. Analogously, on the complement of S, the error probability (when z = 0) is 1 2 (1 − B). The total contribution to L * is thus A + (1 − B). The rest follows from algebra: A.2 Approximation error from φ features Theorem 1. Let L * and L(φ) be the optimal classification error and optimal error under feature map φ respectively. Then, ) is the conditional mutual information in bits and Z opt is the prediction of the optimal classifier.
The last line follows from the fact that Z opt is a deterministic function of φ opt (Proposition 1). Substituting this into the inequality gives the bound, P (f (φ(X, Y )) = Z opt ) ≤ 1 − 2 −I with I = I(Z opt ; φ opt (X, Y ) | φ(X, Y )).
Finally, note that Z opt incurs L * /2 error, and we disagree with Z opt at most a P (f (φ(X, Y )) = Z opt ) fraction of time. Assuming that we get every one of these disagreements wrong gives an upper bound of L * /2 + P (f (φ(X, Y )) = Z opt ) on L(φ)/2.
A straightforward corollary is that whenever φ is an invertible function of φ opt , the conditional mutual information is zero, and therefore the above inequalities become an equality.

A.3 Amazon Mechanical Turk for human judgments
In order to show that HUSE can be reliably estimated even with simple crowdsourcing techniques, we used a single uniform task design where we asked Amazon Mechanical Turk workers to rate the typicality of a sentence from 0-5. We defined 0 as invalid (grammatically or factually incorrect) and 5 as 'very typical'. HJ(x, y) is defined as the average score that crowdworkers assign to a response y given the context x. We did not perform substantial filtering or qualification checks beyond HIT acceptance rate (HIT Approval rate greater than 95 percent and number of HITs approved greater than 50 and location is USA). We constructed each HIT to be 25 examples, and paid one dollar per HIT. We observe that measuring many replicates is sufficient to get low-variance estimates of HJ. For classification tasks where the model is straightforward to identify from references (such as story generation) we require five to ten replicates, while for hard tasks such as summarization at least twenty replicates are needed (Section 5.4). Manual inspection suggests that up to 20% of the collected data are low-quality but that this noise is uncorrelated with the sentence being rated and outweighed by a larger majority of honest and reasonably accurate data. Even if the data quality is low, HUSE is still a valid upper bound (i.e. models with low HUSE are guaranteed to be distinguishable from humans). Thus the models which we identify as having low-HUSE are reliably distinguishable regardless of the crowdworker quality.

A.4 Reddit Dataset
We use a subset of Reddit comments from 2006-2018 scraped from https://pushshift.io/. We construct a dictionary containing the 10,000 most popular words and preprocess the dataset by removing deleted posts, out-of-vocabulary tokens, profanity, comments with less than 10 upvotes, and comments with over 400 tokens.


extfieldsofstudy:
Physics
Medicine
Computer Science

text:
Type-independent Characterization of Spacelike Separated Resources

Quantum theory describes multipartite objects of various types: quantum states, nonlocal boxes, steering assemblages, teleportages, distributed measurements, channels, and so on. Such objects describe, for example, the resources shared in quantum networks. Not all such objects are useful, however. In the context of space-like separated parties, devices which can be simulated using local operations and shared randomness are useless, and it is of paramount importance to be able to practically distinguish useful from useless quantum resources. Accordingly, a body of literature has arisen to provide tools for witnessing and quantifying the nonclassicality of objects of each specific type. In the present work, we provide a framework which subsumes and generalizes all of these resources, as well as the tools for witnessing and quantifying their nonclassicality.

Space-like separated resources of various types are studied in quantum information. In the bipartite setting, at least ten types of objects have been considered as resources in computation or communication tasks: density matrices [1], shared randomness [2], nonlocal boxes [3], steering assemblages [4], teleportages [5,6], distributed POVMs (or 'semiquantum' channels) [7], device-independent steering channels [8], channel assemblages [9], Bob-with-input steering assemblages [10], and bipartite quantum channels [11]. Heterogenous objects appear in quantum networks [12]; for example, depending on the local operations available, various schemes of quantum key distribution have been proposed [13]. With the partial exception of Ref. [6], no unified framework has been given to describe and characterize [14] all these different multipartite space-like separated resource types.
Here, we work in the context of space-like separation, where local operations and shared randomness (LOSR operations) are free, but no-signaling forbids classical communication, and we provide a framework which unifies the study of nonclassicality of arbitrary types of resources. We introduce a common notation for all resource types, distinguished by the nature (trivial, classical, or quantum) of the input and output systems, and define a unified notion of nonclassicality which subsumes the natural notions of nonclassicality for every type of resource.
That is, we here (together with Ref. [15]) demonstrate that entangled states, nonlocal boxes, unsteerable assemblages, nonclassical teleportages, and indeed resources of all the types just listed can be viewed as instances of a single notion of resourcefulness within a unified resource theory [16]: that of nonclassicality of common cause processes. This phrase was first introduced in Ref. [17] in the context of a resource theory of nonlocal boxes, and it is also apt in the broader type-independent context considered here. This unified view based on LOSR operations . We also characterize their nonclassicality using a type-independent absolute robustness monotone M abs (table) that we introduce below. Any single monotone is only partially informative; e.g., M abs assigns the same value to {µ XZ a|x } and PTsi, even though the former is strictly more nonclassical than the latter. also resolves some long-standing confusions [18].
While [15] defines and studies this resource theory more abstractly, this paper proposes tools to quantify the nonclassicality of resources in a type-independent manner, and defines nonclassicality measures that transcend types. For example, we will here quantitatively compare resources of various different types that have previously been studied only separately in the literature. We also discuss how these measures can be computed or approximated using off-the-shelf software. We base our discussion on the resources presented in Fig. 1, whose features are elaborated on below. In other words, we show that one can rigorously compare the quantitative degree of nonclassicality inherent in distributed resources of arbitrary types.
A unified notation for all types of resources -First, we introduce a notation which is capable of describing a wide variety of resources that arise naturally in Bell scenarios. In our framework, a resource is a quantum device distributed over multiple space-like separated parties which receives inputs and produces outputs. Viewed broadly as a channel, this subsumes a wide variety of special cases in the literature, as we will show. For simplicity, we restrict ourselves to the two-party case and to finite-dimensional Hilbert spaces: we denote by X , Y the input systems and by A, B the output systems of the first (Alice) and second (Bob) parties respectively, as shown in Fig. 2. We also use H as an auxiliary system or placeholder.
To  restricts the operators in H(H) to a commutative subalgebra; without loss of generality, we take these operators to be diagonal in the computational basis |i H . Finally, a quantum system (T[H] = Q) has no such restriction. We sometimes omit the tensor product symbol: e.g., D(X Y) denotes D(X ⊗ Y), and we omit subscripts labeling systems when convenient and unambiguous.
A resource R is a map which is trace-preserving and completely positive [19,20] ( for any auxilliary space H . The subscript AB|X Y corresponds to the types and dimensions of all input and output systems. For a resource R as in (1), we define the resource type written and the resource dimension We consider only resources which are nonsignaling from every party to every other. No-signaling from Alice Lab 1: Alice Lab 2: Bob Resource (blackbox) Figure 2. A two-party resource R ∈ D(X Y) → D(AB) and its action on product input ξ ⊗ψ; by allowing X , Y, A, B to be trivial, classical, or quantum, we unify all the resource types shown in Table I. to Bob implies that if one ignores Alice's output A, then Alice's input X has no influence on Bob's output B. That is, the reduced channel for all inputs ξ, ξ ∈ D(X ) and ψ ∈ D(Y). Hence, one can pick an arbitrary ξ to construct the unique R B|Y such that for all ξ and ψ. No-signaling from Bob to Alice can be encoded similarly as Input/output types -Note that when an output A of a party is trivial, with T[A] = I (or equivalently d[A] = I), no-signaling guarantees that the party is irrelevant and can always be ignored. In contrast, when an input X of a party is trivial, with T[X ] = I, that party can nonetheless be nontrivial, as happens (e.g.) with quantum states. When an output A is classical, with T[A] = C, the channel satisfies (for all ξ and all ψ): When an input X is classical, with T[X ] = C, the channel acts on the diagonal subspace, and thus satisfies (for all ψ)  (7) and (when applicable) (8), (9).
For any given type and dimensionalities, this set is representable via a semidefinite program (SDP), using the Choi matrix [21,22] representation of resources; see Sec. C for an explicit proof.
We show ten distinct types of resources which our framework subsumes and which have been previously studied in the literature in Table I.  [3] CC → CC Channel assemblage [9] CQ → CQ Steering assemblage [4] CI → CQ Bob-with-input steering assemblage [10] CC → CQ Teleportage [6] (in teleportation exps. [5]) QI → CQ General bipartite channel [11] QQ → QQ Table I. Types of resources studied in the literature. The arrow indicates a quantum input/output space, while the arrow indicates a classical input/output space.
Examples of resources -We now define the examples from Fig. 1.
The singlet |Ψ − is a quantum state (type II → QQ), written as a channel acting on a trivial input, denoted 1: [15,24,25]. It can be constructed by two parties who share a singlet state |Ψ − ; Alice jointly measures system X together with her half of the singlet using a Bell measurement (BM) in the basis {(σ a ⊗ 1) |Ψ − } a=0,1,2,3 , where a labels her outcome, and Bob proceeds similarly on system Y together with his half of the singlet, with b = 0, 1, 2, 3 as his outcome. (Here, σ 0 = 1 and σ 1,2,3 are the Pauli matrices.) The action of the resulting distributed POVM with quantum inputs X and Y on input quantum states ξ and ψ can be written The resources {µ XZY a|x } and {µ XZ a|x } are steering assemblages (type CI → CQ). The XZY-singlet assemblage µ XZY a|x can be constructed by two parties sharing a singlet, and one of them performing the measurement depending on whether the classical input x is 0, 1, or 2, respectively, and where |± = 1 √ 2 (|0 ± |1 ) and |±i = 1 √ 2 (|0 ± i |1 ). One can write the resulting assemblage in terms of its action on the three possible classical inputs as The XZ-singlet assemblage {µ XZ a|x } is defined similarly, but where the classical inputs are x = 0, 1, corresponding to the first two POVMs above, respectively.
A unified resource theory -Next, we introduce a single resource theory [16] which captures the relevant notion of nonclassicality for all resources of all of the types described above. Within this resource theory (which is expanded upon in the companion article [15]), free resources are the ones that are obtained using only local operations and shared randomness (LOSR operations [17,18]): admits of a convex decomposition into single party resources R i A|X and R i B|Y according to probability distribution p i : We denote the set of all free resources as R free := ABX Y R free AB|X Y , and the set of all no-signaling resources (free or nonfree) as R := ABX Y R AB|X Y ; note that the union runs over all types and dimensions.
For some types, we have R free AB|X Y = R AB|X Y . Definition 3. A resource type is T-trivial if every resource of that type is necessarily free. , it follows that R is LOSR-free.
We now turn our attention towards transformations of resources: a generic transformation τ on resources is a completely positive, linear supermap [27] τ : that transforms a resource R AB|X Y into a resource R A B |X Y , possibly changing its type and dimensions. A transformation is LOSR-free if it is obtainable by local operations and shared randomness, and hence admits of a convex decomposition into products of arbitrary supermaps [27] acting only on a single party. A generic (bipartite) free transformation is shown in Fig. 3(a) of Ref. [15]. The set of free transformations is closed under composition, and maps free resources to free resources.
The resourcefulness of resources is completely characterized by the conversions that are possible between them using free operations. For example, the relative nonclassicality of the resources in Fig. 1 are fully characterized by the conversion relations claimed therein, whose validity we now prove. When we defined the examples above, we described how the singlet |Ψ − can be transformed into the resources {Π ab }, {µ XZY a|x }, {µ XZ a|x }, and P Tsi using local (and hence LOSR-free) transformations. Furthermore, {Π ab } can be freely transformed into the singlet |Ψ − , as proved in [15], so the two are equally resourceful (and hence can be freely transformed into exactly the same resources). The assemblage {µ XZY a|x } can be freely transformed into assemblage {µ XZ a|x } simply by Alice ignoring the third input value, and then also into P Tsi (ab|xy) by Bob further performing the measurements given above Eq. (13) on his quantum output. Finally, {µ XZ a|x } can be transformed into P Tsi (ab|xy) by Bob performing these same measurements.
It remains to show that every arrow absent from the figure corresponds to a conversion that is impossible under LOSR-free transformations. The following proposition implies the nonconvertibility of P  without loss of generality, the side channels can be taken to be classical. One can imagine the transformation in (a) as a two-step procedure: the initial resource (b) of type CC → CC is transformed to a resource (c) of type II → CC, and then to a resource (d) of type II → QQ. In (b)-(d), the shading indicates the portion of the figure whose type is labeled.
Proof. Consider first a generic LOSR transformation taking boxes (CC → CC) to states (II → QQ); the most general such transformation is depicted by the dashed operations in Fig. 3a), since for any party with only a classical input and output, the side channels on their local supermaps may be taken to be classical systems without loss of generality. As shown in Fig. 3b)- Fig. 3d), any such LOSR transformation can be seen as a composition of two LOSR transformations, where the first takes type CC → CC to type II → CC, and the second takes type II → CC to type II → QQ. Now, Prop. 1 guarantees that the result of the first transformation is free, since its type is T-trivial. Since LOSR operations preserve the free set, the final resource resulting after the second transformation is also free. The other two cases listed in the proposition have analogous proofs, but where the T-trivial intermediate types are CI → CC and II → CQ, respectively.
To establish the nonconvertibility of {µ XZ a|x } to {µ XZY a|x }, it suffices to exhibit a monotone whose value would increase under the conversion. Such a monotone is the type-independent absolute robustness, which we introduce below and depict in Fig. 1.
Type-independent monotones -One can quantitatively measure the nonclassicality of a resource using any function that does not increase under LOSR transformations, which is a monotone of our resource theory. We focus on the type-independent absolute robustness here, but consider others in Sec. A. Definition 4. The type-independent absolute robustness M abs (R) of a resource R ∈ R of arbitrary type and dimension is: Our innovation here is to consider functions which behave monotonically even under operations that change the resource type, which allows us to compare the nonclassicality of resources across different types, as in Figure 1. We prove in Sec. A that the absolute robustness (as defined here) has this property-despite the fact that the special cases of it which have been previously studied [17,[28][29][30][31][32] have been type specific, and despite the fact that the computation of M abs (R) involves a specification of the type and dimension of R.
The values of this monotone on the examples in Fig. 1 are exact, and the manner by which they are computed is described in Sec. F. (We also compute these values for a family of parameterized versions of four of these resources.) Note that monotones can be used to prove that some conversions under LOSR are impossible, namely, those which would increase the value of M abs . One cannot conclude anything about which conversions are possible. This can be seen in Fig. 1, where M abs assigns the same value to the Tsirelson box and to the assemblage {µ XZ a|x }, despite the fact that the two are not equivalent, as the former cannot be freely converted to the latter by Prop. 2.
A hierarchy to characterize nonclassicality -We now describe how one can in practice determine whether or not a given resource R is LOSR-free. This can be done using a hierarchy of SDPs which ultimately checks if R is a member of R free . The reasoning is as follows.
If R AB|X Y ∈ R free , then R has a convex decomposition as in (14). By copying the shared randomness to more parties (who can then locally emulate any other party) it follows that R has an n-symmetric extension [33,34] for any n, obtained by copying the second party n times in the product. That is, for any n there exists such that 1. R (n) is no-signaling from any party to any other, 2. R (n) is symmetric under all n! permutations of the copies, and 3. the reduced resource tr B2...B k R (n) = R .
Whether or not an n-symmetric extension R (n) exists can be tested by an SDP. Hence: Proposition 3. The set of classical resources R free AB|X Y of any given type and dimensionalities has a sequence of outer approximations AB|X Y is defined by the set of resources that admit of an n-symmetric extension, and each such set is SDP-representable (see Def. 1). Leveraging the Choi matrix representation of resources, convergence follows immediately from Ref. [34,Theorem 3.4], since the constraints of Eqs. (2)- (7) and (when applicable) (8), (9) have the form required by the theorem; see Sec. D for explicit details.
Application: witnessing nonclassicality -Because this sequence of approximations converges on R free AB|X Y , for any nonclassical resource R / ∈ R free AB|X Y of arbitrary type and dimension, there exists some level n of the hierarchy such that R / ∈ F (n) AB|X Y , which witnesses the fact that R is not free. We stress again that our technique applies to all types of resources, since all that distinguishes different types is the inclusion (or not) of constraints of the form in (8)- (9) in the relevant SDPs.
Application: computation of monotones -This hierarchy enables the practical computation of monotones. For example, consider again the absolute robustness M abs . By replacing R free AB|X Y with the outer approximation F (n) AB|X Y in the definition of M abs , one relaxes the constraints in the minimization, thus obtaining a lower bound on M abs (R). This gives a sequence of approxima-tionsM each of which is explicitly computable using a SDP (see Sec. E), such that lim n→∞M (n) abs (R) = M abs (R). Application: LOSR convertibility of states-Since convertibility relations fundamentally determine the resourcefulness of resources, it is of central importance to be able to determine when one resource can be freely converted to another. By definition, free transformations that convert states (type II → QQ) into states are themselves free resources of type QQ → QQ. Given states ρ ∈ D(AB) and ρ ∈ D(A B ), one can test for the existence of an LOSR-free transformation (viewed as a resource R) such that ρ = R[ρ]. Since this is a linear constraint, one can modify the hierarchy of Proposition 3 to include it, generating a new hierarchy which tests for the possibility of LOSR convertibility between ρ and ρ . A natural extension of this hierarchy to allow generic local supermaps [27] would allow one to test for the possibility of LOSR conversions between arbitrary types of resources, but we leave this for future work.
Outlook -We have given a type independent description of nonclassical resources when local operations and shared randomness are free, generalizing a series of existing results, including those in Ref. [1,[3][4][5][6][7][8][9][10]35]. This work opens many new research avenues. First, although generalizing our definitions and arguments to n-party scenarios is straightforward, multipartite nonclassicality in general scenarios is likely to have a rich structure, as happens for multipartite LOCC-entanglement [36][37][38]. Still more interesting would be to expand our framework to encompass supermaps; for example, this would allow for a description of filtering [39], and for the construction of a hierarchy of SDPs that can witness the possibility or impossibility of any LOSR conversion between any two resources of any type. Much work remains to be done in defining monotones which are computable and which have operational significance across multiple resource types. These questions can also be asked for the resource theory of postquantumness, wherein the free operations are local operations and shared randomness [40]. For all these, the methods of Ref. [41], which presents a unified framework to study monotones in resource theories, are likely to be useful. Finally, we hope that our framework will be used to unify the expanding set of scenarios under study, and to generalize the tools developed to characterize them.

APPENDICES
We order the next sections by increasing complexity, and do not follow necessarily the order of appearance of notions in the main text.
In Section A, we prove that the type-independent absolute robustness M abs (Definition 4 of the main text) is a monotone of our type-independent resource theory of local operations and shared randomness. We also ex-plore other monotones (generalized robustness, nonlocal weight), and link their type-independent variants to their type-specific appearances in the literature. We also show that random robustness cannot naturally be generalized to be type-independent. In Section B we review basic notions of convex optimization, and define LP-and SDP-representable sets, as these are used several times in the present work. Then, in Section C, we show that the set of nonsignaling resources of any given type and dimensionalities is SDP-representable (sometimes even LPrepresentable). On the other hand, the representability of the set of free resources is more complex: we show in Section D that some types can be represented exactly using LPs or SDPs, while other types are represented by a convergent hierarchy of SDPs. In Section E, we show how to compute or approximate monotones using these LP-and SDP representations, and we describe in Section F how we computed the absolute robustness of the examples presented in the main text, while extending the examples to partially entangled states.

Appendix A: Monotones
When comparing resources of a fixed type, it suffices to use the traditional notion of a monotone as a function (from resources of a fixed type to the real numbers) which does not increase under type-preserving free operations. For example, the negativity [67] is a type-dependent LOCC (and thus LOSR) monotone that applies to quantum states (T[R] = 11 → QQ); the relative entropy of nonlocality [32,46] applies to nonlocal boxes (T[R] = CC → CC) and so on. Note that some of these monotones impose also that the dimension of the resource stays con- , as in the example of the random robustness measure, discussed below.
However, the main message of this article is that one can and should compare the resourcefulness of resources across arbitrary types and dimensions. Hence, one should consider dimension-and type-independent monotones, defined formally as follows. for any free LOSR transformation τ , including those which change the type and dimension of an input resource.
We defined and focused on one such monotone, the type-independent absolute robustness, in the main text. We now define several more type-independent monotones, as natural generalizations of type-dependent monotones that have been previously studied [17, 28-32, 47, 58, 63].

Type-independent absolute robustness monotone
We have already defined the type-independent absolute robustness M abs in the main text in Definition 4, as We now prove that this is indeed a type-independent monotone.
Proof. For a given resource R AB|X Y , the value M abs (R) is the value s of a feasible solution (s, S) satisfying for some S ∈ R free AB|X Y . Since any free LOSR transformation τ : R AB|X Y → R A B |X Y (which may change the resource type and dimension) takes the free set R free AB|X Y into the free set R free A B |X Y , it follows by linearity that and also that τ This is the natural type-independent generalization of the absolute robustness monotone defined on quantum states in Ref. [28], defined on boxes in Ref. [29], and defined on steering assemblages in Refs. [30,31]. (It was termed the LHS steering robustness in [30] and the LHS robustness in [31].) A closely related type-independent monotone is obtained by using a different function to quantify the noise being mixed with the given resource: The value of this monotone is related by the variable transformation M abs (R) = M abs (R)/(1 + M abs (R)).
This variant is the natural type-independent generalization of the monotone M abs defined on boxes in Refs. [17,32]. (It was termed the robustness of nonlocality in Ref. [32] and termed M RBST,L in Ref. [17].)

Type-independent generalized robustness monotone
Another related type-independent monotone is obtained by considering mixing a different set of resources, namely, by replacing S ∈ R free with S ∈ R. Then, in analogy with the generalized robustness introduced for quantum states in [63], we define: The proof that this is a type-independent monotone is analogous to the proof for the absolute robustness. The definition above subsumes the definition for quantum states [63], boxes [29], and steering assemblages [30,47,58]. (Note that the same quantity was called the steering robustness in Refs. [30,58] and the robustness of steering in Ref. [47].) Because the set R AB|X Y is SDP-representable in general (unlike the set R free AB|X Y ), computing this monotone can be more efficient than computing the absolute robustness.
Noting that the enveloping set R AB|X Y of resources includes post-quantum resources, one might be motivated to impose a further constraint on the enveloping set, choosing it instead to be the set R AB|X Y of quantumly realizable LOSR resources (sometimes termed localizable resources [43,45]), as was done in [29]; doing so then defines a distinct monotone. However, the characterization of the set of quantumly realizable LOSR resources is an open problem (and for the case of boxes, the set is even not closed [62]). We leave as an open question the impact of the choice of a type-independent enveloping theory on the operational significance of the generalized robustness [65].

Type-independent nonlocal weight monotone
Another related type-independent monotone is given by the minimum weight on a nonfree resource with which one can mix a free resource to generate the given resource: The proof that it is a type-independent monotone is again analogous to the proof for the absolute robustness. This is the natural type-independent generalization of the nonlocal weight monotone [60] defined on boxes, and also of the steering weight [30] or steerable weight [47,61] monotone, defined on steering assemblages. It is also linked [29] to the best separable approximation of quantum states [52].

Type-and dimension-dependent random robustness measure
We close by noting that the random robustness monotone defined in Ref. [28] for quantum states cannot be easily generalized to a type-independent monotone. The random robustness is defined to parallel the absolute robustness, but where the set of resources being mixed with the given resource is taken to be a singleton set containing only the "maximally mixed" resource of the same type as the given resource. However, the resulting measure is not a type-independent LOSR monotone; indeed, it is not even a type-dependent monotone under LOSR operations (nor under LO operations or LOCC operations, for that matter). As shown in Ref. [28], the random robustness can increase under local operations that change the dimensionality of one's resources. Ultimately, this is a consequence of the dimension-dependence of the maximally mixed resource; e.g., for two-qubit states the random robustness is based on the maximally mixed state 1 4 /4, while for two-qutrit states it is based on 1 9 /9. However, if one restricts attention only to resources of a fixed type and a fixed dimension, then one can show that the random robustness behaves monotonically. It is conceivable that the random robustness satisfies some new notion of type-independence which incorporates dimensional constraints, but it is unclear whether such a new notion is of any significance, and we do not pursue it here.

Appendix B: Convex optimization and LP-and SDP-representability
We now present some practical tools which are useful for characterizing various important sets of resources, leveraging the fact that efficient numerical solvers such as MOSEK [42] are available to represent and optimize over convex sets that are defined using linear inequalities (such solvers are termed linear programs, or LPs) and linear matrix inequalities (such solvers are termed semidefinite programs, or SDPs) [49].
Both LPs and SDPs optimize a linear objective over a convex set: linear programs optimize over LPrepresentable sets, while semidefinite programs optimize over SDP-representable sets.
where c ∈ R p , P ∈ R p×n and Q ∈ R p×m , and γ 0 is interpreted componentwise.
Thus, LP-representable sets are defined by linear inequality constraints, linear equality constraints (which can be written as pairs of inequalities), and projections of such sets (by moving the corresponding coordinates to the slack variables y); we refer the reader to [44] for a complete reference on such manipulations.
are symmetric matrices of size p × p, and, for a symmetric matrix M ∈ R p×p , the constraint Γ 0 is interpreted as Γ being semidefinite positive.
Thus, SDP-representable sets are defined by equality constraints of various types, semidefinite positiveness constraints, projections, and all the operations that define LP-representable sets (the inequality constraint γ 0 is rewritten as the SDP constraint of a diagonal matrix).
A variety of sets are LP-or SDP-representable. For example, although the set X in the definition above contains real vectors, sets of Hermitian matrices can be represented as well, by expanding on a basis with real coefficients. Again, we refer the reader to [44] for more details.
Definition 9. A linear program (resp. semidefinite program) corresponds to the problem where X is LP-representable (resp. SDP-representable).
It is also useful to consider conic extensions of convex sets.
Definition 10. Let X be a convex set. The conic exten-sionX ⊇ X iŝ We easily verify that if X is LP-representable, then its conic extensionX is also LP-representable: it is sufficient to add an additional variable t ∈ R with the constraint t ≥ 0 to Definition (7), and replace c + P x + Q y 0 by ct + P x + Q y 0. By a similar argument, one can verify that if X is SDP-representable, thenX is also SDPrepresentable.
Appendix C: The set R AB|X Y of all nonsignaling resources of given types and dimensionalities is SDP-representable Next, we introduce the useful Choi description of resources, and then show that the set of all nonsignaling resources of any given type and dimensionalities can be represented exactly by an SDP or LP.

Choi state representation of resources
In the main text, we described resources as completely positive, trace preserving linear maps. Here, we introduce a second (equivalent) description of a resource R ∈ D(X Y) → D(AB) in terms of its Choi [21,22] matrix J R ∈ D (ABX Y ). The Hilbert spaces X and Y are isomorphic to X and Y respectively. The distinction between X and X is introduced for clarity in this section, and will be dropped later on. Using the computational basis of those spaces, we construct the maximally entangled states φ X X and φ YY : Definition 11. The Choi state J R ∈ D (ABX Y ) corresponding to the resource R is defined as: (C3) One can write this out explicitly as

Constraints on the Choi state of a resource with special properties
The constraint that a channel be completely positive is equivalent to the constraint on the Choi state that while the constraint that a channel be trace-preserving is equivalent to the constraint on the Choi state that As discussed in the main text, we consider only nosignaling resources, as befits our assumption of space-like separation. This translates into the following constraints on the Choi state: Note that condition (C7) implies condition (C6) above. These nonsignaling constraints can be written explicitly as follows. For all j B , j X , j Y , k B , k Y : and for all j A , j X , j Y , k A , k X : Resources which have certain inputs or outputs that are classical satisfy further constraints, as we now show. Trivial input or output Hilbert spaces correspond to onedimensional Hilbert spaces in the tensor product in which the Choi state J R is defined, and thus such systems do not appear explicitly in the description of J R as a Hermitian matrix, and so imply no constraints beyond fixing the dimensionality.

Constraints from classicality of outputs and inputs
As discussed in the main text, the statement that an output A is classical, denoted T[A] = C, expresses the fact that the given resource always produces outputs on A that are diagonal in a fixed basis, as in Eq. (8). The Choi state of such a resource satisfies The constraints for the systems of other parties are analogous.
The statement that an input X is classical, denoted T[X ] = C, expresses the fact that the given resource is defined only for input states that are diagonal in a fixed basis, as in Eq. (8). The Choi state of such a resource satisfies i X |J|j X = 0 for i X = j X . Explicitly, for all i A , i B , i X , i Y , j A , j B , j X and j Y we have: (C11) Hence we have the following.
Definition 12. The set J AB|X Y of Choi states corresponding to nonsignaling resources R AB|X Y of a given type and dimensionalities is equal to the set of Hermitian matrices that are • completely positive (C5), • trace preserving (C6), • nonsignaling (C7), • classical in the relevant Hilbert spaces: (C10) and (C11).

This proposition follows.
Proposition 4. The set R AB|X Y of nonsignaling resources of any given type and dimensionalities is SDPrepresentable, as is the set J AB|X Y of corresponding Choi states. In the case where no input or output has quantum type, these sets are furthermore LP-representable.
Proof. All the constraints in Definition 12 are of the form that define SDP-representable sets. Thus, the set J AB|X Y (for any given types and dimensionalities) is SDP-representable, as is the corresponding set R AB|X Y . When no inputs or outputs have quantum type, the Choi matrix is fully diagonal, and hence the semidefinite constraint (C5) reduces to a linear inequality constraint, which means that all the constraints are LPrepresentable.
Appendix D: Representability of the set of LOSR-free resources of any type In Section C we discussed the characterization of the set R AB|X Y of nonsignaling resources, by characterizing the set J AB|X Y of Choi states of nonsignaling resources. We now turn our attention to the harder but more important task of characterizing the set of LOSR-free resources R free AB|X Y , by characterizing the set J free AB|X Y of the corresponding Choi states.
We first describe particular types for which the set of free resources can be described exactly using an LP or SDP. We then describe in detail how, for any given type and dimensionalities, this set can be represented by an SDP hierarchy.

Exactly LP-or SDP-representable resource types
It is widely known that nonlocal boxes of type CC → CC have an exact representation using linear programs [2,48,59]. It is also known that steering assemblages of the form CI → CQ can be represented using semidefinite programs [4]. We generalize these results. To simplify the discussion, we will in this section refer to a party with input X and output A as a classical party A|X whenever (T[A], T[X ]) ∈ (C, C), (I, C), (C, I), (I, I) .
We first give some special types for which the set of LOSR-free resources of that type admit of an exact LP or an exact SDP representation.
For single party resources, the situation is simple.
Proposition 5. The set J free A|X of free single-party resources of any type is always SDP-representable. Moreover, J free A|X is LP-representable when the party A|X is classical, that is, whenever neither the input nor the output of the party contains any quantum component.
Proof. This follows directly from the fact that J free A|X = J A|X ; that is, the set of free single-party resources coincides with the set of all no-signaling single-party re-sources, which by Proposition 4 is SDP-representable. The LP-representable case follows from that proposition as well.
One can then show the following; note that here, with respect to the notation introduced above, we dropped the prime superscripts on the input spaces. Proposition 6. Consider the (N +1)-party resource with systems A, B 1 , . . . , B N , X , Y 1 , . . . , Y N , and define B = B 1 ⊗ . . . ⊗ B N , and similarly for Y. Let the party A|X be classical and the other systems be of arbitrary type and dimension, with J free B|Y SDP-representable. Then J free AB|X Y is also SDP-representable.
Proof. Any free J ABX Y can be written as When party A|X is classical, the set J A|X = J free A|X has a finite number of extremal points, one for each deterministic strategy. Denoting the finite set of associated Choi states, indexed by λ, as {J λ AX } λ , one can rewrite Eq. (D1) (without loss of generality) as for some probability distribution q λ and where (for all λ) Ĵ λ BY λ ⊂Ĵ free B|Y . By further definingĴ λ BY := q λ J λ B|Y , one can simplify this to Now, if J free B|Y is SDP-representable, then so too is the set of objects of the form J ABX Y , since such objects are simply linear combinations of objects drawn from an SDPrepresentable set. (In particular, for each classical value that system X and A can take, Eq. (D3) constitutes a linear combination of objectsĴ λ BY which are each drawn from an SDP-representable set.) A similar proposition holds for LP-representability, with an analogous proof.
Proposition 7. Let party A|X be classical, and J free B|Y be LP-representable. Then J free AB|X Y is also LPrepresentable.
One final special case worth noting is the type 11 → QQ, which is SDP-representable when d[A]d[B] 6, by virtue of the PPT criterion [50].
A few applications of these propositions are given in Table II.  Table II. Types with exact LP or SDP representability of their free sets.

A hierarchy of SDPs for the characterization of free resources of arbitrary types
The set of LOSR-free resources of more general types do not admit of exact LP or exact SDP representations, and so one must resort to a hierarchy of approximations, which we will now give, after introducing some useful preliminaries.

Symmetric extensions
Let J ∈ D(AX BY) be a Choi state satisfying Definition 12. Here, we have reordered Hilbert spaces on J and other Choi states to fit the content of this section. We write B n 1 = B 1 ⊗ · · · ⊗ B n for the tensor product of n copies of spaces isomorphic to B, and similarly for Y n 1 , and we write B n 1 ⊗ Y n 1 = (BY) n 1 . This is to be contrasted with B defined in Proposition 6, where the tensor factors were not necessarily isomorphic. Below, we will consider operators of the form J AX (BY) n 1 ∈ D(AX B n 1 Y n 1 ). We write the symmetric group of degree n as S n , which we identify with the set of bijections We say that an operator J AX (BY) n 1 is symmetric if We are now ready to define the set of Choi states with symmetric extensions, where each such Choi state is in one-to-one correspondence with a resource that has a symmetric extension (as defined in the main text).
Definition 13. The Choi state J ∈ D(AX BY) has an n-symmetric extension if there exists a state J ∈ D(AX B n 1 Y n 1 ) which obeys the following conditions: 1. The state J corresponds to a nonsignaling resource as in Definition 12.
2. The reduced state 3. The state J is invariant under any joint permutation (in the sense of Eq. (D4)) of the n parties of B n 1 and Y n 1 .
We denote the set of Choi states having an n-symmetric extension as J Note that if one considers a Choi state of a resource with systems of a special type (trivial or classical), then the copied systems in the extended Choi state will (by symmetry) also be of that special type. Hence, any constraints from the cases when B or Y are classical will automatically imply that the copies of these systems satisfy the same constraints. The set J

(n)
AB|X Y is SDP-representable, as it is defined as the set of nonsignaling Choi states which satisfy additional linear constraints.

Constructing the hierarchy of SDPs
As stated in the main text, any LOSR-free resource has an n-symmetric extension for all n, since it has a decomposition according to Eq. (14) of the main text, which can be extended to an arbitrary number of copies of B|Y as in (16) of the main text. Hence, the Choi state J AX BY corresponding to such a resource has an nsymmetric extension for all n as well.
It is not difficult to see that the set of Choi states with n-symmetric extensions includes the set of states with (n − 1)-symmetric extensions. Thus, we have, mirroring (17) of the main text: Because each set in the hierarchy is SDP-representable, this constitutes a series of tests which is guaranteed to (at some finite level) witness the fact that any given nonfree resource (of any type) is indeed nonfree.

Convergence of the SDP hierarchy
To prove that this sequence converges on the set J free AB|X Y , we use Theorem 3.4 of Ref. [34]. For convenience, we rewrite the elements of Definition 13 in the notation of [34], before using their theorem to prove convergence.
The no-signaling condition can be given more explicitly as a pair of constraints: no-signaling from X to any other party (as in Eq. (6) of the main text) and no-signaling from Y n to any other party. By the invariance under joint permutation of parties, this last condition guarantees that for any n-symmetric extension, none of the n input systems of B n 1 can signal to any output of any other party.
To write these in the notation of Ref. [34], we first denote the trace operation as a linear operator, as follows. For generic operators Ω AX ∈ H(AX ) and Ω BnYn ∈ H(B n Y n ), we define and Then the constraint of no-signaling from A to X is then expressed as where . The constraint of no-signaling from Y n to B n is then expressed as where Finally, we reexpress the linear constraints from classicality in the notation of Ref. [34]. For a generic operator on an output space, e.g. A, we define the classicality operator by for Ω A ∈ H(A). For a generic operator on an input space, e.g. X , we define the classicality operator by for Ω X ∈ H(X ). Classicality of A and X (respectively) are then expressed as while classicality of B n and Y n (respectively) are expressed as Because J AX (BY) n 1 is symmetric under exchange of parties, these latter two constraints imply that all copies of B and Y satisfy the analogous classicality constraints.

Convergence of the hierarchy
Finally, we can leverage Theorem 3.4 of Ref. [34] to prove that if there exists a symmetric extension of a Choi state for all n, then that Choi state corresponds to a free resource. In other words, the hierarchy just given converges on the set of Choi states associated to free resources. It is worth noting that Theorem 3.4 of Ref. [34] follows from an application of the de Finetti theorem for quantum channels, which roughly states that any element of an exchangeable sequence of quantum channels can be written as a mixture of many copies of a single unknown channel.) Proposition 8. If a given Choi state J AX BY ∈ D(AX BY) admits an n-symmetric extension, then there exists a free resource with Choi state J free AX BY ∈ D(AX BY) such that  (8) and (9) (from the main text) due to the specific types of the input and output systems, then it follows that J free AX BY satisfies the same constraints (and hence is of the appropriate type).
Proof. Suppose one has a resource of a specified type whose Choi state J AX BY admits of an n-symmetric extension. Then Theorem 3.4 of [34] states that there exists a probability distribution {p i } and operators σ i AX and ω i BY such that the operator satisfies the bound of Eq. (D17). It furthermore guarantees that the operators σ i AX and ω i BY satisfy so σ i AX and ω i BY are Choi states of single party channels, and hence J free AX BY is the Choi state of some free resource. The only sense in which the specified type of one's resource impacts this argument is that additional classicality constraints of the form in Eqs. (D13) or (D15) must be included for each classical input or output system. These constraints can be embedded in the maps Γ and Λ of Ref. [34]. The free resource whose existence is guaranteed by the theorem will necessarily satisfy these same constraints, and hence be of the appropriate type.
If for a given J AX BY there exists an n-symmetric extension for all n, then the resource it represents is LOSRfree, since the distance to the free set goes to zero in Eq. (D17) as n → ∞.
The hierarchy above can be tightened by introducing PPT cuts [33,55]. The additional discriminating power granted by such cuts remains to be explored.

Special cases where the hierarchy converges after finitely many steps
In certain cases, the hierarchy converges after a finite number of steps. Here, we generalize an observation made by Terhal et al. in Ref. [66]. Proof. As we have already argued, any free resource has an n-symmetric extension for all n, and hence has one for n = d [Y]. We now prove the converse. Let R be a resource of the type considered in the proposition, as shown in Fig. 4a. Assume now that R has an n-symmetric extension with n = d[Y], as shown in Fig. 4b, with inputs y 1 to y n and outputs β 1 to β n . Next, imagine that Alice and Bob share such a resource, where Alice has possession of X and A, while Bob has possession of all the other input and output systems; that is, Bob's (classical) input is y = (y 1 , . . . , y n ), and his (classical) output is β = (β 1 , . . . , β n ). In Fig. 4c, we consider a local (and hence free) transformation that Bob can implement, wherein he inputs the classical values y 1 = 1, . . . y n = n, obtaining as his outcome a tuple of values for β. The resulting resource R has type T[X ]1 → T[A]C, which is a useless type according to Prop. 1. However, R can be converted back to R using an LOSR-free transformation, as shown in Fig. 4; namely, Bob just selects the value of the yth output (β y ), for whatever input y he is given. Since this free transformation preserves the set of LOSRfree resources and yet generates R from a free resource, R itself must be free.  Note that these are cases for which an exact representation exists, as described in Section D 1.
solute robustness of the singlet can be directly computed from its Schmidt coefficients using the formulas therein: where, implicitly, M abs (·) applies on the density matrix derived from the pure state with the given Schmid decomposition. We also verified this value using the PPT criterion (Section D). The absolute robustness of the distributed measurement is equal to that of the singlet, as we previously proved that these resources are interconvertible under LOSR operations. The values of the absolute robustness for the two steering assemblage examples were computed using the exact SDP representation in Section D.
The values of the absolute robustness for the Tsirelson box were computed using the exact LP representation given in Section D.

A graphical understanding of absolute robustness
We also verified this value by the following graphical argument, which corresponds to Fig. 5.
In the CHSH scenario with binary inputs and outputs, we define the isotropic line as the one-dimensional affine subspace that contains the Tsirelson box and the uniformly random distribution. By extension this isotropic line also contains the PR-box. This isotropic line corresponds to the bold line of the figure, at the normalization coordinate (abcissa) = 1.0. The part of the isotropic line on the CHSH value (ordinate) interval [−2 √ 2, 2 √ 2] can be realized with quantum resources, and thus represents the quantum set. The part of the isotropic with CHSH value interval [−2, 2] corresponds to the free set. Any probability distribution can be projected on the isotropic line by symmetrization under the symmetries of the CHSH inequality (I = abxy (−1) a+b+xy P (ab|xy)),  and that projection does not affect the CHSH expectation value. Thus, the search for the optimal noise to mix can be restricted to the conic extension of that subspace. Using the definition (E2) of the absolute robustness, we draw the conic extensions of both the quantum realizable set and the free set; and we dot the area of the latter where it corresponds to subnormalized resources. The Tsirelson box J Tsi can be brought into the conic extension of the free set by adding to it a subnormalized free resourceĴ S , and we can find an optimal solution of the minimization (E2) in this dotted area. We show the optimal solution graphically asĴ S , and denote its trace by x. Using the intercept theorem [57], we obtain M abs (J Tsi ) = x = ( √ 2 − 1)/2 ≈ 0.207.

Extension to partially entangled states
We now consider parameterized variants of several of the resources studied in the main text.
We now define a family of resources of each of these types and dimensionalities, defined by the maximum achievable M abs that can be achieved starting from the state in Eq. (F2), as one ranges over α ∈ [0, π/4]. To compute this family of resources explicitly, we computed the projective measurement(s) which generate a resource of each of these specified types and dimensionalities. The absolute robustness of each of these families of resources (computed using the same methods as for the specific resources in the main text) is also plotted in Figure 6. One can see that the behavior of M abs mirrors that of the specific resources in the main text, in that for all α, the state resource takes the highest value, followed by the fine-grained assemblage, while the coarse-grained assemblage and the box take the lowest values (which are equal).
Interestingly, the optimal projective measurements can be chosen so that the sequence of conversions are possible between those optimal objects, analogous to conversion relations holding among the specific resources in the main text. Namely, for any α ∈ [0, π/4], the measurements to obtain the optimal µ 3 α can be chosen to be in the X basis (|± ), the Y basis (|±i ) and the Z basis (|0 , |1 ). The measurements to obtain the optimal µ 2 α can simply be those in the X and the Z basis. These are the same measurements defining the specific assemblages in the main text. To transform µ 2 α into the optimal box P α , however, the measurements are slightly adapted, corresponding to the POVM elements where θ 1 = π − θ 0 . We obtain θ 0 = π/4 for α = π/4, with θ 0 monotonically decreasing towards 0 as α → 0.


extfieldsofstudy:
Computer Science
Physics

text:
Social Sentiment Analysis Using Classifiers and Ensemble Learning

Instant message applications has become the trend of present social network for connecting people nowadays. With such massive information transmitted between end users, it may provide valuable hidden knowledge for data analysing and help us to obtain some insights of how the messages can influence current social trends. During the analyses, the author uses several different classifiers to conduct sentiment collection and use Ensemble Learning to aggregate the results. As a result, the author maps data about users’ sentiment graph in database of given category.

Introduction
Classification is significant in the real world and is widely used in text classification, image classification. In recent years, many classification methods have been developed, such as the Naïve Bayes, Logistic Regression, Decision Tree and Support Vector Machine. WhatsApp generates a huge amount of data. First, the author use LDA model to analyzes the content and divided people into different groups. Then, the authors analyze sentiment of people in groups. People can express their own emotions when talking with each other. The author tries to seek out whether users express positive or negative feelings. By using five kinds classifiers to do the analysis and using voting classifier to aggregate the results from these five classifiers the author gets the final results. These five classifiers are Naive Bayes classifier, Linear SVC classifier, Logistic Regression classifier, MNB classifier and Bernoulli NB classifier. These classifiers use different methods to do the analysis. Then the author uses Ensemble method which aims to compose a meta-classifier with different classifiers. Compared with single classifier, the metaclassifier is more efficient and has better generalization performance. By using the voting classifier, the results predicted by most classifiers are used as the final class label. Then the author analyzes the sentiment for people in different groups and get their emotions changes. A few people in some groups may be extremely active. However, a number of people in some groups may be not such active. Therefore, the author draws a popularity graph to show the five most popular groups in different time.

Five classifiers used in sentiment analysis
In this paper, the author analyzes the sentiment of people in these public groups mainly using Ensemble method. The author uses five classifiers that are Naive Bayes classifier, Linear SVC classifier, Logistic Regression classifier, MNB classifier and Bernoulli NB classifier. Voting classifier is a kind of classifier to aggregate the results from classifiers and get the final results. In these classifiers, Gaussian NB classifier, Multinomial NB classifier, Bernoulli NB classifier are all belong to Naive Bayes Classifier.  [1] The author will introduce these classifiers later.

Naive Bayes
Bayesian rule developed by the English mathematician Thomas Bayes to describe the relationship between two conditional probabilities In machine learning, the two most widely used classification model are Decision Tree Model and Native Bayesian Model. Naive Bayes Classifier has a solid mathematical foundation and stable classification efficiency. The Naive Bayes Classifier is relatively simple since it is based on a simple assumption that attributes are conditionally independent of each other when the target value is given. For the given items to be classified, the probability of each category appearing under the condition of this item appearing and which one is the largest is considered as which category the item to be classified belongs to. There are three kinds of classifiers in Naive Bayes Classifiers which are Gaussian NB classifier, Multinomial NB classifier, Bernoulli NB classifier. [2]

Gaussian NB classifier
When dealing with continuous data, a typical assumption is that the continuous values associated with each classify are distributed according to Gauss distribution. Therefore, the author can convert some continuous variables into discrete values. Assuming that the training set contains continuous value x , we classify the data according to categories and calculate the mean and deviation of each classification.

Multinomial NB classifier
For a multinomial distribution event model, the sample represents the frequency of a specific event, which is generated by multinomial distribution This is a typical event model for document classification, where events represent the occurrence of a word in a single document, and the value represents the number of some word appearance. If the given class and feature do not appear together in the training set, the probability estimation based on frequency is 0. When they multiply with each other, all information in other probability will be eliminated. Therefore, researchers usually set a small sample correction called pseudo count in all probability estimates to prevent estimated probability to be set to 0. This kind of method is called Laplace smoothing. When the pseudo count is set to 1, the Lidstone Smoothing is used in usual.

Bernoulli NB classifier
In the multivariate Bernoulli event model, the feature is two variables which describe the input. It uses global features and each eigenvalue is Boolean in usual. This model is usually used for text categorization, which uses two features instead of word frequency. This event model is particularly suitable for short text classification.

Logistic Regression Classifier[3]
Regression is actually the estimation of unknown parameters of known formulas. In fact, Logistic Regression is a linear regression normalized by logistic equation. In Logistic Regression Classifier, a part of a given training sample is marked as 1 (positive), and the rest is marked as 0 (negative). Train a classifier from these samples and predict the probability of future outcomes based on the performance of historical data.

Linear SVC classifier
Support Vector Classifier searches the best possible linear classifier according to the distribution of training samples. Samples that determine the location of the classification boundary are not all training data, but two data points of different categories with the smallest spacing between the two categories, namely "support vector". Thus, a few training samples which are most effective for prediction tasks can be screened from massive or even high-dimensional data. This kind of classifier is similar to SVC with parameter kernel='linear', but it is implemented lib linear not lib SVM. Therefore, it has more flexibility  [4][5] The idea of Ensemble Learning is: one problem (such as classification problem) involves many kinds of algorithms in prediction (the algorithm in the following figure can solve classification problem). Among the prediction results, the prediction category that appears most is chosen as the final prediction category of the sample. In voting classifier, the results of various models are aggregated by voting. The results of the selected models can be good or bad, so the result of aggregation is the best. The basic idea of voting Classifier is to combine different machine learning models and predict the final labels by voting or averaging. For example, there are five classifiers, classifier1 → class2, classifier2 → class2, classifier3 → class3, classifier4 → class4, classifier5 → class5,then the final predict class is class 2.

Method for the analysis
The author uses five classifiers to do the analysis of sentiment and use voting classifier to aggregate the results from the five classifiers and get the final result. The five classifiers are Gaussian NB classifier, Multinomial NB classifier, Bernoulli NB classifier, Logistic Regression classifier, Linear SVC classifier. These five classifiers use different methods to do the classification. Voting classifier select the result with the most votes as the final results. For each classifier, the author gets the corresponding learning models and store them in the files so that following analysis can use these files.

Training dataset and test dataset
These five classifiers are supervised learning. Therefore, the author should input the training dataset and test dataset which is label data to build the learning model for each classifier and use the models to analyze the new data from WhatsApp public groups. the author gets these two kinds of datasets containing positive data and negative data from Standford sentiment analysis data. Figure 2 shows the datasets the author uses for the training and testing.

Popularity Analysis
A number of people in some WhatsApp public groups are extremely active and send much more message in the groups. However, a few people in some other groups are not such active and the volume of groups' message is much less. Therefore, the author tries to find the popularity of these groups and finds the five most popular groups in different time.
The author makes statistics for the volume of message for each group. When one user sends a piece of message, the author will increase one for the volume of message of corresponding group. Then the author gets all Groups' volume of message and obtains the five most popular groups. The author draws the final results in a bar graph. Figure 2 shows the volume of message for WhatsApp public groups.

Results from Sentiment analysis
In sentiment analysis, the author tries to find the people's emotions in groups. Therefore, the author uses five classifiers to analyze the sentiment and uses Ensemble Learning to aggregate the results from these five classifiers to get the final results. Then the author can use this model to do the sentiment analysis. For this analysis, the author inputs user's chat message in groups and gets the sentiment of this user. Figure 3 shows one result from this model when the author inputs some words.

Results from popularity analysis
In popularity analysis, the author makes statistics for the volume of message in each group and makes a bar graph to show the five most popular groups. Figure 4 shows the popularity bar graph. Figure 4 popularity bar graph. The author can find the five most popular groups in different time. For example, in the begin of June, the author can obtain the five most popular groups are 916036211434-1498983672@g.us, 958512306343-1423782739@g.us, 912321790312-1482398208@g.us, 913284293802-1432809422@g.us and 582908038012-1423838921@g.us.

Conclusion
In this article, the author analyzes WhatsApp public groups in sentiment aspect. In sentiment analysis, the author tries to find the sentiment of users in these groups. The author uses five classifiers to analyze the sentiment and voting classifier to aggregate the results to increase the accuracy and efficiency. The five classifiers are Naive Bayes classifier, Linear SVC classifier, Logistic Regression classifier, MNB classifier and Bernoulli NB classifier. These classifiers use different methods to do the analysis. The author inputs the training dataset and test dataset into this model and lets the five classifiers get the learning models. Then the author uses these five classifiers and voting classifier to find whether the user's chat message is positive or negative.
In popularity analysis，the author makes statistics for the volume of message in each group and makes a bar graph to show the five most popular groups.
By analyzing the data, the author can find predict the sentiment of users. Also, there are many other aspects such as popularity and Multimedia Content to be analyzed. Therefore, the author will also try to analyze the other aspects to find more information in the future.