Machine learning in 10 pictures

I find myself coming back to the same few pictures when explaining basic machine learning concepts. Below is a list I find most illuminating.

Why lower training error is not always a good thing: ESL Figure 2.11. Test and training error as a function of model complexity.

Examples of under and overfitting. PRML Figure 1.4. Plots of polynomials having various orders M, shown as red curves, fitted to the data set generated by the green curve.

ITILA Figure 28.3. Why Bayesian inference embodies Occam’s razor. This figure gives the basic intuition for why complex models can turn out to be less probable. The horizontal axis represents the space of possible data sets D. Bayes’ theorem rewards models in proportion to how much they predicted the data that occurred. These predictions are quantified by a normalized probability distribution on D. This probability of the data given model Hi, P (D | Hi), is called the evidence for Hi. A simple model H1 makes only a limited range of predictions, shown by P(D|H1); a more powerful model H2, that has, for example, more free parameters than H1, is able to predict a greater variety of data sets. This means, however, that H2 does not predict the data sets in region C1 as strongly as H1. Suppose that equal prior probabilities have been assigned to the two models. Then, if the data set falls in region C1, the less powerful model H1 will be the more probable model.

(1) Why collectively relevant features may look individually irrelevant, and also (2) Why linear methods may fail. From Isabelle Guyon's feature extraction slides.

Why irrelevant features hurt kNN, clustering, and other similarity based methods. The figure on the left shows two classes well separated on the vertical axis. The figure on the right adds an irrelevant horizontal axis which destroys the grouping and makes many points nearest neighbors of the opposite class.

How non-linear basis functions turn a low dimensional classification problem without a linear boundary into a high dimensional problem with a linear boundary. From SVM tutorial slides by Andrew Moore: a one dimensional non-linear classification problem with input x is turned into a 2-D problem z=(x, x^2) that is linearly separable.

Why discriminative learning may be easier than generative: PRML Figure 1.27. Example of the class-conditional densities for two classes having a single input variable x (left plot) together with the corresponding posterior probabilities (right plot). Note that the left-hand mode of the class-conditional density p(x|C1), shown in blue on the left plot, has no effect on the posterior probabilities. The vertical green line in the right plot shows the decision boundary in x that gives the minimum misclassification rate.

Learning algorithms can be viewed as optimizing different loss functions: PRML Figure 7.5. Plot of the ‘hinge’ error function used in support vector machines, shown in blue, along with the error function for logistic regression, rescaled by a factor of 1/ln(2) so that it passes through the point (0, 1), shown in red. Also shown are the misclassification error in black and the squared error in green.

ESL Figure 3.2. The N-dimensional geometry of least squares regression with two predictors. The outcome vector y is orthogonally projected onto the hyperplane spanned by the input vectors x1 and x2. The projection yˆ represents the vector of the least squares predictions.

Why Lasso (L1 regularization or Laplacian prior) gives sparse solutions (i.e. weight vectors with more zeros): ESL Figure 3.11. Estimation picture for the lasso (left) and ridge regression (right). Shown are contours of the error and constraint functions. The solid blue areas are the constraint regions |β1| + |β2| ≤ t and β1² + β2² ≤ t2, respectively, while the red ellipses are the contours of the least squares error function.
Full post...

Mehmet Ali Yatbaz, Ph.D. 2014

Current position: Software Engineer, Facebook, London. (Linkedin, Publications).
PhD Thesis: Linguistic Category Induction and Tagging Using the Paradigmatic Context Representations with Substitute Words. Koç University Department of Computer Engineering, February 2014. (PDF, Presentation, Keynote)
M.S. Thesis: Stretch: A Feature Weighting Method for The k Nearest Neighbor Algorithms. Koç University Department of Computer Engineering, October 2007. (PDF, Presentation).

Linguistic Category Induction and Tagging Using the Paradigmatic Context Representations with Substitute Words

This thesis introduces a new paradigmatic representation of word contexts. Paradigmatic representations of word context are constructed from the potential substitutes of a word, in contrast to syntagmatic representations, which are constructed from the properties of neighboring words. The potential substitutes are calculated by using a statistical language model that is trained on raw text without any annotation or supervision. Thus, each context is represented as a distribution of substitute words. This thesis introduces models with different properties that can incorporate the new paradigmatic representation, and discusses the applications of these models to the tagging task in natural language processing (NLP).

In a standard NLP tagging task, the goal is to build a model in which the input is a sequence of observed words, and the output, depending on the level of supervision, is a sequence of cluster-ids or predefined tags. We define 5 different models with different properties and supervision requirements. The first model ignores the identity of the word, and clusters the substitute distributions without requiring supervision at any level. The second model represents the co-occurrences of words with their substitute words, and thus incorporates the word identity and context information at the same time. To construct the co-occurrence representation, this model discretizes the substitute distribution. The third model uses probabilistic voting to estimate the distribution of tags in a given context. Unlike the first and second models, this model requires the availability of a word-tag dictionary which can provide all possible tags of each given word. The fourth model proposes two extensions to the standard HMM-based tagging models in which both the word identity and the dependence between consecutive tags are taken into consideration. The last one introduces a generative probabilistic model, the noisy channel model, for the taggin tasks in which the word-tag frequencies are available. In this model, each context C is modeled as a distinct channel through which the speaker intends to transmit a particular tag T using a possibly ambiguous word W. To reconstruct the intended message (T), the hearer uses the distribution of possible tags in the given context Pr(TjC) and the possible words that can express each tag Pr(WjT).

The models are applied and analyzed on NLP tagging tasks with different characteristics. The first two models are tested on unsupervised part-of-speech (POS) induction in which the objective is to cluster syntactically similar words into the same group. The probabilistic voting model is tested on the morphological disambiguation of Turkish, with the objective of disambiguating the correct morphological parse of a word, given the available parses. The HMM-based model is applied to the part-of-speech tagging of English, with the objective of determining the correct POS tag of a word, given the available tags. Finally, the last model is tested on the word-sense disambiguation of English, with the objective of determining the correct sense of a word, given the word-sense frequencies.

Full post... Related link

Turkish Language Resources

This post contains links to various Turkish language resources that I have collected. Please send a comment if you find Turkish resources that you would like to see on this page.

ITU Turkish Natural Language Processing Pipeline

This webpage provides the Turkish NLP Tools and API developed in Istanbul Technical University by our Natural Language Processing group led by Asst. Prof. Dr. Gülşen Eryiğit including a Tokenizer, Normalization tools, Deasciifier, Vocalizer, Spelling Corrector, Turkish word detector, Morphological Analyzer, Morphological Disambiguator, Named Entity Recognizer, and Dependency Parser.

TS Corpus

Taner Sezer's TS Corpus is a 491M token general purpose Turkish corpus. See comments below for details.

BounWebCorpus

Hasim Sak's page contains some useful Turkish language resources and code in addition to a large web corpus.

Bibliography

Özgür Yılmazel's Bibliography on Turkish Information Retrieval and Natural Language Processing.

tr-disamb.tgz

Turkish morphological disambiguator code. Slow but 96% accurate. See Learning morphological disambiguation rules for Turkish for the theory.

correctparses_03.txt.gz, train.merge.gz

Turkish morphology training files. Semi-automatically tagged, has limited accuracy. Two files have the same data except the second file also includes the ambiguous parses (the first parse on each line is correct).

test.1.2.dis.gz, test.merge.gz

Turkish morphology test files, second one includes ambiguous parses (the first parse on each line is correct). The data is hand tagged, it has good accuracy.

tr-tagger.tgz

Turkish morphological tagger, includes Oflazer's finite state machines for Turkish. From Kemal Oflazer. Please use with permission. Requires the publically available Xerox Finite State software.

turklex.tgz, pc_kimmo.tgz

Turkish morphology rules for PC-Kimmo by Kemal Oflazer. Older implementation. Originally from www.cs.cmu.edu

Milliyet1.bz2, Milliyet2.bz2, Milliyet3.bz2

Original Milliyet corpus, one token per line, 19,627,500 total tokens. Latin-5 encoded, in three 11MB parts. From Kemal Oflazer. Please use with permission.

Turkish wordnet

From Kemal Oflazer. Please use with permission.

METU-Sabanci Turkish Treebank

Turkish treebank with dependency annotations. Please use with permission.

sozluk.txt.gz

English-Turkish dictionary (127157 entries, 826K) Originally from www.fen.bilkent.edu.tr/~aykutlu.

sozluk-boun.txt.gz

Turkish word list (25822 words, 73K) Originally from www.cmpe.boun.edu.tr/courses/cmpe230

Avrupa Birliği Temel Terimler Sözlüğü

(Originally from: www.abgs.gov.tr/ab_dosyalar, Oct 6, 2006)

BilisimSozlugu.zip

Bilişim Sözlüğü by Bülent Sankur (Originally from: www.bilisimsozlugu.com, Oct 9, 2006)

turkish.el

Emacs extension that automatically adds accents to Turkish words while typing on an English keyboard.

en-tr.zip, lm.tr.gz

Turkish English parallel text from Kemal Oflazer, Statistical Machine Translation into a Morphologically Complex Language, Invited Paper, In Proceedings of CICLING 2008 -- Conference on Intelligent Text Processing and Computational Linguistics, Haifa, Israel, February 2008 (lowercased and converted to utf8). The Turkish part of the dataset is "selectively split", i.e. some suffixes are separated from their stems, some are not. lm.tr.gz is the Turkish text used to develop the language model.

Full post...

dlib: Deniz's C Library

(Download the latest version from Github)

Abstract: The main design goal of dlib is to make C programming as practical and concise as Perl, and yet to retain its fine grained control over memory use. For years I have been starting my research projects in Perl, because I can get results quickly. Then at some point I rewrite everything in C, because I run out of memory (I usually work with large statistical models). The tiny memory overheads for each string, array, hash, or object add up when you have billions of them. Yet, I cringe at the prospect of expressing the same ideas in C using many more lines of code than Perl. Why should that be the case?

Contents

• Introduction
• Compilation
• File input
• Tokenization
• Dynamic arrays
• Hash tables

Introduction

The main design goal of dlib is to make C programming as practical and concise as Perl, and yet to retain its fine grained control over memory use. For years I have been starting my research projects in Perl, because I can get results quickly. Then at some point I rewrite everything in C, because I run out of memory (I usually work with large statistical models). The tiny memory overheads for each string, array, hash, or object add up when you have billions of them. Yet, I cringe at the prospect of expressing the same ideas in C using many more lines of code than Perl. Why should that be the case?

As a motivational example, let's say we want to "count the number of times each word appears in a file". It takes 11 words to express this program in English (7 if you don't count the function words). Perl is just as concise (7 tokens excluding punctuation):

while(<>) {
  for (split) {
    $cnt{$_}++;
  }
}

Imagine what a nightmare this tiny program is in standard C (or especially Java). The main feature that distinguishes Perl among high level languages and enables a Perl programmer to write concise code is that it provides reasonable defaults for everything, so that things you express most often can be written concisely (human languages and compression algorithms use the same trick). And of course as with every modern language these days Perl has built in dynamic arrays, hashes, and regexps and makes them practical to use with its concise syntax. This is my feeble, incomplete, and evolving attempt to import some of these ideas into C. Among other things, dlib introduces some iteration constructs for file I/O and string tokenization and built-in hashes to make programs of this sort almost as concise:

forline (str, NULL) {
  fortok (tok, str) {
    cnt(tok)++;
  }
}

Compilation

To compile your C code with dlib, #include "dlib.h" at the beginning of your files and add dlib.c to the files to be compiled. My typical gcc options are:

-O3 -D_GNU_SOURCE -std=c99 -pedantic -Wall

I tried to stick with the C99 standard but used some extensions that can be turned off. Use the -D_GNU_SOURCE compiler flag if you want to compile with these extensions without warnings. Define the following flags with -D compiler options if you don't have, or don't want these extensions:

_NO_POPEN   Do not use pipes in File I/O.
_NO_GETLINE Do not use GNU getline.
_NO_PROC    Do not use the proc filesystem for memory reporting.
_NO_MUSABLE Do not use GNU malloc_usable_size for memory reporting.
NDEBUG      Turn off debug output and assert checks (from assert.h).

File input

forline(s, f), is an iteration construct which executes the statements in its body with the undeclared string variable s set to each line in file f. All the file handle creation, opening and closing, allocating and freeing of string buffers etc. are taken care of behind the scenes. The following example prints the length of each line in "file.txt":

forline (str, "file.txt") {
  printf("%d\n", strlen(str));
}

There are some special f arguments:

• If f==NULL, stdin is read.
• If pipes are available, and f starts with <, as in f=="< cmd args", the cmd is run with args and its stdout is read.
• If pipes are available, compressed files with .gz, .xz, and .bz2 extensions are automatically handled.
• Otherwise a regular file with path f is read.
  

Tokenization

fortok(t, s) is an iteration construct which executes the statements in its body with the undeclared string variable t set to each whitespace separated token in string s. Empty tokens are skipped. It modifies and tokenizes s the same way strtok does, but unlike strtok it is reentry safe (i.e. multiple nested fortok loops are ok). fortok3(t, s, d) takes an additional character array d to specify delimiter characters any one of which will act as a delimiter. fortok(t, s) is equivalent to fortok3(t, s, " \f\n\r\t\v"). Examples:

char *str = strdup("  To be    or not");
// need strdup because fortok won't work with constant strings
fortok (tok, str) {
  printf("[%s]", tok); // prints "[To][be][or][not]"
}

char *pwd = strdup(":root::/root:/bin/bash:");
fortok3 (tok, pwd, ":/") {
  printf("[%s]", tok); // prints "[root][root][bin][bash]"
}

split(char *str, const char *delim, char **argv, size_t argv_len) returns the tokens of a string in an array. This is useful because one often needs to refer to the n'th token in a string rather than iterating over them. split splits the str into tokens delimited by single characters from delim (including empty tokens) and sets the pointers in the argv array to successive tokens. argv should have enough space to hold argv_len pointers. Split stops when argv_len tokens are reached or str runs out. It modifies str by replacing delimiter characters with '\0'. Returns the number of tokens placed in argv. Example:

char *pwd = strdup(":root::/root:/bin/bash:");
char **toks = malloc(10 * sizeof(char *));
int n = split(pwd, ":/", toks, 10);
for (int i = 0; i < n; i++) {
  printf("[%s]", toks[i]); // prints "[][root][][][root][][bin][bash][]"
}

Note the difference in delimiter handling between split and fortok. fortok and fortok3 follow strtok and see multiple delimiter characters in a row as a single delimiter, whereas split, following strsep, will perceive empty fields. fortok is intended for free text, split for structured data.

NOTES: Neither split nor fortok can handle a multi-character delimiter like "::". Not sure if using different delimiter handling strategies in the two will be confusing for the user. Probably need something like chop or trim eventually.

Dynamic arrays

darr_t (pronounced "dar-ty") is a general purpose dynamic array type in dlib.

• darr_t darr(size_t n, type t) returns a new array that has an initial capacity of at least n and element type t. n==0 is ok. The elements are not initialized.
• void darr_free(darr_t a) frees the space allocated for a.
• size_t len(darr_t a) gives the number of elements in a. A new array has len(a) == 0.
• size_t cap(darr_t a) gives the current capacity of a. It will grow as needed, up to a maximum of (1<<58) elements.

A regular C array reference, such as a[i], can be used as an l-value (a[i] = 10), an r-value (x = a[i]), or both (a[i]++). I think this type of access makes the code more readable and I wanted the same flexibility with darr_t. So instead of the usual set, get, add etc. functions we have a single macro val(darr_t a, size_t i, type t) which gives a reference to the i'th element of a that can be used as an l-value or an r-value. All of the following are valid expressions and do what they look like they are supposed to:

darr_t a = darr(0, int);  // initialize array
val(a, i, int) = 10;      // set an element
int x = val(a, i, int);   // get an element
val(a, i, int)++;         // increment an element
int *p = &val(a, i, int); // get a pointer to an element
val(a, len(a), int) = 5;  // add a new element, increments len(a)

The user can request or set any index of a darr_t from 0 to (1<<58-1). The darr_t will never complain and resize itself to permit the access (if memory allows). len(a) will be one plus the largest index accessed (read or write). Some may think this gives too much power to the user to shoot themselves in the foot. A read access to a never initialized element will return a random value. An accidental read or write to a very large index may blow up the memory. Oh well, don't do it.

Hash tables

Hash tables are implemented as dynamic arrays (darr_t) with some search logic. You can initialize and free a hash table using darr and darr_free exactly like you do with dynamic arrays. The macro D_HASH defines an inline function xget (the prefix x is user specified) that searches the array for an element matching a given key and returns a pointer to it:

etype *xget(darr_t htable, ktype key, bool insert);

The etype and ktype are user specified types for array elements and their keys respectively. The boolean argument insert determines what happens when a matching element cannot be found. If insert == true one will be created (in a user specified manner) and added to the array and xget will return its pointer. If insert == false, xget will return NULL.

forhash(etype, eptr, htable, isnull)

is an iteration construct for hash tables which executes the statements in its body with etype *eptr bound to each element of darr_t htable for which the macro or function isnull returns false.

In order to define the xget function, the macro D_HASH takes the following nine arguments (I am open to suggestions to reduce this number). The last six can be macros (preferrable) or functions.

• prefix: The prefix added to get to allow multiple hash table types (e.g. x for xget).
• etype: Type of array element.
• ktype: Type of key.
• keyof: ktype keyof(etype e) returns the key for element e.
• kmatch: bool kmatch(ktype a, ktype b) returns true if two keys match.
• khash: size_t khash(ktype k) is a hash function for keys.
• einit: etype einit(ktype k) returns a new element with key matching k.
• isnull: bool isnull(etype e) returns true if array element e is empty.
• mknull: void mknull(etype e) modifies array element e to become empty.

NOTE: This horribly convoluted interface is necessary to have a general enough implementation that can support sets (where the key and the element are one and the same) and maps (where the key is a function of the element); element types that are primitive (uint32_t, char*) or compound (structs, bit-fields), keys that can be components of compound elements (e.key) or arbitrary functions of primitive ones (e & mask), arrays that store the elements themselves or their pointers etc. It is not intended for daily use. Think of it as your hash table code generator. Once you correctly generate the code for the few hash table types you use, you will hopefully never need D_HASH again.

Here is an example hash table for counting strings:

#include <stdio.h>
#include "dlib.h"

typedef struct strcnt_s { char *key; size_t cnt; } strcnt_t;
#define keyof(e) ((e).key)
extern size_t fnv1a(const char *k);  // string hash fn defined in dlib
#define strmatch(a,b) (!strcmp((a),(b)))
#define newcnt(k) ((strcnt_t) { strdup(k), 0 })
#define keyisnull(e) ((e).key == NULL)
#define keymknull(e) ((e).key = NULL)

D_HASH(s, strcnt_t, char *, keyof, strmatch, fnv1a, newcnt, keyisnull, keymknull)

Given the function sget defined by D_HASH above, we can now write our word counting example from the introduction.

#define cnt(k) sget(htable, (k), true)->cnt

int main() {
  darr_t htable = darr(0, strcnt_t);
  forline (str, NULL) {
    fortok (tok, str) {
      cnt(tok)++;
    }
  }

And print the counts:

  forhash (strcnt_t, e, htable, keyisnull) {
    printf("%s\t%lu\n", e->key, e->cnt);
  }
}

Full post...

Smoothing a Tera-word Language Model

Deniz Yuret. In The 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-08: HLT) (Download PDF, code)
Update of Jan 14, 2014: The latest version gets rid of all glib dependencies (glib is broken, it blows up your code without warning if your arrays or hashes get too big). The glookup program reads ngram patterns with wildcards from stdin and prints their counts from the Web1T Google ngram data. The glookup.pl script quickly searches for a given pattern in uncompressed Google Web1T data. Use the C version for bulk processing, the perl version to get a few counts quickly. The model.pl script optimizes and tests various language models. See the README in the code repository for details. Typical usage:
$ model.pl -patterns < text > patterns
$ glookup -p web1t_path < patterns > counts
$ model.pl -counts counts < text



Abstract: Frequency counts from very large corpora, such as the Web 1T dataset, have recently become available for language modeling. Omission of low frequency n-gram counts is a practical necessity for datasets of this size. Naive implementations of standard smoothing methods do not realize the full potential of such large datasets with missing counts. In this paper I present a new smoothing algorithm that combines the Dirichlet prior form of (Mackay and Peto, 1995) with the modified back-off estimates of (Kneser and Ney, 1995) that leads to a 31% perplexity reduction on the Brown corpus compared to a baseline implementation of Kneser-Ney discounting.

Full post... Related link