Review of prediction and data analysis algorithms

Anton Antonov

Accendo Data LLC

Introduction

In this talk we are going to review machine learning and prediction algorithms using Mathematica implementations. The algorithms considered are: decision trees and forests, naive Bayesian classifiers, associative rules learning, bi-sectional clustering, non-negative matrix factorization, prefix trees, static and dynamic ranking of linked items using Markov chains, a sparse linear algebra recommender for histories over item×metadata relations.

We are going to look into couple of classifications of these algorithms and into utilization patterns for their application. All algorithms are demonstrated with relevant examples. Future directions and extensions would be discussed.

The implementations of the discussed algorithms can be found at the GitHub project MathematicaForPrediction, https://github.com/antononcube/MathematicaForPrediction .

Structure of the talk

A motivational example: a search engine and a recommender

Association rules

Document×term matrix

Dimension reduction

Naive Bayesian classifiers

Decision trees and forests

Prefix trees

Static ranks (prestige) with random walks

Outlier detection

Case studies

Classification of the algorithms vs data types

Classification of the algorithms vs problems

Future plans and directions

Who am I

M.Sc. in Mathematics (General algebra) (1997)

M.Sc. in Computer Science (Data bases) (1997)

Ph.D. in Applied Mathematics (Large scale air-pollution simulations) (2001)

Kernel Developer at Wolfram Research, Inc. (2001-2008)
	Developed and documented NIntegrate and Total
	Worked on NSum, linear algebra, similarity, and statistical functions
	First design of the Wavelet framework

Principal Engineer at Sezmi Corporation (2008-2011)
	Recommendation and search engines for movies and TV shows
	Scheduling algorithms for distribution of data by broadcasting

Mathematical modeling and algorithms consultant (2011-2013)
	Panasonic Automotive Systems America
	KIT Digital (now Piksel)
	Elance
	and others

Operations research analyst (now)
	RaceTrac Petroleum

Classification of the problems

Here is a morphological analysis table that presents a classification of the problem areas for the machine learning and prediction algorithms.

Row[{Sequence@@(Button[Dynamic@Style[#[[1]],20,If[CurrentValue["MouseOver"],"HyperlinkActive","Hyperlink"]],SystemOpen["~/MathFiles/Presentations/WTC-2013/"<>#[[2]]],Appearance->None]&/@{{"Morphological analysis of algorithms vs problems","Morphological analysis of algorithms vs problems.pdf"}})}]

Classification of the algorithms

Here is a morphological table that classifies the considered machine learning and prediction algorithms according to the data they can be applied to and the core principles that make the algorithms work.

Row[{Sequence@@(Button[Dynamic@Style[#[[1]],20,If[CurrentValue["MouseOver"],"HyperlinkActive","Hyperlink"]],SystemOpen["~/MathFiles/Presentations/WTC-2013/"<>#[[2]]],Appearance->None]&/@{{"Morphological analysis of algorithms vs data","Morphological analysis of algorithms vs data.pdf"}})}]

A general classification function should be able to discern the different types of data and select an appropriate algorithm.

A motivational example

A movie and TV shows search engine:

Static ranks

Relevance ranks (using a linear vector space representation)

Reverse indexing and ranked join (not prediction per se)

Topics and statistical thesaurus (using dimension reduction)

Outlier detection

MVC with a recommender

User profile

Relevant item candidates first, reordering/filtering second

Association rules instead of profile or for recommendation sets

Prefix trees for prediction of what next is going to be watched

Item-item recommender that can use item-user consumption history or interactions

Linear vector space representation

Given a document, its words can be taken without regard of their order in the document. We say we turn the document into a “bag of words”.

We have m documents and n words.

With the bag-of-words transformation each document can be seen as a point in a (ℝ^n) linear vector space, each axis of which corresponds to a word.

The whole document collection can be seen as a sparse matrix in (ℝ^(m×n)).

Assume that we have ordered in some way all the words (terms) in the document collection and in the space of words (terms) (ℝ^n) the axis (Subscript[e, w]) corresponds to the word (term) w. We represent the document D as a point in (ℝ^n) in the following way:
1. turn D into a bag of words;
2. stem the words of D;
3. for each term w:
3.1. if w does not appear in D then the coordinate of (Subscript[e, w]) is 0,
3.2. if w appears (Subscript[f, w]) times in D then the coordinate of (Subscript[e, w]) is (Subscript[f, w]).

In this representation we can derive the document × term frequency matrix F∈(ℝ^(m×n)) that corresponds to the document collection. The frequency matrix F is further transformed to reflect better the significance of the words in the document collection using different weight functions.

Weight functions

We can take the approach used in search engines for calculating weights for document-term matrices. (See [5].)

Frequency matrix

We use the following definitions of the frequency matrix F.

Each entry (Subscript[f, i j ]) of the matrix F is the number of occurrences of the term j in the list of terms of the document i.

Weights

The matrix F is transformed into the matrix M. Each entry of the matrix F is transformed with the formula

(Subscript[m, i j])=(Subscript[l, i j])(Subscript[g, j])(Subscript[d, i])

where
(Subscript[l, i j]) -- local term weight;
(Subscript[g, j]) -- global term weight;
(Subscript[d, i]) -- normalization weight.

Various formulas exist for these weights and one of the challenges is to find the right combination for each collection of documents we work with.

weightFormulas={
{"local","Binary",χ[(Subscript[f, i j])]},
{"local","Logarithmic",Log[1+(Subscript[f, i j])]},
{"local","Term frequency (TF)",(Subscript[f, i j])},
{"global","None",1},
{"global","Inverse document frequency (IDF)",Log[(n/((∑_j)χ[(Subscript[f, i j])]))]},
{"global","Global frequency\ninverse document frequency (GFIDF)",((∑_j)(Subscript[f, i j]))/(∑_j)χ[(Subscript[f, i j])]},
{"global","Normal",1/(Sqrt[(∑_i)((((Subscript[f, i j])))^2)])},
{"normalization","None",1},
{"normalization","Cosine",((((∑_j)(Subscript[g, j])(Subscript[l, i j])))^(-1/2))}
};
Grid[Prepend[Map[{Style[#[[1]],FontFamily->"Times"],Style[#[[2]],FontFamily->"Times"],Style[TraditionalForm[#[[3]]]]}&,weightFormulas],Style[#,Blue,FontFamily->"Times"]&/@{"weight type","name","formula"}],Alignment->Left,Dividers->{None,{True,True,False}}]

Linear vector space representation -- examples

Bag of words

stopWords

bagOfWords=ToBagOfWords[ToLowerCase@ExampleData[{"Text","UNHumanRightsEnglish"}],{{},stopWords}];
bagOfWords[[1;;30]]

SortBy[Tally[bagOfWords],-#[[2]]&][[1;;20]]

bagOfWords=ToBagOfWords[ToLowerCase@ExampleData[{"Text","Hamlet"}],{{},stopWords}];
bagOfWords[[1;;30]]

SortBy[Tally[bagOfWords],-#[[2]]&][[1;;20]]

Document × term matrix

Using NPR transcripts.

F

Less than 1% fill-in:

Length[ArrayRules[F]]/Apply[Times,Dimensions[F]]//N

It is interesting to see the structure of the sparsity by re-arranging the rows and columns:

Frows=#&/@F;
Frows=SparseArray[Reverse@Sort[Frows]];
Frows=Transpose[Frows];
Frows=Reverse@Sort[#&/@Frows];
Frows=SparseArray[Frows];
Frows=Transpose[Frows];

MatrixPlot[Frows,MaxPlotPoints->1000]

Associative rules learning

Associative rules learning is also known as “market basket analysis”.

Given a set of baskets (or transactions) T:

1. Find μ-frequent sets -- sets of items that appear together more than μ|T| times

2. Extract rules antecedent -> consequent from each μ-frequent set

2.1. apply the measures confidence, lift, leverage, conviction, and others;
2.2. order and filter the rules.

Example: after examining 10000 shopping carts within a day in a Walmart store we can conclude that if people buy jell-o and peanut butter there is 83% probability that they will also buy bread, and this is supported by 2% of the purchases.

Example with movie genres in a catalog.

For more detailed explanations see the documentation at MathematicaForPrediction at GitHub.

Dimension reduction

Dimension reduction is a very useful technique that can be used get insights, data cleaning, and  reduce computational times.

Dimension reduction is very similar to the statistical procedure Principal Components Analysis and both are often done using eigenvalue or singular value decompositions.

We can use Singular Value Decomposition (SVD) and Non-Negative Matrix Factorization (NNMF).

For SVD we have to normlize and centralize the data, but this is not always meaningful for some data (like natural language texts).

NNMF is not unique, has convergence issues, and its basis vectors are not orthogonal, but it can be easily interpreted. 
 (In some sense we trade orthogonality for interpret-ability.)

In this presentation I show clarification examples and topic extraction with NNMF and handwritten digits recognition using SVD.

Example: Statistical thesaurus and topic extraction for NPR podcasts

In this example we are going to demonstrate the use NNMF for topic extraction and statistical thesaurus formation using a collection of full transcripts of NPR podcasts. We are using the so called bag of words model which allows the transcripts to be represented as points in a high dimensional space (e.g. (ℝ^20000)). The topic extraction is a dimension reduction process. The words in the original texts were stemmed first (using Porter stems).

(Link to topic extraction with NNMF .)

Statistical thesaurus

Using NNMF we can find a statistical thesaurus that fits the body of the transcripts. For example, the words “pollution”, “fossil” , ”greenhouse”, “gasoline” are found together in the NPR transcripts.

The statistical thesaurus for the i-th term can be found by taking, say, 20 nearest neighbors of the i-th column from the right matrix factor in a SVD or NNMF (using the Euclidean distance).

Here is a table with examples of statistical thesaurus “entries”.

Magnify[#,1.8]&@({{"word", "statistical thesaurus"}, {"senate", {"senat","republican","democrat","vote","immigr","welna","campaign","mccain","support","committe","amend","elect","voter","pass","presidenti"}}, {"obama", {"obama","presid","republican","elect","vote","democrat","white","campaign","voter","parti","barack","mccain","gun","clinton","polit"}}, {"war", {"war","unit","iraq","relat","meet","forc","translat","kerri","visit","kuhn","weapon","recent","secretari","outsid","soldier"}}, {"pollution", {"pollut","fossil","greenhous","gasolin","solar","rapid","batteri","cleaner","reduct","spill","effici","miner","discount","mit","motor"}}, {"fbi", {"fbi","terror","inform","terrorist","agent","crimin","mall","crime","arrest","kast","homeland","backpack","zwerdl","warrant","investig"}}, {"singer", {"singer","voic","languag","lyric","unintellig","songwrit","listen","foreign","heart","hit","pop","soul","babi","norri","artist"}}, {"jazz", {"jazz","whitehead","musician","bass","player","kevin","tune","piano","sound","pianist","instrument","drummer","rhythm","drum","trio"}}, {"school", {"school","student","univers","colleg","kid","high","teach","class","studi","learn","educ","communiti","program","year","young"}}, {"homeland", {"homeland","surveil","suspici","warrant","privaci","identifi","prioriti","commission","patrol","databas","agent","grain","airlin","bin","citizen"}}})

Statistical thesaurus -- computations

W=Wth;
H=Normal[Hth];

{W,H}=NormalizeMatrixProduct[W,H];

HNF=Nearest[Range[Dimensions[H][[2]]],DistanceFunction->(Norm[H[[All,#1]]-H[[All,#2]]]&)]

Clear[StatThesaurus];
StatThesaurus[word_String,n_Integer:20]:=
Block[{sword,tpos,inds},
sword=word/.stemmingRules;
tpos=Position[terms[[pos]],sword];
If[Length[tpos]==0,{},
inds=HNF[tpos[[1,1]],n];
terms[[pos]][[inds]]
]
];

thWords={"community","marathon","race","rave","homeland","police","ticket","integrate"};
Grid[Prepend[Map[{#,StatThesaurus[#,15]}&,thWords],Style[#,Blue,FontFamily->"Times"]&/@{"word","statistical thesaurus"}],Dividers->All,Alignment->Left,Spacings->{Automatic,0.75}]

60 topics

Here is table of 60 topics extracted using NNMF. Each topic is a vector from the reduced dimension space.

Classification

In a classification problem we are given a training database of labeled records.

The records have attributes.

There is a categorical dependent attribute, the rest are predictor attributes.

The predictor attributes can be both numerical and categorical.

In classification the dependent attribute is called “class label”.

The goal of classification is to find the distribution of the dependent attribute in terms of the predictor attributes.

Classification with decision trees and naive Bayesian classifiers

Let dom(X) denote the domain of the variable X.

Let (Subscript[X, i]), i∈[1,…,k],k∈ℕ, correspond to the variables (the columns) of the given data array.

We assume that there is a function

F:dom((Subscript[X, 1]))×dom((Subscript[X, 2]))×…×dom((Subscript[X, k]))->L.

The function F is called a classifier.

We construct decision trees and naive Bayesian classifiers in order to approximate F.

Classification with decision trees and naive Bayesian classifiers

Comparison over geometric data.

Decision tree:

Naive Bayesian classifier

Example: Handwritten digits recognition

Application of decision trees in comparison with SVD:

“Classification of handwritten digits”

http://mathematicaforprediction.wordpress.com/2013/08/26/classification-of-handwritten-digits/

at my blog “Mathematica for prediction algorithms”, http://mathematicaforprediction.wordpress.com.

Example: Naive Bayesian classifiers and decision trees for GDP per capita analysis

Link to Basic theory and construction of naive Bayesian classifiers.nb .

Sample of a data array with country data

Classification results

Explanation with a decision tree

Prefix trees -- description

In computer science a prefix tree (or a trie) is data structure that allows quick retrieval of associations between a set of keys and a set of values. It is assumed that each key is a sequence of elements. (Most often the keys are considered to be strings i.e. sequences of characters.) The prefix tree nodes do not store the keys. Instead the position of a node in the prefix trees corresponds to a key.

Consider the following list of words:

wordList=Sort[{"war","ward","warden","work","car","cars","carbs"}];
(*TableForm[wordList,TableHeadings->Automatic]*)
TableForm[wordList]

Here is a prefix tree in which the keys are the list of words above and the values are the number of appearances of the corresponding prefix. For example, the prefix “car” appears three times in the list of words; that is why we have path {{},7}->{"c",3}->{"a",3}->{"r",3}.

mytrie=TrieCreate[wordList];
LayeredGraphPlot[TrieToRules[ mytrie],
DirectedEdges->True,VertexRenderingFunction->({Lighter[Yellow],EdgeForm[Darker[Red]],Rectangle[#-{0.4,0.2},#+{0.4,0.2}],Black,Text[Style[#2[[1]],FontSize->14],#1]}&),ImageSize->600]

We can shrink the tree by merging nodes that have only one child with their child. In this way we produce a tree in which each node would have an inseparable sub-sequences of elements. (In these examples these elements are characters.)

mytrie=TrieCreate[wordList];
LayeredGraphPlot[ mytrie//TrieShrinkLeafs//TrieToRules,
DirectedEdges->True,VertexRenderingFunction->({Lighter[Yellow],EdgeForm[Darker[Red]],Rectangle[#-{0.4,0.2},#+{0.4,0.2}],Black,Text[Style[#2[[1]],FontSize->14],#1]}&),ImageSize->600]

Another transformation of the tree is to replace the numbers of appearances with probabilities -- each value of a node is the probability the to arrive at that node from the parent.

mytrie=TrieCreate[wordList];
LayeredGraphPlot[ mytrie//TrieNodeProbabilities//TrieToRules,
DirectedEdges->True,VertexRenderingFunction->({Lighter[Yellow],EdgeForm[Darker[Red]],Rectangle[#-{0.4,0.2},#+{0.4,0.2}],Black,Text[Style[#2[[1]],FontSize->14],#1]}&),ImageSize->600]

And of course we can do both transformations.

mytrie=TrieCreate[wordList];
LayeredGraphPlot[ mytrie//TrieShrinkLeafs//TrieNodeProbabilities//TrieToRules,
DirectedEdges->True,VertexRenderingFunction->({Lighter[Yellow],EdgeForm[Darker[Red]],Rectangle[#-{0.4,0.2},#+{0.4,0.2}],Black,Text[Style[#2[[1]],FontSize->14],#1]}&),ImageSize->600]

Further explanations about prefix trees can be found at http://en.wikipedia.org/wiki/Trie .

Prefix trees -- applications

Road trips example

1. Trips are seen as sequences of road network segments.

2. Hence using prefix trees we can calculate looking at the beginnings of the trips the probabilities of the destinations .

3. Time can be easily included: sequences in the Cartesian product of time intervals and road network segments.

4. Works great with crowd-sourcing / collaborative filtering strategies.

Trip prefix tree example

Kanji recognition example

1. The sequence of the strokes is used to predict the pictogram candidates.

2. For example, consider prefix trees of sequences of strokes placed in the seven radical positions.

http://japanese.about.com/library/weekly/aa070101a.htm

Principles and analogies

Address sparsity

Bad inter-connectivity

Too many tags

Too few tags per item

Make the data consistent with the philosophy of your prediction system or data analysis

Add more data columns

Item-item recommenders

Decision trees

Naive Bayesian classifiers

Association rules

Multiple tags from a time taxonomy from timestamps

Multiple time taxonomy tags from time stamps

Multiple time taxonomy tags from time stamps

Building classifiers is slow, classification is fast and with small memory requirements

Find candidates quickly then apply more precise algorithms

Plagiarism catching -- dimension reduction, n-grams

Linear algebra recommendations, predicate sets

Collaborative filtering instead of data curation and relationship explanations

Also, try to put the interaction (collaborative) history in a (bi-partite) graph.

Make a family of predictors and combine them

With linear regression

With a voting scheme

No need of explanation ability

Good classifiers might have very complicated internals.

Examples:

Family of clusterings with regression combinator

Neural networks

Random forests

Case studies

Plagiarism catching

Automatic metadata derivation

Finding the most important statements in Freakonomics podcasts

Recommendations with dynamic ranks

Extensions

Methodological

Combination with optimization

Programming R&D

References

[1] Breiman et al, Classification and Regression Trees, Chapman and Hall/CRC; 1 edition (January 1, 1984), http://www.amazon.com/Classification-Regression-Trees-Leo-Breiman/dp/0412048418

[2] Ye, ed., ‪The Handbook of Data Mining, CRC Press; 1 edition (November 21, 2004), 				http://www.amazon.com/gp/search?index=books&linkCode=qs&keywords=0805855637

[3] Breiman, Statistical Modeling: The Two Cultures (2001),
http://faculty.smu.edu/tfomby/eco5385/lecture/Breiman’s%20Two%20Cultures%20paper.pdf