Random Intersection Trees

Found an interesting paper with a new idea on how to build interpretable decision rules. The paper
describes an algorithm to find a set of binary features that are together indicative of a class. For example, a set of binary features might be:

• Humidity = high: true / false
• Temperature > 10 C: true / false
• Sunny = true / false
• Rain = true false

A feature is said to be active whenever the result evaluates to true. For two classes C1 and C2, the goal is to find a subset of active features S  such that P(S|C1) > O2 and P(S|C2) < O1 for two thresholds 0 < O1 < O2 < 1. 

For example, let the class be good weather and bad weather. Furthermore, I specified the thresholds

as O1 = 0.5 and O2 = 0.25. A good result might then be 

• P(S = {temperature > 10, sunny} | good weather)  > .5
• P(S = {temperature > 10, sunny} | bad weather)    < .25

Such a result would be indeed interpretable and we could agree with the results that a higher temperature and sun would result in higher probabilities for good weather.

The algorithm works in two steps: 

1. Candidate generation for subsets S.
2. Check subsets for constraint: P(S|C1) > O2 and P(S|C2) < O1 

The main algorithm in the paper is an efficient candidate generation algorithm.

The main idea is to organise the subset search into a random tree of fixed depth and breadth.

At every node in the tree we pick a random example from the dataset with a positive label and then

compute the intersection of that example with the active feature set of the parent node.

By intersecting with positive examples only, the set of features gets more and more refined at each level. All remaining sets at the specified depth are candidates. Afterwards, we only have to check gif the subset holds to the constraints. 

A very interesting method to find rules in a dataset which is an interesting alternative to decision tree learning and apriori rule discovery.

Social Network Sampling

I will start working for a social network in August. My new job is data scientist at the business network Xing. I decided to play with their open API a little. The Xing API gives access to users in the network as well as their contact list. So an external app can analyze the social graph. Well actually there are restrictions on the number of queries so it is possible to
analyze the graph partly. My goal is to extract an unbiased sample from the complete graph by performing a random walk from a start node. That means at every node the algorithm expands all
the node's successors and then picks a random one. The chosen successor is the next node. With
a probability of 0.15 the algorithm returns to the start node. This will ensure that we explore the graph around the start node. The going back is ensuring a trade off between breadth of the exploration and the depth of the exploration. I use the ruby version of the API.
A code snippet for a random walk step in the Xing API
is shown below:

##
# Random walk step: 
#   1) With probability 0.15 go back to start
#   2) Randomly choose a node from the successors
def random_walk_step(user_id, start)
  reset = false
  if Random.rand < 0.15
    user_id = start    
    reset = true
  end
  num_contacts = 5 # control branching
  contacts     = XingApi::Contact.list(user_id, limit: num_contacts)[:contacts][:users]
  next_user    = Random.rand(num_contacts)    
  contacts.map! {|x| x[:id]}
  if reset
    return random_walk_step(contacts[next_user], start)
  end
  return [contacts[next_user], contacts, user_id]
end

The random step function takes a user id as the current node and a node we started the random walk at. First we decide if we restart the search at the start node, then it samples a neighbor. Repeating the process and updating the user id with the sampled neighbor results in a graph. The function below, explores the graph for 25 nodes and returns the graph as a dot file:

##
# Print graph as graphviz file
def dot(path)
  expended = []
  File.open(path, 'w') do |file|
    file.write "digraph my_neighbors {\n"
    start_id = XingApi::User.me[:users].first[:id]
    ids = random_walk_step(start_id, start_id)  
    45.times do
      id = ids[2]
      username = XingApi::User.find(id)[:users].first[:display_name]
      username.gsub! /\W/, ""      
      if not expended.include? username
        expended = expended + [username]
        ids[1].each do |neighbor| 
          neighborname = XingApi::User.find(neighbor)[:users].first[:display_name]
          neighborname.gsub! /\W/, ""       
          file.write "#{username} -> #{neighborname};\n"        
        end
      end
      ids = random_walk_step(ids[0], start_id)      
    end
    file.write "}"
  end
end

A dot file is a graph description that can be converted into graph images. A sample graph of my network is shown below.

Integrating Weka's UI into your own code

Weka is a machine learning toolkit written in Java. Despite it's capability to run as a stand alone

user interface, you can also use Weka in your own Java code. That means, all algorithms you can find in the user interface are also trainable and usable in your Java application. The cool thing is, you can also integrate part of Weka's user interface into your own. So my goal was to integrate the option to choose a Weka classifier and configure it using Weka's native components.

Choosing and configuring a Weka classifier, here a Support Vector Machine.

After browsing a little through the Weka UI code I found two classes that can be used to

open the editor to choose a classifier and to configure it. Once the window closes, the classifier

with it's configuration is ready to be used by other functions. The first UI component is the GenericObjectEditor, which is responsible for choosing a classifier. The second is the PropertyDialog which is configuring the current classifier. Blow I showed some code that displays the dialog and prints out the classifier. I found the example in the Weka GenericObjectEditor class at the bottom. For the code to work you have to make sure the weka.jar is in your CLASSPATH.

package wekaui;

import java.awt.Frame;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.beans.PropertyEditor;
import weka.classifiers.Classifier;
import weka.classifiers.rules.ZeroR;
import weka.gui.GenericObjectEditor;
import weka.gui.PropertyDialog;

/**
 * Choose a classifier and configure it in your own java code.
 *
 * @author Daniel Kohlsdorf
 */
public class WekaUI {

    public static void main(String[] args) {
        Object initial = new ZeroR();
        GenericObjectEditor.registerEditors();
        GenericObjectEditor editor = new GenericObjectEditor(true);
        ce.setClassType(weka.classifiers.Classifier.class);
        ce.setValue(initial);

        // Setup the property view
        PropertyDialog propertyDialog = new PropertyDialog((Frame) null, editor, 100, 100);

        // Get the classifier when the window is closed
        pd.addWindowListener(new WindowAdapter() {
            @Override
            public void windowDeactivated(WindowEvent e) {
                PropertyEditor propertyEditor = ((PropertyDialog) e.getSource()).getEditor();
                if (propertyEditor.getValue() != null) {
                    Classifier classifier = (Classifier) propertyEditor.getValue();
                    System.out.println("CLASSIFIER: " + classifier);
                }
            }
        });
        propertyDialog.setVisible(true);
    }

}

K-Means works just fine

It is interesting how powerful vector quantization can be. Since I like the quantization idea a lot, I think the following insight from a 2011 paper was notable: K-Means outperforms single layer neural nets for self taught learning. The task is to learn features of an image from small patches extracted in a sliding window. Features are extracted over these patches by:

1) Learning an auto encoder over these patches
    We learn a neural net with the input layer
     connected to a smaller hidden layer that connects
     to an output layer. The input and output are the same
     so we try to reconstruct the input using feature detectors
     in the hidden layer.

2) Learning a restricted Boltzmann machine
    Probabilistic version  using a Markov random field of the above method.
    No output layer is needed since the model is undirected. Learning can be
    performed using Gibbs sampling.

3) K-Means:Vector quantization. Features are soft assignments to cluster centers.

4) Gaussian Mixtures: Fitting a gaussian mixture using Expectation Maximization. The features are
     the posterior.

These features are used for classification using a Support Vector Machine. Interestingly enough, k-means outperforms all other methods by at least three to four percent accuracy on the CIFAR and NORB data set.

However, for a lot of the bigger task more recent results suggest that deep convolutional neural nets outperform everyone else.

Spectrogram Interest Points: Shazaam

After some time, I decided to write another blog post. This time I want to talk about what one can do with local interest points in a spectrogram.

An interest point in a spectrogram is a point of high magnitude in time and frequency. Normally we use points that are a local maximum in a small region.
In that way these points group around interesting audio events in the spectrogram. One use of these features is audio indexing and retrieval. For example, the Shazaam app records audio using your phone. It proceeds to extract local features from the audio and compares them against a data base
of songs, indexed in advance. The app is capable of naming a large variety of songs from noisy recordings.

The algorithm for indexing is extracting such interest points from the spectrogram and continues to
hash combinations of these points. Therefore, the algorithm uses one of the points in a region as an anchor point and measures the offset from the anchor point to other points in a neighborhood. These combinations are to index the audio file. For an unseen song, the hashes are extracted using a sliding window and the app searches for matches with the pre recorded hashes. The image above shows local interest points in red and some combinatorial hashes in yellow grouping around a dolphin whistle. We
used the same features to build a dolphin whistle detector running on an underwater wearable computer.

The algorithm is quite robust to noise and shows good indexing performance on music data.

ICASSP: Pattern Discovery in Dolphin Whistles

Abstract of my ICASSP 2014 paper on Dolphin Communication Mining:

"The study of dolphin cognition involves intensive research of animal vocalizations. Marine mammalogists commonly study a specific sound type known as the whistle found in dolphin communication. However, one of the main problems arises from noisy underwater environments. Often waves and splash noises will partially distort the whistle making analysis or extraction difficult. Another problem is discovering fundamental units that allow research of the composition of whistles. We propose a method for whistle extraction from noisy underwater recordings using a probabilistic approach. Furthermore, we investigate discovery algorithms for fundamental units using a mixture of hidden Markov models. We evaluate our findings with a marine mammalogist on data collected in the field. Furthermore, we have evidence that our algorithms enable researchers to form hypotheses about the composition of whistles."

Symbolic Aggregate approXimation: A symbolic time series representation

I used this time series representation some years ago for a lot for my research. I still think it is an elegant way of representing time series. You can use this easy to use algorithm to convert a one dimensional time series into a string. Given a time series you split it into w equally sized segments and estimate the sample mean in each segment. So we end up with a time series of length w. We then divide the Y axis into k regions using split points or thresholds. Assigning a unique symbol to each of the regions we can
check in which region each sample mean falls into and read of the symbol. So we end with a string of size w.

You can see the performance on multiple time series data sets in the original paper. Furthermore, there is a very efficient way on how to index massive data sets using this representation.