13 Text Classification and Naive Bayes

Question 1

Standing query

Answer 1

Is like any other query except that is is periodically executed on a collection to which new docs are incremantally added over time.

Question 2

Classification

Answer 2

Given a set of classes, we seeks to determine which class(es) a given object belongs to.

Question 3

Routing/filtering

Answer 3

Classification using standing queries.

Question 4

Topics

Answer 4

A general class is usually referred to as topic. For instance ÒChinaÓ or ÒcoffeÓ

Question 5

Applications of classification in IR

Answer 5

Preprocessing steps Finding a docs encoding, truecasing, and identifying the language of a doc Spam Automatic detection of spam pges, which are then not included in the search engine index Porn mode Filter out Sentiment detection The automatic classification of a movie or prduct review as positive or neg- ative. Personal email sorting Finding the correct folder for a new email. Topic-specific or vertical search Vertical search engines restrict searches to a partical topic. For example, the query Òcompute scienceÓ on a fertical search engine for the topic China will return a list of Chinese computer science departments with higher precision and recall than the query Òcomputer science ChinaÓ on a general prupose search engine. Ranking function The ranking function in ad hoc IR can also be based on a document classifier. More specified later. (sec. 15.4)

Question 6

Rules in text classification (TC)

Answer 6

A rule captures a certain combination of keywords that indicates a class. Hand-coded rules have good scaling properties, but creating and maintaining them over time is labor intensive. In machine learning these rules are learned automatically from training data

Question 7

Statistical text classification

Answer 7

The approach where where rules are learning automatically with machine learning.

Question 8

Labeling

Answer 8

The process of annotating each doc with its class.

Question 9

Document space

Answer 9

In TC we are given a description d ∈ X of a document where X is the docu- ment space. Typically, the document space is some type of high-dimensional space.

Question 10

Space class

Answer 10

In TC, we are given a fixed set of classes C = {c1, c2,…,cj} Typically, the classes are human defined for the needs of an application.

Question 11

Training set

Answer 11

In TC, we are usually given a training set D of labeled docs <d> where <d> ∈ X x C</d></d>

Question 12

Learning method classifier

Answer 12

Using a learning method or learning algorithm, we then with to learn a classificer or classification function ɣ that maps documents to classes: ɣ : X -> C

Question 13

Surpervised learning

Answer 13

The above type over learning is called supervised learning because a su- pervisor serves as a teacher directing the learning process. We denote the supervised learning method _ and write _(D) = _. The learning method _ takes the training set D as input and return the learning classification function _

Question 14

Test set data

Answer 14

Oncle we have learning ɣ, we can apply it to the test set, for example, the new doc, “first rpivate Chinese airline” whose class in unknown. The classification function hopefylle assigns the new document to class ɣ(d’) = China.

Question 15

Spareseness

Answer 15

The training data are never large enough to represent the frequency of rare events adequately. Therefore, the probability will often be zero.

Question 16

Bernoulli model

Answer 16

Equivalent to the binary independence model, which generates an indicator for each term of the vocabulary, either 1 indicating presence of the term in the doc or 0 indicating absence.

Question 17

Concept drift

Answer 17

The graudal change over time of the concept underlying a lcass like US pres- ident from George W. Bush to Barack Obama. The Bernoulli model is par- ticularly robust with respect to this because the most important indicators of a class are less likely to change.

Question 18

Feature selection

Answer 18

Is the process of selecting a subset of the terms occuring the training set and using only this subset as features in TC. Two main purposes:

1. It makes training and applying a classifier more efficient by decreasing the size of the vocabulary. Important for classifiers that are expensive to train (unlike NB)
2. It often increases classification accuracy by elimination noise features

Question 19

Noise feature

Answer 19

Is one that, when added to the doc representation, increases the classification error on new data. Example Suppose are rare term, say arachnocentric, has no info about a class, say China, but all instances of arachnocentric happen to occur in China docs in out training set. Then the learning method might produce a classifier that misassigns test docs containing arachnocentric to China.

Question 20

Overfitting

Answer 20

Such an incorrect generalization from the example above from an accidental property of the training set is called overfitting.

Question 21

Mutual information (MI)

Answer 21

MI measures how much info the presence/absence of a term contributes to making the correct classification decision.

Question 22

X² feature selection

Answer 22

In statistics, the X² test is apllied to test the independce of two events. In feature selection, the two events are occurerence of the term and occurrence of the class. A high X² value indicates that the hypothesis of independence, which implies that expected and observed counts are similar, are inncorrect.

Question 23

Frequency-based feature selection

Answer 23

A feature selection method. It selects some frequent terms that have no specific info about the class.

Question 24

Greedy feature selection

Answer 24

All the tree feature selection methods desrbed (MI, X2 and frequency based feature selection) are examples of greedy methods. They may select features that contribute no incremental information over previously selected features.

Question 25

Two-class classifier

Answer 25

An approach to an any-of problem. You must learn several two-class classi- fier, one for each class, where the two-class classifier for class c is the classifier for the two classes c and its complement c̄

Question 26

Effectiveness

Answer 26

Is a generic term for measures that ealuate the quality of classification deci- sions, including precision, recall, F1 and accuaracy.

Question 27

Performance

Answer 27

Refers to the computational efficiency of classification and IR systems.

Question 28

Macro/Micro- averaging

Answer 28

We often want to compute a single aggregate measures that combines the measures for individual classifier. There are two methods for doing this.

Macroaveraging
Computes a simple average over classes

Microaveraging
Pools per-doc devision across classes, and then computes an effectiveness measure on the pooled contigency table.

The differences between the two methods can be large. Macroaveraging gives equacl weights to each class, whereas microaveraging gives equal weight to each per-doc classification decision.

Question 29

Development set

Answer 29

A set for testing while you develop your methods.