I thought I'd write up an explanation of how Latent Semantic Indexing works since I used it in my most recent project PUBmatch.co

PUBmatch.co is a tool I thought of while I was at Metis Data Science Bootcamp.  You can see my slides from my presentation here.  

This post has a companion python notebook if you'd like to follow along here: 
Latent Semantic Indexing Notebook

Latent Semantic Indexing appealed to me because it involves the use of Singular Value Decomposition.  Singular Value Decomposition is at the heart of signal processing.  Signal processing is involved in so many systems that we use, it's the unsung hero of the information age.  Telephones, radar, non-destructive testing, data compression,  and movie special effects.   Treating conversation like a signal simplifies the process of extracting meaning.  

Not buying it?  Consider this: How many different ways you can express the same ideas and concepts. In communication we take our ideas  and put together (compose) the appropriate words (frequencies).  We say these words to others (raw signals) to communicate concepts.  Other people hear these words (raw signals) and decompose them into different meanings (frequencies). 

What does it look like?  

The above pictures illustrate the ability to "decompose" a signal into "principal components".  In the example above we're "decomposing" a given signal into two parts. 

How does this relate to LSI (Latent Semantic Indexing)? 

Imagine that each one of those signals in "SVD Original" is a sentence.  Because we've decomposed these two signals we can throw one away.  We'll throw away the Noise and keep the SVD smooth signal.  However, with LSI we're usually filtering out hundreds of thousands of dimensions. The same idea still applies though: Decompose the signal, throw away the parts you don't care about, keep the ones that have meaning.  

Let's do a small example of LSI pseudo-by-hand.  

I have seven sentences.  I'd like to extract the signal or meaning from each one of these sentences so I can see how similar they are to one another.  

The bacon egg and cheese was there.
Bacon goes well with egg and cheese.
Bacon is not cheese.  
There are books about cheese.
I read books about cheese.
I read books.
You read books. 

What sort of signal is in there? LSI will start by having us get rid of "stop words" then put the words into a matrix counting the number of occurrences of each word in each document.  

The bacon egg and cheese was there.
Bacon goes well with egg and cheese.
Bacon is not cheese.  
There are books about cheese.
I read books about cheese. 
I read books.
You read books. 

Now put them into a matrix. 

Now each sentence is represented by the number of occurrences of words.  This is called a "Bag of Words" or "Term Document Matrix".   Each document can be imagined as a vector whose direction is within a hyperspace whose axes are represented by each of the words.  It's called a hyperspace because as soon as you have more than 3 words your space you can't visualize it. 

Now let's decompose this system into 2 principal components.  I use the scipy library to do this. 

 ` from scipy.sparse.linalg import svds as SVDS `
 ` SVDS(<the matrix above>)`

This outputs three matrices: docs, eigen_roots, terms_T.  

We're interested in comparing documents so we will use the docs Matrix.  

In the above matrix, we're representing each doc in a two dimensional space.  Since this is convenient to view for humans so let's visualize these sentences in 2d space.  

The X and Y axes are linear combinations of the preexisting words.  You can see the X axis weighs the word "bacon" negatively whereas the Y axis weighs it positively by roughly the same order of magnitude.  This would cause sentences that have and do not have the word bacon, to be further away from one another.  

Look at the sentences that had the word bacon, they're all pointing in a different direction than the sentences that did not have bacon in them.  

What can I do with this though?  Now you can check similarity of sentences within this reduced space you've created.   This new space we've created contains the "semantic meaning" we've chosen to care about.  

Cosine Similarity is just 1 - Cosine.  You use Cosine because it is only a function of the angular distance between the vectors and thus ignores the magnitudes.  This is important.  If someone is talking about a Bacon Egg and Cheese McMuffin and you're writing a book about the history of the Bacon Egg and Cheese McMuffin, you'll be able to compare the two if you're using cosine similarity, but if you just computed, say, Euclidean distance, the two topics would appear to be vastly unrelated.  

Ok let's compute the cosine similarity between two of these sentences.  
"There are books about cheese"
"You read books"

For this I'll use 
`from scipy.spatial.distance import pdist`
`1 - pdist((<you read books about cheese>,<I read books>))`

Cosine Similarity = 0.763


We can also look at the entire corpus and see how each sentence compares to all the others.  

For more reading, or if you're interested in just jumping right in and doing this yourself I suggest you checkout: Gensim

Tools used:
python, scipy, matplotlib, numpy, jupyter notebook

PUBmatch.co is my passion project completed while at Metis Data Science Bootcamp.  PUBmatch.co makes it easier to parse through the giant open access database PubMed by allowing you to input anything from a news article clipping to an email thread. 

Watch the presentation here: 

This project is open source.  Check it out at www.github.com/ryanglambert/kojak

Receiving Treatment at T = 0 results in 0 mutations and therefore no resistances developed.  This is obviously ideal and unrealistic.

Since the default starting resistance to each drug is "false" at T = 0 , and since viruses aren't allowed to reproduce in the presence of a drug they're not resistant to, you can see there is no reproduction and all viruses clear by roughly T = ~70.  With a final population of 0 in all patients.  

For Prescriptions administered at T = 75, T = 150, and T = 300, there is a marginal difference in number of patients cured (virus pop < 50).  Although, due to T = 300 not being at a steady state we can't include that in our comparison.   

As expected, this looks exactly like the test with one drug at T = 0.   If the patient is cured before T = 100 then a drug at T = 150 should show no difference on either of the histogram or the time series charts.  

For sim 7: T = 75 T = 150 and Sim 8:  two drugs at T = 150 , the results were surprising.  I reran these a couple of times to see that I just hadn't mislabeled them.  

What I expected was for the Sim 7 to have more cured patients since any treatment at all was started earlier.  However, Sim 8 had more cures even though both drugs were administered later.  I think I have an explanation.  

When the patient receives a Drug 1 at T = 75 the virus population hasn't quite hit the "steady state" ceiling that slows reproduction.   So viruses that haven't reached their steady state limit yet have more opportunities to reproduce, and therefore more opportunities for resistance mutation.  

For Sim 8,  the drugs are administered at the same time, and at a steady state virus population which means two things: There are fewer opportunities for resistance mutation, and the mutations have two drugs to mutate resistance to simultaneously giving them an effective  mutation probability of .25% ( .5% * .5%) at time of drug administration.   More analysis would be necessary to characterize this difference in more detail.  

These two simulations also highlight a key difference in the "Time Window of Adminstration" that results in a cure (virus population < 50).  

Sim 9 is kind of funny.  

The drugs are spaced far enough apart that the viruses can mutate against each one independently enough to return to a steady state close to what would have happened if they had taken no drugs at all.  

For the realistic cases (No Drug at T = 0) it appears that taking two drugs simultaneously instead of one or two at different times allows for a larger window of administration (i.e. not requiring you to catch the virus at an early enough time) and higher likelihood of cure.   

Simulation 3 - 5 and 9 resistant populations seem to show that it is actually worse to take 1 drug "not early enough" or to take 1 or 2 drugs too far apart.  Doing so would result in developing mutated viruses that no longer respond to either of the drugs administered.  

This simulation doesn't consider things like:

• side-effects 
  
• drug to drug interactions 
  
• patient compliance
  
• varying strength of drugs
  
• many more
  

which helps me understand how this is a whole entire niche industry in itself. (https://en.wikipedia.org/wiki/Bioinformatics)  
I can also see the use of very powerful computers for this kind of analysis since each simulation run here took roughly 2 minutes running on a MacBook 2.6 gHz 8 GB RAM.   Learning to run these kinds of simulations in the cloud is something I'm planning on the horizon.  

Tools used: matplotlib, numpy, Python
Source:  https://github.com/Ryanglambert/virus_simulation