A => B, If A is true, then B is True

Logically this is equivalent to ~A U B

Clustering:

Group of similar user/user-queries based on terms

group of similar comments based on words

group of animal observation having similar features

Find regions that are more populated than random data

i.e regions where r = P(X)/P_o(X) is large ( P_o(X) is uniform)

f(X) = E[y|X] = r/(1+r)

Rule Mining: Clustering Features

Association Rule Mining:

Nice to Read: http://www.academia.edu/648890/Support_vs_Confidence_in_Association_Rule_Algorithms

Infer rule A,B,C => D if

high support: P(A,B,C,D) > s

high confidence: P(D|A,B,C) > c

high Interestingness: P(D |A,B,C) / P(D) > i

Problems with Association Rules:

Characterization of classes:

small classes get left out

use decision trees instead of association rules based on mutual information – costly

Learning rules from data:

high support means negative rules cannot catered as it focusses only on association

use “interesting subgroup discovery” instead

Nice to Read: Beyond market baskets: generalizing association rules to correlations”

One Approach to Latent Models:

Matrix A needs to be written as A ≈ XY (i.e) m X n = (m X k )(k X n) [ m words, n documents, k topics]

since X and Y are always smaller, this is almost always an approximation

so we minimize || A – XY ||_F  – Here _F means sum of squares

Subject to all entries being non-negative – NNMF

Graph Based Problems – Pregel

Map Reduce Evolution – Iterate

Many applications require repeated MR

1. iterate MR:
   • but make it more efficient – Avoid Data copy (HaLoop, Twister)
2. generalized data-flow graph of Map Reduce tasks
   • tasks are blocking for Fault Tolerant (Dryad/LINQ, Hyracks)
3. direct implementation of recursion in MR
   • How to recover from non-blocking tasks failing?
   • graph model: (Pregel, Giraph – Hadoop, Graphlab, GPS)
   • stream model: (S4)

Repeated Matrix Vector Products using MR:

Matrix Vector Product as Graph operation:

Pregel ( Graph Programming Model):

Each Vertex executes the code once the graph is loaded

Each Vertex knows its outgoing edges

Vertices are distributed across processors

SuperStep: Each Vertex

 receives messages from in-neighbours

 … computation…

sends messages to out-neighbours

decides whether or not to halt

(halt: vertex stays  inactive except if it receives  a message)

computation halts if all vertices are in halt state

Pregel Summary:

• Appropriate if problem can be mapped to a Graph
• Data needs to fit in total memory
• avoids reloading data between iterations
• need to properly distribute vertices to machines: graph partitioning
• Important Features:
  • Combiners – Avoid repeating identical messages
  • aggregation – global checks
  • Graph mutation – vertices can modify the graph

Have a look: http://www.cs.rochester.edu/u/sandhya/csc258/seminars/naim_mapreduce.pdf

Resource Description Framework Graphs

• Model graphs are a bag of edges
• Every edge is a triple.
• <subject><predicate><object>
• Each node/edge has a unique identifier (URI)

Graph Query Language:

• Datalog
• XPath
• Blueprints/Gremlin
  • Rich JDBC-like Graph traversal API
• SPARQL:
  • Query by Patterns or template of Patterns
  • Proposed extensions to include full graph traversal support

Linked Open Data and Challenges:

• 30 Billion edges (RDF) and growing
• Graph is growing larger
• Recursive Traversals
• Data partitioning is not easy
  • Complex Interconnectivity
  • Pay as you grow model

Graph Data Management:

• Transactional GDM
  • Neo4J
  • Jena
  • HyperGraphDB
  • RDF3x
• Analytical GDM
  • Pregel
  • Giraph
  • Hama
• Both
  • Trinity
  • Horton
  • Titan

Graph Problems:

• Reachability Queries
• Shortest path Queries
• Pattern Queries

HW:

Partitioning RDF graphs for parallel execution is hard because

Why Big Data Technology?

Challenges of Traditional Data warehousing Technology:

1. Fault Tolerance at scale
2. Variety of Data Types
3. Manage data volumes without archiving
4. Parallelism

Parallel Computing:

Speed up S = T₁/T_p, Time with p processors vs with one

Efficiency E = T₁/pT_p

Scalable Algorithm – E, increasing function of n/p, Where n is the ‘problem size ‘

Parallel Efficiency of Map Reduce:

Post Map Data – σD

P Processors – Mappers+Reducers

wD – Useful word to be done

OverHeads – σD/P  – Intermediate data to be written by each Mapper

Time for transmitting to P reducers = (OverHeads/P reducers)* P mapper results = (σD/P²)*P = σD/P

Efficiency of MR – ε_MR =  Useful Work to be done / Work done by MR

Useful Work done = wD

Work done by MR = P ( work done by each process + Intermediate write + Intermediate read work done by each process)

= P ( wd/P +  (2c σD/P)  )

ε_MR = wd / P ( wd/P +  (2c σD/P)  ) = 1 / (1 + 2cσ/w)

This implies Efficiency of MR is independant of P. Therefore it is scalable.

Efficiency approaches 1 if useful work done per data item grows, independent of P.

Calculating Parallel Efficiency for WordCount:

n – No of Documents

m – No of words

f – Average frequency of the words occuring in each document

Total Data = nmf

Intermediate data = atmost m words * P processes = mP

σD = mP

σ = mP/D = mP/nmf = P/nf

Substituting in Efficiency equation

ε_MR = 1 / (1 + 2cσ/w) = 1 / (1 + 2c P/wnf)

Assuming c and w are same,

ε_MR = 1/(1 + 2P/nf)

as n/P –> ∞, ε_MR ==> 1

Preamble:

Search Engine, Social Networking site, Auction sites live on ads. Thereby they need to

• Recognize and Distinguish Shopper and Surfer from a browser
• Gauge opinion and sentiment
• Understand what people say
• Machine learning from Information Theory

Shannon Theory – Measuring Information:

Information is related to Surprise.

Dog bites a man – Not news

Man bites a dog – Interesting !!!!!!

Message informing us of an event that has the probability conveys

– log ₂ p gives the bits of information

TF – IDF:

Rarer words make better keywords

IDF = Inverse document frequency of word w = log ₂ (N/N_w)

where

N = Total documents

N_w = Documents containing word w

More frequent words make better keywords

(n_w)^d  = Frequency of w in document d

TF – IDF = term-frequency x IDF = (n_w)^d  log ₂ (N/N_w)

Document that has the word Turing 15 times is more likely about Computer Science than one with 2 Occurrences

TF – IDF was invented as a heuristic technique

Mutual information between all words and all pages is proportional to

Σ_d Σ_w  (n_w)^d  log ₂ (N/N_w)

Language and Statistics:

Does similar documents have similar TF-IDF keywords?!!

Semantics of a word-use depend on context. Is it computable?!!

Is semantics i.e Meaning just Statistics ?!! or more 

Machine learning : Shoppers or Surfers:

Machine learning is all about learning from the past data.

– past behaviour of many many searchers using these keywords

For ex: With Keywords Red, Flower, Gift, Cheap what is the likely chances that the user will end up in a buy

Prediction Using Conditional Probability:

Determine P(B) , given R, F , G, C. In other words P(B|R, F, G, C)

Sets, Frequencies and Bayes Rule:

p(B|R) = (i/r)

p(R) = (r/n)

p( B and R ) =  i/n = i/r * r/n = p(B|R) p(R)

This is Bayes Rule.

p(B,R) = p(B|R) p(R) = p(R|B) p(B) = i/k * k/n

Naïve Bayer’s Classifier:

P(B|R,C) P(R,C)       =       P(R,C|B) P(B) – Bayer’s rule

=       P(R|C,B) P(C|B) P(B) – Bayer’s rule

=       P(R|B) P(C|B) P(B) – R and C are independent

Given values r and c for R and C

compute:

 p(r|B=y) * p(c|B=y) * p(B=y)

p(r|B=n) * p(c|B=n) * p(B=n)

Choose B =y if this is >α(usually 1) and B=n otherwise

Likelihood Ratio:

L = _i=1∏ ⁿ  p(x_i |B =y) * p(B=y)
                    p(x_i |B =n) * p(B=n)

Sentiment Vs Machine Learning:

Millions of tweets per day. Companies can listen to the voice of their customers like never before

Sentiment – Brands/ Competitive position … +/- counts

Using the likelihood ratio to define if the new tweet is likely positive or not.

Machine Learning and Mutual Information:

Mutual information between Feature (F) viz Red, Cheap.. and Behaviour (B) viz Buyer, Surfer… is

I(F,B) = _f,b Σ p(f,b) log[ p(f,b) / p(f)p(b)

If f and b are independent, then p(f,b) = p(f) p(b), thereby I(F,B) = 0

This implies if F and B are independent there will be no mutual information across both.

Opinion Mining Vs Sentiment:

Using Information Theory we can figure whether or not it is positive or negative comment/compliant.

But what are they complaining about ?!!!!

Example:

Book me an American flight to New york. I hate British food.

– Here the user may probably refer the word American to airliner rather than the nationality

Book me an American flight to New york. I hate English food.

– Here the user may probably refer the word American to Nationality rather than the airliner

Took the car on a terrible, bumpy road,it did well enough.

– Is the family happy with their new car?

– Does Bayer classifier work good in this? probably not !!!!!!

Bayesian learning using “bag of words” – is it enough ?!!