Text Analysis (Part-6)

 In the previous lectures we had already covered various important Text Analysis Technique, this lecture was not about the technique to perform text analysis but it was about the technique to faster the process of Text Analysis, this is named as  Locality Sensitive Hashing (LSH).

Locality Sensitive Hashing

Why LSH?

The task of finding nearest neighbours like finding the similar document is very common. Although using brute force to check for all possible combinations will give us the exact nearest neighbour but it is not practical for larger data as it is time consuming. Approximate algorithms to accomplish this task has been an area of active research, although these algorithms don’t guarantee the exact answer, but provide a good approximation. These algorithms are faster and scalable. Locality sensitive hashing (LSH) is one such algorithm which have various applications.

Basic Idea

LSH refers to a family of functions (known as LSH families) to hash data points into buckets so that data points near each other are located in the same buckets with high probability, while data points far from each other are likely to be in different buckets. This makes it easier to identify observations with various degrees of similarity.


The goal of the LSH is to find the near duplicate pairs of documents from the given large collections of documents. For this LSH algorithm has been divided into 3 steps:

  • Shingling
  • Min Hashing
  • Locality-sensitive hashing

The basic idea can be depicted as below

Shingling

In this step, we convert each document into a set of characters of length k (also known as k-shingles or k-grams). The key idea is to represent each document in our collection as a set of k-shingles.

Example Consider there is one document, D, “Nadal”. Now if we’re interested in 2-shingles, then our set will be {Na, ad, da, al} and similarly set of 3-shingles will be {Nad, ada, dal}.

Certain facts regarding the shingles:

  • Similar documents are more likely to share more shingles
  • Reordering paragraphs in a document of changing words doesn’t have much affect on shingles
  • k value of 8–10 is generally used in practice. A small value will result in many shingles which are present in most of the documents (thus, bad for differentiating documents)

Jaccard Index

We’ve a representation of each document in the form of shingles. Now, we need a metric to measure similarity between documents. Jaccard Index is one of the matrix that one can use. Jaccard Index between any two documents A & B can be defined as:

It’s also known as intersection over union (IOU). Suppose A: “Nadal” and B: “Nadia”, then 2-shingles representation will be:

A: {Na, ad, da, al} and B: {Na, ad, di, ia}.

Thus, Jaccard Index = 2/6

It is to be noted that more number of common shingles will result in bigger Jaccard Index and hence more likely that the documents are similar.


Hashing

The idea of hashing is to convert each document to a small signature using a hashing function H. Suppose a document in our corpus is denoted by d. Then:

  • H(d) is the signature and it’s small enough to fit in memory
  • If similarity(d1,d2) is high then Probability(H(d1)==H(d2)) is high
  • If similarity(d1,d2) is low then Probability(H(d1)==H(d2)) is low
Note: Choice of Hashing is tightly linked to the similarity metric we are using. For Jaccard Similarity the appropriate hashing function is min-hashing.

Min Hashing

This is the somewhat technical and critical aspect of this algorithm.

Step 1: Random permutation (π) of row index of document shingle matrix.

Step 2: Hash function is the index of the first (in the permuted order) row in which column C has value 1. Do this several time (use different permutations) to create signature of a column.


Locality-Sensitive Hashing

The general idea of LSH is to find a algorithm such that if we input signatures of 2 documents, it tells us that those 2 documents form a candidate pair or not i.e. their similarity is greater than a threshold t. It is to be noted that we are taking similarity of signatures as a proxy for Jaccard Similarity between the original documents.

  • Hash columns of signature matrix M using several hash functions
  • If 2 documents hash into same bucket for at least one of the hash function we can take the 2 documents as a candidate pair

Band Partition

The algorithm is as followed:

  • Divide the signature matrix into b bands, each band having r rows
  • For each band, hash its portion of each column to a hash table with k buckets
  • Candidate column pairs are those that hash to the same bucket for at least 1 band
  • Tune b and r to catch most similar pairs but few non similar pairs

Comments

Post a Comment

Popular posts from this blog

Model Evaluation and Selection

Image
Model Process :    In decision maker process, we follow f : x  → y and Real world process (RWP) tends to the population. After building a model, we need to know, how accurate the model is expected to be on population. For that, here comes the Confusion Matrix Here we are getting 88 out of 100 as correct, therefore the                        Accuracy = 88/100 = 0.88 we need to check whether the accuracy will be fine for model, for that we check Expected Accuracy.                                E[x] =  Σ x P(x)X                                h(x(vector)) = y (Actual) Goal to be achieved here is    h(x(vector)) = f(x(vector)) for each x belongs to population.   h(x(vector)) = y , E [ h(x(vector)) = f (x(vector)) ] for each x belongs...
Read more

Convolutional Neural Networks(Part-4)

Image
  AlexNet AlexNet is considered to be the first paper/ model which rose the interest in CNNs when it won the ImageNet challenge in 2012. AlexNet is a deep CNN trained on ImageNet and outperformed all the entries that year. It was a  major improvement  with the next best entry getting only 26.2% top 5 test error rate. Compared to modern architectures, a relatively simple layout was used in this paper. ZFNet ZFNet is a modified version of AlexNet which gives a better accuracy.  One major difference in the approaches was that ZFNet used 7x7 sized filters whereas AlexNet used 11x11 filters. The intuition behind this is that by using bigger filters we were losing a lot of pixel information, which we can retain by having smaller filter sizes in the earlier conv layers. The number of filters increase as we go deeper. This network also used ReLUs for their activation and trained using batch stochastic gradient descent. GoogLeNet The GoogLeNet architecture is very different f...
Read more

Introduction to Machine Learning(Part-4)

Image
Training Data is the subset of population, where population can be of n variables x 1 ,x 2 ,........,x n . Let us discuss it by example , assume we are taking to factors to differentiate individuals that is Eye color and Hair color. Eye color can be Blue,Green  and Brown. Hair color can be Black, red, blond and grey. So the total combinations we will be working be 3*4 = 12 Here, we can make prediction of function by Joint Probability Distribution.We assume that eye color and hair color does not tell us much about the individuals.Let us add an attribute Milk allergy which has binary values Yes(y) or No(N), now the combinations on which we can work will be 3*4*2 = 24. If we add an another attribute income which is continuous then the combinations to learn is  3*4*2* ∞ =  ∞. So , there are two ways by which we can learn this problem: Discretize / Bucket : In this we divide the attribute income in interval like: k maps to [1,100k] ,[100k,500k,.......] Probability Density Func...
Read more