Chars2vec: character-based language model for handling real world texts with spelling errors and human slang

This paper describes our open source character-based language model chars2vec. This model was developed with Keras library (TensorFlow backend) and now is available for Python 2.7 and 3.0+.

Introduction

Creating and using word embeddings is the mainstream approach for handling most of the NLP tasks. Each word is matched with a numeric vector which is then used in some way if the word appears in text. Some simple models use one-hot word embeddings or initialise words with random vectors or with integer numbers. The drawback of such models is obvious – such word vectorisation methods do not represent any semantic connections between words.

There are other language models, called semantic, collating words related by sense with the affine embedding vectors. In fact these models represent contextual proximity of various words: such models are trained on a large corpora of existing texts such as encyclopedias, news texts or literature. The result is that the words appearing in similar contexts in these texts are represented by proximal vectors. The classic examples of semantic language models are Word2Vec and GloVe. Some of the more modern semantic language models (ULMFiT, ELMo) are based on the recurrent neural networks (RNNs) and on other neural network architectures.

Semantic models contain some information about the sense of words extracted while training on large texts corpora but they operate with a fixed vocabulary (usually lacking some rarely used words). This is a significant drawback for solving some of NLP problems. If a number of important words in a text does not belong to the vocabulary of a semantic language model then it is non-efficient in solving some kinds of NLP tasks — the model won’t be able to interpret these words. Such a case could arise if we try to process texts written by humans (these could be replies, comments, applications, documents or posts in web). These texts could contain slang, some rare words from specific areas, or given names which are not presented in language vocabulary and, accordingly, in semantic models. Typos also produce “new” words without any collated embedding.

A good example is the task of processing user’s comments to movies while building a movie recommender system based on MovieLens dataset. Words “like Tarantino” could often be found among peoples comments; errors or typos in director’s surname “Tarantino” produce a number of “new” words like “Taratino”, “Torantino”, “Tarrantino”, “Torontino”, etc. The ability to extract this “Tarantino” feature from users comments would obviously improve movies relevance metric and recommendations quality as well as extraction of various other features represented by non-vocabulary words, either very specific like surnames, or produced by typos and erroneous spelling.

To solve the problem we have described it would be appropriate to use a language model that would create word embeddings based only on their spelling and would collate similar vectors to similarly spelled words.

About chars2vec model

We have developed the chars2vec language model based on symbolic embeddings of words. The model represents each sequence of symbols of arbitrary length with a fixed length vector, the similarity in words spelling is represented by the distance metric between vectors. This model is not dictionary based (it does not store a fixed dictionary of words with corresponding vector representations), that is why it’s initialisation and usage procedures do not require significant computational resources. Chars2vec library could be installed via pip:

>>> pip install chars2vec

The following code snippet creates chars2vec embeddings (with dimension 50) and projects these embedding vectors on a plane with the help of PCA, outputting an image depicting the geometrical meaning of the described model:

Execution of this code produces the following image:

We can see that the similarly spelled words are represented by the neighbouring vectors. Yet the model is based on a recurrent neural network accepting a sequence of symbols of a word, not on analysis of the facts of letters or patterns presence in a word. The more changes such as additions, deletions or replacements we make in a word the further its embedding would stand from the original.

Application of character-based models

The idea of text analysis on character level is not new — there are models creating embeddings for each symbol and then creating symbolic word embedding with the help of an averaging procedure. The averaging procedure is the bottleneck — such models provide some sort of solutions of the problems stated above, unfortunately, not the optimal ones, because the search of the proper form of each word’s embedding creation from the symbols embedding vectors requires additional training if we want to encode some information about the symbols relative positioning and symbolic patterns besides the mere fact of symbols presence in a word.

One of the pioneering NLP models processing texts on the character level is karpathy/char-rnn. This model takes some text as an input and trains a recurrent neural network (RNN) to predict the next symbol of a given sequence of characters. There are other RNN based character-level language models such as Character-Level Deep Learning in Sentiment Analysis. In some cases the convolutional neural networks (CNNs) are used to process a sequence of characters, check out Character-Aware Neural Language Models, an example of CNNs usage for texts classification could be found in the paper Character-level Convolutional Networks for Text Classification.

A prime example of a character-based language model is the model implemented in the fastText library by Facebook. The fastText model creates symbolic word embeddings and solves texts classification problem based on their symbolic representation. This technology is based on the analysis of multiple n-grams forming words instead of RNNs which makes this model very sensitive to typos and spelling errors as far as they can significantly change the range of n-grams forming a word. Yet this model provides embeddings of words missing from the language vocabulary.

Model architecture

Each chars2vec model has a fixed list of characters used for words vectorisation: the characters from this list are represented by various one-hot vectors which are fed to the model when the character appears in the text; the characters absent in the list are ignored in the vectorisation procedure. We trained models designed to process English texts; these models use a list of the most popular of ASCII characters — all English letters, digits and the most popular punctuation:

[‘!’, ‘“‘, ‘#’, ‘$’, ‘%’, ‘&’, “‘“, ‘(‘, ‘)’, ‘*’, ‘+’, ‘,’, ‘-’, ‘.’, ‘/’, ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘:’, ‘;’, ‘<’, ‘=’, ‘>’, ‘?’, ‘@’, ‘_’, ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’, ‘m’, ’n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’, ‘v’, ‘w’, ‘x’, ‘y’, ‘z’]

The model is not case sensitive, it converts any symbol’s case to the lower one.

Chars2vec is implemented with the help of Keras library based on TensorFlow. The neural network creating words embeddings has the following architecture:

A sequence of one-hot vectors of an arbitrary length representing the sequence of characters in a word, passes through two LSTM layers, the output is the embedding vector of the word.

To train a model we have used an extended neural network including chars2vec model as a part. To be more specific, we are dealing with a neural network taking two sequences of one-hot vectors representing two different words as an input, creating their embeddings with one chars2vec model, calculating the norm of the difference between these embedding vectors and feeding it into the last layer of the network with the sigmoid activation function. The output of this neural network is a number ranging from 0 to 1.

The extended neural network is trained on pairs of words, in training data a pair of “similar” words is labeled with 0 value, and a pair of “not similar” with 1. In fact we define the “similarity” metric as a number of substitutions, additions and removals of characters that have to be performed to make one word from the other. This brings us to the way of obtaining such training data — it can be generated by taking a multitude of words and then performing various changes upon them to obtain a new set of words. A subset of new words produced by changes in one original word would naturally be similar to this original word and such pairs of words would have label 0. Words from different subsets would obviously have more differences and should be labeled with 1.

The size of the initial words set, the number of words in each subset, the maximum number of changing operations upon a word within one subset define the result of model training and model’s vectorisation rigidity. The optimal values of these parameters should be chosen regarding the language specifics and the particular task. The other important point is keeping the whole training set balanced (none of the two classes should prevail).

The second part of the extended neural network has only one edge which weight could be adjusted during training process; this part of the network applies monotonous function to the embedding vectors difference norm. The training dataset dictates that this second part should output 0 for “similar” word pairs and 1 for “not similar”, so while training the extended model the inner chars2vec model learns to form neighbouring embedding vectors for the “similar” word pairs and distant ones for the “not similar” pairs.

We have trained chars2vec models for English language with embedding dimensions of 50, 100, 150, 200 and 300. The project source code is available in the repo along with the model training and usage examples (we’ve trained the model on our dataset for a new language).

Train your own chars2vec model

The following code snippet shows the way to train your own chars2vec model instance.

A list of characters model_chars that the model would use for words vectorisation should be defined as well as the model’s dimension dim and path to the model storage folder path_to_model. Training set (X_train, y_train) consists of pairs of “similar” and “not similar” words. X_train is a list of word pairs, and y_train is a list of their binary similarity metric scores (0 or 1).

It is important that all the characters from the model_chars list should be present in the set of words of the training dataset — if a character is absent or appears very seldom then unstable model behaviour could be observed once this character is met in the test dataset. The reason is that the corresponding one-hot vector has been rarely fed into the model’s input layer and some weights of the model’s first layer have always been multiplied by zero meaning their tuning has never been performed.

Another advantage of chars2vec model is the ability to solve various NLP problems for an arbitrary language lacking open pertained language models. This model could provide better solutions of some texts classification or clustering problems than classic models if you are processing texts with specific vocabularies.

Benchmarks

We have performed benchmarking on the IMDb dataset for the reviews classification task using various words embeddings. IMDb is an open dataset of movie reviews which could be positive or negative so it is a binary text classification task with 50k reviews as the training set and 50k set for tests.

Along with chars2vec embeddings we have tested several prominent embedding models like GloVe, word2vec by Google (“pre-trained vectors trained on part of Google News dataset (about 100 billion words). The model contains 300-dimensional vectors for 3 million words and phrases”), fastText (wiki-news model with dimension 300, “1 million word vectors trained on Wikipedia 2017, UMBC webbase corpus and statmt.org news dataset (16B tokens)”).

The classifier model looks the following way: each review is vectorised by averaging the embedding vectors of all the words comprising it. If a word is out of the model dictionary, a zero vector is assigned to it. We have used a standart tokenisation procedure along with stop words by NLTK library. The classifier we chose was the linearSVM. The table below shows test accuracies for the most popular models we have benchmarked this way. We should point out that our chars2vec model is about 3 oders lighter than the semantic models relying on large vocabularies and still demonstrates quite reasonable results.

We see some space for chars2vec model improvements needed to compete with the results of the semantic models.

Chars2vec: character-based language model for handling real world texts with spelling errors and… was originally published in HackerNoon.com on Medium, where people are continuing the conversation by highlighting and responding to this story.

This post adresses the general problem of constructing a deep learning based recommender system. The particular architecture discribed in the paper is the one powering the new smart feed of the iki service, pushing your skills on daily basis — to check its performance, please try product beta.

If you feel familiar with the general idea of recommender systems, mainstream approaches and would like to go straight to the details of our solution, please skip first two sections of the paper.

Introduction

Recommender systems have changed the way we interact with lots of services. Instead of providing static data they bring interactive experience, an option to leave your feedback and to personalise the information you are given. A recommender system creates personalised informational flows independently for each user but also takes into account behaviour of all users of a service.

Often it is impossible for a user to choose among the variety of the given options by checking each of them be that movies in an online cinema, consumer goods in an online store or any other content. In case there is lot of content in a service a user faces the problem of informational overload. One of the ways to solve this problem is taking advantage of the targeted recommendations.

One of the examples of a service where targeted content plays crucial role is iki. iki is your personal career and professional consultant powered by machine learning and artificial intelligence related technologies. After a user has defined the areas of his professional interests, iki creates daily content feed developing knowledge and chosen skills with the help of the recommender system with the deep learning architecture described below.

A general description of recommender systems problem setting

The main objects present in any recommender systems are users U, items R and some interactions between them. These interactions are usually presented as a matrix F(|U|x |R|), each cell containing some information about an interaction — the fact that an item has been viewed / bought, the given rating, like / dislike or something else. Depending on the number of users and items in a system the F matrix can become enormously large. But each user normally gives some ratings or interacts only with a small percent of items in the system which results in a very sparse ratings matrix. It is known that one can reduce the number of independent parameters of a sparse model without a significant loss of information. We come to the problem of the right presentation of the rating data in a recommender system: we have to map each user to some vector space by means of a vector with a fixed length n, n<<|U| and each item — to another vector space by means a vector with a fixed length m, m<<|R|. One of the most popular solutions of this problem is SVD (Singular Value Decomposition) of the F matrix which gives us two matrices with shapes |U| x n and n x |R| for a given n with their product being the best approximation of the matrix F. The lines of the first matrix are vectors corresponding to users, the lines of the second one are vectors, corresponding to system’s items; let us call these vectors the “SVD embeddings” of users and items correspondingly.

The traditional method of creating prognosis in recommender systems is collaborative filtering. The main assumption of this method is that users having given similar ratings of some items in the past tend to give similar ratings to other items in the future. One of the most popular methods of solving the collaborative filtering problem is creation of user’s and item’s dense embeddings with the SVD of the initial sparse ratings matrix F. To predict the value of a new rating of user u on item i we have to calculate a scalar product of the corresponding user’s and item’s SVD embeddings.

There are several open libraries providing instruments for construction of various recommender systems based on users ratings matrix. Among others we could name various methods of matrix factorisation (SVD, Non-negative matrix factorization NMF), different variations of nearest neighbours algorithm, co-clustering methods, user based and item based models. The examples of such solutions are Surprise library and LightFM library.

Besides the information about users interactions with items there usually is some other data in a recommender system describing users and items separately. This data could be variative and heterogeneous — items and users could contain some textual descriptions, numerical characteristics, categorical features, images and other types of data. The way of processing and usage of this data depends on the particular problem and is not a universal part of recommender systems.

The main properties or metrics of a recommender system are recommendations relevance and scalability in case of really large numbers of users or items. That setting brings the common recommender system’s architecture consisting of two sequential blocks: candidates generator, choosing a relatively small subset from the large items set, and ranking module, giving a rating of relevance to user’s interests to each item in the chosen subset. This rating is often used to rank items in the order the user will see them.

Deep learning powered recommender system architecture

Content based recommender system with a deep learning architecture is closely related to the actual content present in the system. Futher on we shall dive into details of iki recommender system to describe the DL approach.

In iki user’s interactions with content are views and ratings — a user can like or dislike any content element. An item in our case is a webpage with a blog, an article, a tutorial, a course, or some other content providing professional knowledge. Each content element has textual description or is a text itself.

Content embeddings are the result of text vectorisation procedure. We used GloVe language model with 300 dimensions to vectorise separate words. GloVe is a language model developed at Stanford University, resembling word2vec (preserving semantic similarity of words). The difference is that besides keeping semantics GloVe takes advantage of the statistical approach, taking in account the number of words occurrence in text corpus.

We count tf-idf weights of all the occurring words in the text corpus, then the vectors corresponding to content elements are calculated as a weighted sum of GloVe vectors of words in this content element with tf-idf weights.

A user can add to his profile some information regarding his current and past jobs (such as position name and description of each job). Our system processes this data and extracts a list of professional skills of each user with a special language model Skills Extractor developed for this purpose. In a nutshell the idea of this model is to learn the semantics of “skills” on the corpus of English CVs and to be able to extract previously unseen skills from an unstructured English text. A user can also add some skills manually. To tune the content feed a user has to select some areas of professional interests on our hierarchical cloud of tags similar to Apple Music mechanics. iki offers several hundreds of professional interests to be selected as a part of user’s content feed. User’s skills and selected tags are used in our recommender system as user’s features.

Another set of features used to train our recommender system are content and users embeddings obtained after applying SVD to the user’s ratings matrix. This is not the only usage of the information about ratings and views in the system — we create user’s vector representation describing his viewed and rated content. This is done the following way: having content’s vector representation let us take the minimum, the maximum and the average value of each coordinate on the whole corpus of user’s viewed content. This operation results in three vectors with the same length as the content embeddings. We perform the same operation on the set of liked and disliked content obtaining another 6 vectors with the same length. These dense embeddings are also used as a user’s feature during recommender system training step.

Candidates generation

For each tag (content topic) our recommender system creates a separate set of recommendations and, particularly, selects a subset of candidates for further ranking. The goal of iki recommender system is not only to provide the content on corresponding topic but also to rank content elements by quality and expertise level to fit the resulting feed to each user’s level of expertise.

Let us go deeper into details of the candidates generation step. For each tag our system selects candidates for ranking with the help of the following mechanics: the content elements that recently have received particular user’s positive ratings are selected along with the sets of content elements surrounding these selected ones (we take the union of several neighbourhoods in the content embeddings space) are added to the candidates space. We also take in consideration the set of users with similar recent activity on the selected tag (a cosine distance between ratings and views vectors is calculated for this set of users). The set of content elements recently viewed or rated is also added to the set of candidates. Variation of the described neighbourhoods radius provides different number of generated candidates.

Candidates ranking

For each tag a separate neural network instance is trained and used for content candidates ranking. Each neural net instance is trained and then used for ranking on the content subset corresponding to this tag. The ranking net takes some data about the content element and the user as an input and outputs some number between 1 and -1 as the predicted rating used for the final ranking of the content elements. The model is trained on the set of given ratings and views; each sample of the set is comprised of a user and a content element, the target value is 1 for like, -1 for dislike and 0 if the user just viewed the content without giving it any rating.

The ranking net has 6 inputs with different dimensions. The first input takes information about user’s selected tags and his skills which is transformed in a dense user profile embedding in the next layer. This information allows system to take into account other interests (tags) of the particular user while ranking content corresponding to particular interest. There is a finite number of tags in iki so the information about them is encoded with a fixed length binary encoded vector (1 for selected tags, 0 for the rest).

The skills extracted from user’s CV with SkillsExtractor may be quite variative so we statistically normalise them to eliminate really rare phrases and to end up with a fixed length set. Then we vectorise skills in the same binary way as we have already done with tags. During the periodic recommender system training we update the actual set of skills.

The next two inputs take user’s vector representations we have described before comprised of the rated and viewed averaged content embeddings. Their outputs are united in the next layer which creates dense user’s embedding in the content embeddings space — we call it dense user preference embedding. These two embeddings are united with the other inputs taking SVD embeddings of content and user as well as the content embedding. The obtained vector is passed forward and goes through several dense layers of the neural net. The activation function of the last net’s layer is tanh which gives us an output value in [-1, 1] corridor.

The problem of the cold start in iki is solved the following way: for a particular tag without any ratings the system recommends a new user a set of random content elements with significant distance among each other. This provides a variety of quite different content elements for a new user to choose from at the beginning of his experience.

Results and model’s benchmark

We have tested various recommender system models and combinations (like SVD, NNMF et al.) at the research phase before constructing the final model described above. The model we ended up with obviously shows the best results accuracy on the specific iki dataset. Providing a meaningful benchmark for a deep learning based recommender system is not a trivial task because the ranking net’s architecture is tailored to a specific type of data and it is quite obvious that this specific architecture outperforms any interaction matrix based recommender system just as it takes advantage of more data used to form predicted score.

The other problem is that when you do not have a large enough real user base with all the profile and ratings data, it is hard to simulate the real recommender system performance. You can generate a dataset, but it is no sense in generating a noisy one, so you will tailor some sets of skills and experience and preferences to some users and your recommender system will decode this information and tailor the recommendations to the artificial user profiles you have generated. This approach leaves no room for the real world spontaneous user’s actions processing which really matters.

Recommender systems with deep learning architectures was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.

We want to present our brand new open source library RedBlackPy. Now it is available for Python 3.6+ on MacOS and Linux (Windows in near future).
It is distributed under Apache License 2.0. You can easily install it via pip:

>>> pip install redblackpy

Article structure:

• Highlights. What is RedBlackPy?
• Why red-black trees? Simple explanation of red-black trees balancing.
• Series and SeriesIterator. Features, code examples and benchmarks.

Highlights

RedBlackPy is a Python library with data structures based on red-black trees. In some sense, it can be considered as an additional library for pandas. Pandas containers are aimed at efficient work with static data, i.e. once you load it, you do not add any more elements or delete them because of computational costs. RedBlackPy, on the opposite, was designed for efficient work with dynamic and ordered data, we include benchmarks for core operations. The other important advantage of RedBlackPy is good scalability. The first release is presented by two classes: Series and SeriesIterator. For Cython users we have included pxd definitions files for these classes.

Series is a mapping data structure to keep 1-d data, which:

• Keeps data in order, sorted by keys.
• Provides fast operations to work with dynamic data: insertion, deletion, get item by key, set item by key.
• Provides all basics numeric data types with a specific number of bits (numpy’s dtype analogue): unsigned integers, signed integers,
  floating points. Certainly, you can keep any Python objects in this container.
• Provides convinient user interface to work with time series or scientific evaluations: access by any key using interpolation. Interpolation is built into getitem operator and does not use additional memory. Arithmetic operations as for vectors, data shifting over the index.

SeriesIterator is an iterator-generator for efficient iterating over multiple Series objects. For example, if you’re given a set of Series objects and need to construct an ordered union of keys of these Series then you just need to initialize a SeriesIterator. This iterator does not use additional memory to concatenate keys, it generates next value of the union inplace.

In our team we use these data structures for handling predictive modelling problems and in financial time series analysis tasks.

Why Red-black trees?

Red-black tree is a well-known data structure (for example, C++ STL map and set are based on red-black trees). There is a lot of information about red-black trees so we would not go through all the details here. We’ll just introduce the main ideas of the concept so that the audience not familiar with this structure will get the idea of the self-balancing logic. Here we assume that our reader is familiar with the basics of binary search trees. The statements and proofs in this section are not required to understand the following sections.

Definition 1. Red-black tree is a self-balancing binary search tree which satisfies the following conditions:

1. Each node is either red or black.
2. The root is black.
3. All leaves are black.
4. If a node is red, then both its children are black.
5. Every simple path from the root to any of leaves nodes (NIL on Figure1.) contains the same number of black nodes.

A self-balancing means that insertion and deletion operations include some modifications to keep tree balanced. But what exactly means that a tree is balanced?

Definition 2. A binary search tree is said to be balanced of order 𝑛 if
the difference in lengths of the longest simple path and the shortest simple path (each path goes from the root to leaves) equals 𝑛.

Can we color any binary search tree with respect to conditions of Definition 1? The next proposition gives the answer to this question.

Proposition 1. Let T be a red-black tree. Then T is balanced of order m,
where m ≤ height(T)/2.
Proof. Consider arbitrary simple path 𝜸 of length height(T) in T. Also, consider another simple path 𝜼 from root to arbitrary leave node. According to conditions 2–4 (Definition 1) minimal possible number of black nodes in 𝜸 equals to⎡height(T)/2⎤. At the same time, the maximum possible number of black nodes in path 𝜼 is equal to length(𝜼). According to condition 5 we obtain the required assertion. ◀︎

Now we know that lengths of any two simple paths from the root to leaves nodes in red-black tree differ not more than twice. As the height of a binary search tree defines the complexity of a search operation, the next question appears. What can we say about the height of an arbitrary red-black tree?

Proposition 2. Let T be a red-black tree with n nodes. Then the following holds:
height(T) ≤ 2 log(n +1), where log is binary logarithm.
Proof. By Proposition 1 any simple path from root to leaves in T has length not less than height(T)/2. Therefore n is not less than number of nodes in the first⎡height(T)/2⎤levels (1st level is the root, 2nd is the root children, etc.).
Thus we get obvious lower bound for n and it implies the statement:

◀︎

By Proposition 2 the search operation in red-black trees has logarithmic in size complexity. It turns out that there is an efficient algorithm (logarithmic complexity) to insert or delete a node. This algorithm includes modifications (so called rotations) to keep the tree complying with Definition 1.

Our choice of the core data structure was initially defined by the problems we have faced in quantitative research. We had defined the objectives through the prism of financial series processing, but the resulting solution could be applied to a bunch of other problems in an obvious way. For instance, if you are working with trading market data, you have multiple time series and their keys do not necessarily coincide. But we know that the current stock state (active orders) equals to the state of the last modification (price change). It means that we have to deal with piecewise constant signals and we naturally come to floor interpolation (see Figure 2). From the other side if we are working with an order book, for example, we have a very frequently changing structure and so a fast realization of the insertion and deletion operations is needed. One could briefly define the following objectives:

• Keep data sorted (for interpolation)
• Scalability to process up to millions of items
• Fast modification operations
• Fast items access, fast iterating
• Convenient unconstrained and optimized interpolation methods to construct values inplace. We include several interpolations: floor, ceil, linear, keys only (see docs).
• Convinient iterating over multiple asynchronous time series
• Vector arithmetic operations

Using arrays and hash tables as the core data structures is very expensive in this case because of frequent memory reallocation, rehashing, data shifting when you insert or delete an element. To avoid these effects we have decided to use self-balancing binary trees.

Series and SeriesIterator

Note. In this section we present some benchmarks. All tests have been carried out on a MacBook Pro (Retina, 13-inch, Early 2015) 2,7 GHz Intel Core i5.

Now let us consider some simple use cases and benchmarks for the main operations. We would like to mention that we do not compete with Pandas Series and it would not be correct to compare RedBlackPy Series and Pandas Series in terms of competition because their core data structures are different. By demonstrating benchmark results we’d like to show that the proper choice of a data structure for specific problem is an important step in the R&D process.

Interpolation

Interpolation is built into getitem operator. You can initialize Series with the specific interpolation type, you can also change it after initialization. Interpolation does not create a new item, it uses neighbours to calculate a value inplace (see Figure 2). The code example listed below shows how interpolation works. :

The figure below schematically describes interpolation logic. Assume we’ve got a discrete signal with 5 points. By making a query for a value of some key we obtain different results depending on interpolation type.

SeriesIterator

The SeriesIterator class provides efficient iterating over a sorted union of keys of multiple Series objects. This class is also based on the red-black tree concept. Red-black tree is used as min-heap in case of forward iterator and as max-heap in case of reversed iterator. This heap uses k memory cells, where k is the number of Series objects. The figure below schematically describes the work of SeriesIterator.

Now let us create ten Series objects with random data and evaluate the execution time of an iteration loop. In the code snippet below we create SeriesIterator from the list of Series, each Series object contains 100 000 items. After initialization we are iterating over the sorted union of keys of these Series objects forward and backward.

For ten Series objects each containing 100 000 elements, forward and reverse loops took 0.95 seconds and 0.92 seconds respectively. This time has been obtained on MacBook Pro (Retina, 13-inch, Early 2015).

Core operations benchmarks

We shall provide test results for some simple code snippets to show the main difference between two data structures, specifically between Pandas.Series and RedBlackPy.Series.

Each function is tested on containers of the following sizes: 10³, 10⁴, 10⁵, 10⁶.
To plot the results we have used logarithmic scale of the time axis.

As we can see in the results below RedBlackPy outperforms Pandas in insertion, deletion and search (get item) operations. For instance, iterating over a list of one million keys and calling getitem operator took 11.8 seconds for Pandas.Series and 2.7 seconds for RedBlackPy.Series in case of random list of keys. But Pandas outperforms RedBlackPy in iterating over Series because of continuous memory allocation. For the same reasons arithmetic operators work in RedBlackPy slower than in Pandas. Modern processors support vector instructions (SSE, AVX) and usage of aligned and continuous allocated memory provides optimisation of arithmetic operators for vectors.

In case you are iterating over a sorted list of keys and calling getitem operator it makes sense to use so called ‘itermode’ of RedBlackPy Series. For a Series with million items execution of the code snippet below took 0.5 seconds. Just call one method and get a good speedup (in this case about 20 times faster than Pandas).

Here is the open source RedBlackPy repository. We shall be grateful for any feedback on the project. Thank you!

This is the first one of the series of technical posts related to our work on iki project, covering some applied cases of Machine Learning and Deep Learning techniques usage for solving various Natural Language Processing and Understanding problems.

In this post we shall tackle the problem of extracting some particular information form an unstructured text. We needed to extract our users’ skills from their Curriculam Vitaes (CVs) even if they are written in an arbitrary way such as “was deploying quantitative trading algorithms on production server”.

This post has a demo page, check our model’s performance on your CV.

Linguistic models

Modern linguistic models (ULMfit, ELMo) use unsupervised learning techniques such as creating RNNs embeddings on large texts corpora to gain some primal “knowledge” of the language structures before a more specific supervised training step. In some cases on the contrary you need a model trained on a very specific and small dataset. These models possess nearly zero knowledge of the general linguistic structures and work only with special text features. A classic example would be a naive sentiment analysis tool for movie reviews or news datasets — the simplest working model could operate only with “good” or “bad” adjectives synonyms and some emphasising words presence. In our research we took advantages of both approaches.

Generally when some corpus of texts is analysed we are looking at the whole vocabulary of each text. Popular methods of texts vectorisation, such as tfidf, word2vec or GloVe models are using the whole document’s vocabulary to create its vector except of stopwords (such as articles, pronouns, and other quite generic language elements bringing little semantic sense in such a statistical averaging procedure). If there is a more specific task and you have some additional information about the texts corpus, you could probably state that some information is more valuable than the other. For example, to perform some analysis on a corpus of cooking recipes it would be important to extract ingredients or dish names classes from the texts. The other example is extracting professional skills from the CVs’ corpus. If we could vectorise each CV by relating it with a vector of extracted skills it would let us perform much more successful industry positions clustering, for example.

Example:

CV: Data scientist, hands on expertise in machine learning, big data, development, statistics and analytics. With my team of data scientists implemented Python machine learning model ensembles, stacking, and feature engineering demonstrating high accuracy rates in predictive analytics. Created a recommender system using Doc2Vec words embeddings and neural networks.

Extracted professional skills: machine learning, big data, development, statistics, analytics, Python machine learning model ensembles, stacking, feature engineering, predictive analytics, Doc2Vec, words embeddings, neural networks.

Step 1: Parts of speech tagging

The task of entities extraction is a part of text mining class problems — extracting some structured information from an unstructured text. Let us take a close look at the suggested entities extraction methodology. As far as skills are mainly present in so-called noun phrases the first step in our extraction process would be entity recognition performed by NLTK library built-in methods (checkout Extracting Information from Text, NLTK book, part 7). Part of speech tagging method extracts noun phrases (NP) and builds trees representing relationships between noun phrases and the other parts of the sentence. NLTK library has a number of tools performing such phrase decomposition.

We can define a model as a regular expression giving the sentence decomposition (for example, we can define a phrase as a number of adjectives plus a noun) or we can teach a model on a labeled number of texts from NLTK with extracted noun phrases examples in them. This step results in receiving a number of entities among which some are the target skills and some are not — besides skills CV could contain some other entities such as places, persons, objects, organisations, whatever.

Step 2: Deep learning architecture for candidates classification

The next step is entities classification. Here the objective is quite simple — to tell skills from “not skills”. The set of features used for training is composed regarding the structure of the candidate phrase and the context. Obviously, to train a model we had to create a labeled training set, we did it manually for 1500 extracted entities with skills and “not skills” among them.

We have never tried to fit our model to some finite set of hardcoded skills, the core idea behind the model was to learn semantics of skills in English CVs and to use the model for extraction of the unseen skills.

Each word’s vector is comprised of such binary features as occurrence of numbers or other special characters (skills often contain numbers and symbols: C#, Python3), capitalisation of the first letter or of the whole word (SQL). We also check if a word appears in the English language vocabulary and in some thematic lists such as names, geographical names, etc. The final model using listed features has shown 74.4% correct results on the test set of entities. Usage of another binary feature describing presence of the popular English prefixes and suffixes in a candidate improved model’s performance up to 77.3% correct results on test set. And the addition of one-hot vectors encoding parts of speech to the models’ features set boosted our results to 84.6%.

A reliable semantic words embedding model could not be trained on a CV dataset, it is too small and narrow, to mitigate the problem you should use words embeddings trained on some other, really large dataset. We used GloVe model vectors with 50 dimensions which improved our models’ performance up to 89.1% correct results on a test set. You can play with the final model in our demo by uploading a text from your CV.

Popular part of speech taggers (NLTK POS tagger, Stanford POS tagger) often make mistakes in the CV’s phrases tagging task. The reason is that often a CV text neglects grammar in order to highlight experience and to give it some structure (people start sentences with a predicate, not with a subject, sometimes phrases miss appropriate grammatical structure), a lot of words are specific terms or names. We had to write our own POS tagger solving the aforementioned problems.

The classification is performed with a Keras neural network with three input layers each designed to take special class of data. The first input layer takes a variable length vector comprised of the described above features of the candidate phrases which could have arbitrary number of words. This feature vector is processed with an LSTM layer.

The second variable length vector brings the context structure information. For the given window size n we take n neighbouring words to the right and n words to the left of our candidate phrase, vector representations of these words are concatenated into the variable length vector and passed to the LSTM layer. We found that the optimal n=3.

The third input layer has fixed length and processes the vector with the general information about the candidate phrase and its context — coordinatewise maximum and minimum values of word vectors in the phrase and its context which, among the other information, represent the presence or absence of many binary features in the whole phrase.

We called this architecture SkillsExtractor, here it is.

It’s Keras implementation looks the following way:

The best result in model training has been achieved with the Adam optimiser with learning rate decreased to 0.0001. We chose binary_crossentropy as the loss function because the model is designed to classify in two classes.

To make its’ usage handy, let us add fit method performing neural net’s training and automatic stopping with the usage of cross validation and predict function, forming the prognosis for the feature vector of the candidate phrase.

pad_sequences function converts a list of feature sequences to a 2d array with width equal to the longest sequence in the list. This is made to bring variable length data going to the LSTM layers to the format needed for model training.

onehot_transformfunction converts the target values 0 and 1 to one-hot vectors [1,0] and [0,1]

As long as the numbers of words in an entity and in its context are arbitrary, the usage of a sparse fixed length vector does not look reasonable. Thus the recurrent neural nets processing vectors of the arbitrary lengths here come as a handy and quite natural solution. Our tests proved that the architecture using dense layers to deal with fixed length vectors and LSTM layers for handling varied length vectors is optimal.

Several architectures have been tested with different combinations of dense layers with LSTM ones. The resulting architecture configuration (the size and number of the layers) showed the best results on cross-validation test which corresponds to the optimal usage of training data. Further model tuning could be performed by increasing the training data set size along with scaling the layers size and number appropriately, doing latter with the same dataset would lead to model overfitting.

Results

All the CVs used for model training were from the IT industry. We were delighted to see that our model also showed quite reasonable performance on the dataset of CVs belonging to other industries such as Design and Finance. Obviously processing CVs with entirely different structure and style would result in a lower model performance. We would also like to mention that our understanding of the “skills” concept could vary from someone elses’. One of the hard cases for our model would be telling skills from new companies names as skills are often equal to software frameworks and sometimes you cannot tell wether this is a startup name mentioned or a new JS framework or a Python library. Nevertheless in most cases our model could be a useful tool for automatic CV analysis and along with some statistical methods could solve wide range of data science tasks on an arbitrary CV corpus.

Deep learning for specific information extraction from unstructured texts was originally published in TDS Archive on Medium, where people are continuing the conversation by highlighting and responding to this story.