# Category: PROBLEM SOLVING

## Dynamic Programming in NLP - Skip Grams

In this series of posts, I will be exploring and showing how dynamic programming technique is used in machine learning and natural language processing. Dynamic programming is very popular in programming interviews. DP technique is used mainly in problems which has optimal substructure and can be defined recursively, which means that a problem of size N can be solved by solving smaller sub-problems of size m < N. Such problems […]

## LeetCode : Cherry Pickup

Problem Statement Solution : This problem is probably one of the most difficult path traversal problem, I have seen on LeetCode and I will let you know the reason why. The most faulty assumption to begin with is that, this can be solved using a greedy approach, i.e. find the maximum possible cherries during the forward traversal (0,0) to (N-1, N-1) and then find the maximum possible cherries during the […]

## LeetCode : Reaching Points

Problem Statement Solution : The obvious way is to go with a DFS or BFS like approach. Starting from the point (sx, sy), we can go in two possible directions (sx + sy, sy) and (sx, sx + sy) and then each of these points can go in two possible directions and so on. Note that the paths will form a tree like structure as we are going in either […]

## LeetCode : Swim in Rising Water

Problem Statement Solution : One possible solution is to see whether for each water level, he can swim from (0, 0) to (N-1, N-1) without waiting anywhere in between. To check whether he can swim from (0, 0) to (N-1, N-1) i.e. there exists a path, we can use DFS or BFS to traverse the matrix. He can swim from point A to B if the height of B is less […]

## Building a Neural Network from scratch in Python

In this post I am going to build an artificial neural network from scratch. Although there exists a lot of advanced neural network libraries written using a variety of programming languages, the idea is not to re-invent the wheel but to understand what are the components required to make a workable neural network. A full-fledged industrial scale neural network might require a lot of research and experimentation with the dataset. Building a simple […]

## Building an Incremental Named Entity Recognizer System

In the last post, we saw how to train a system to identify Part Of Speech tags for words in sentences. In essence we found out that discriminative models such as Neural Networks and Conditional Random Fields, outperforms other methods by 5-6% in prediction accuracy. In this post, we will look at another common problem in Natural Language Processing, known as the Named Entity Recognition (NER in short). The problem […]

## Building a POS Tagger with Python NLTK and Scikit-Learn

In this post we are going to understand about Part-Of-Speech Taggers for the English Language and look at multiple methods of building a POS Tagger with the help of the Python NLTK and scikit-learn libraries. The available methods ranges from simple regular expression based taggers to classifier based (Naive Bayes, Neural Networks and Decision Trees) and then sequence model based (Hidden Markov Model, Maximum Entropy Markov Model and Conditional Random […]

## Generative vs. Discriminative Spell Corrector

We have earlier seen two approaches of doing spelling corrections in text documents. Most of the spelling errors encountered are in either user generated contents or OCR outputs of document images. Presence of spelling errors introduce noise in data and as a result impact of important features gets diluted. Although the methods explained are  different in how they are implemented but theoretically both of them work on the same principle. […]

## Using Word Vectors in Multi-Class Text Classification

Earlier we have seen how instead of representing words in a text document as isolated features (or as N-grams), we can encode them into multidimensional vectors where each dimension of the vector represents some kind semantic or relational similarity with other words in the corpus. Machine Learning problems such as classification or clustering, requires documents to be represented as a document-feature matrix (with TF or TF-IDF weighting), thus we need some […]

## Designing a Contextual Graphical Model for Words

I have been reading about Word Embedding methods that encode words found in text documents into multi-dimensional vectors. The purpose of encoding into vectors is to give "meaning" to words or phrases in a context. Traditional methods of document classification treat each word in isolation or at-most use a N-gram approach i.e. in vector space, the words are represented as one-hot vectors which are sparse and do not convey any meaning whereas […]