I discover interesting things

Abstract Neural Machines at ICLR 2017

2017-02-08T07:54:00.002-08:00

With my recent excitement for abstract neural machines (see e.g. the related NAMPI workshop), I skimmed the long list of submission of the ICRL conference for interesting papers.
(I might have missed one or the other people [please let me know], but this is what I found.)

I will post a follow-up post as I worked my way through all the papers.

Accepted Papers

Making Neural Programming Architectures Generalize via Recursion

Abstract: Empirically, neural networks that attempt to learn programs from data have exhibited poor generalizability. Moreover, it has traditionally been difficult to reason about the behavior of these models beyond a certain level of input complexity. In order to address these issues, we propose augmenting neural architectures with a key abstraction: recursion. As an application, we implement recursion in the Neural Programmer-Interpreter framework on four tasks: grade-school addition, bubble sort, topological sort, and quicksort. We demonstrate superior generalizability and interpretability with small amounts of training data. Recursion divides the problem into smaller pieces and drastically reduces the domain of each neural network component, making it tractable to prove guarantees about the overall system’s behavior. Our experience suggests that in order for neural architectures to robustly learn program semantics, it is necessary to incorporate a concept like recursion.

Lie-Access Neural Turing Machines

Abstract: Recent work has demonstrated the effectiveness of employing explicit external memory structures in conjunction with deep neural models for algorithmic learning (Graves et al. 2014; Weston et al. 2014). These models utilize differentiable versions of traditional discrete memory-access structures (random access, stacks, tapes) to provide the variable-length storage necessary for computational tasks. In this work, we propose an alternative model, Lie-access memory, that is explicitly designed for the neural setting. In this paradigm, memory is accessed using a continuous head in a key-space manifold. The head is moved via Lie group actions, such as shifts or rotations, generated by a controller, and soft memory access is performed by considering the distance to keys associated with each memory. We argue that Lie groups provide a natural generalization of discrete memory structures, such as Turing machines, as they provide inverse and identity operators while maintain differentiability. To experiment with this approach, we implement several simplified Lie-access neural Turing machine (LANTM) with different Lie groups. We find that this approach is able to perform well on several algorithmic experiments, and outperforms RNN-based methods.

Program Synthesis for Character Level Language Modeling

Abstract: We propose a statistical model applicable to character level language modeling and show that it is a good fit for both, program source code and English text. The model is parameterized by a program from a domain-specific language (DSL) that allows expressing non-trivial data dependencies. Learning is done in two phases: (i) we synthesize a program from the DSL, essentially learning a good representation for the data, and (ii) we learn parameters from the training data - the process is done via counting, as in simple language models such as n-gram. Our experiments show that the precision of our model is comparable to that of neural networks while sharing a number of advantages with n-gram models such as fast query time and the capability to quickly add and remove training data samples. Further, the model is parameterized by a program that can be manually inspected, understood and updated, addressing a major problem of neural networks.

From a software-engineering point of view, I feel that this approach is very promising, as it offers somewhat interpretable output in form of a domain-specific language:

Neuro-Symbolic Program Synthesis

Abstract: Recent years have seen the proposal of a number of neural architectures for the problem of Program Induction. Given a set of input-output examples, these architectures are able to learn mappings that generalize to new test inputs. While achieving impressive results, these approaches have a number of important limitations: (a) they are computationally expensive and hard to train, (b) a model has to be trained for each task (program) separately, and (c) it is hard to interpret or verify the correctness of the learnt mapping (as it is defined by a neural network). In this paper, we propose a novel technique, Neuro-Symbolic Program Synthesis, to overcome the above-mentioned problems. Once trained, our approach can automatically construct computer programs in a domain-specific language that are consistent with a set of input-output examples provided at test time. Our method is based on two novel neural modules. The first module, called the cross correlation I/O network, given a set of input-output examples, produces a continuous representation of the set of I/O examples. The second module, the Recursive-Reverse-Recursive Neural Network (R3NN), given the continuous representation of the examples, synthesizes a program by incrementally expanding partial programs. We demonstrate the effectiveness of our approach by applying it to the rich and complex domain of regular expression based string transformations. Experiments show that the R3NN model is not only able to construct programs from new input-output examples, but it is also able to construct new programs for tasks that it had never observed before during training.

Neural Program Lattices

Abstract: We propose the Neural Program Lattice (NPL), a neural network that learns a hierarchical program structure from a mixture of strong supervision and weak supervision. Our starting point is the recent work of Neural Programmer-Interpreters (NPI), which can only learn from strong supervision (full program execution traces). NPLs can additionally learn from weak supervision consisting of flat sequences of elementary operations. We demonstrate the capability of NPL to learn to perform long-hand addition and arrange blocks in a grid-world environment. Experiments show that it performs on par with NPI while using weak supervision in place of most of the strong supervision, thus indicating its ability to impute latent program abstraction structure from examples containing only weak supervision.

Rejected Papers

Getting rejected from a conference is by no means a sign that the paper doesn't have good ideas; it might just not fit the reviewers' taste, or the advances it proposes might be more on a level of engineering than conceptually. The NIPS experience also revealed a large amount of randomness in the decision-making progress.

Thanks to the open review process, everyone can see what was criticized and led to the rejection.

Dynamic Neural Turing Machine with Continuous and Discrete Addressing Schemes

Abstract: In this paper, we extend neural Turing machine (NTM) into a dynamic neural Turing machine (D-NTM) by introducing a trainable memory addressing scheme. This addressing scheme maintains for each memory cell two separate vectors, content and address vectors. This allows the D-NTM to learn a wide variety of location-based addressing strategies including both linear and nonlinear ones. We implement the D-NTM with both continuous, differentiable and discrete, non-differentiable read/write mechanisms. We investigate the mechanisms and effects for learning to read and write to a memory through experiments on Facebook bAbI tasks using both a feedforward and GRU-controller. The D-NTM is evaluated on a set of Facebook bAbI tasks and shown to outperform NTM and LSTM baselines. We also provide further experimental results on sequential MNIST, associative recall and copy tasks.

Hierarchical Memory Networks

Abstract: Memory networks are neural networks with an explicit memory component that can be both read and written to by the network. The memory is often addressed in a soft way using a softmax function, making end-to-end training with backpropagation possible. However, this is not computationally scalable for applications which require the network to read from extremely large memories. On the other hand, it is well known that hard attention mechanisms based on reinforcement learning are challenging to train successfully. In this paper, we explore a form of hierarchical memory network, which can be considered as a hybrid between hard and soft attention memory networks. The memory is organized in a hierarchical structure such that reading from it is done with less computation than soft attention over a flat memory, while also being easier to train than hard attention over a flat memory. Specifically, we propose to incorporate Maximum Inner Product Search (MIPS) in the training and inference procedures for our hierarchical memory network. We explore the use of various state-of-the art approximate MIPS techniques and report results on SimpleQuestions, a challenging large scale factoid question answering task.

Not about Neural Abstract Machines, but related Papers

This is not a typical neural abstract machine, but it follows the idea of using differentiable elements to make things trainable that otherwise wouldn't be:

Neural Functional Programming

Abstract: We discuss a range of modeling choices that arise when constructing an end-to-end differentiable programming language suitable for learning programs from input-output examples. Taking cues from programming languages research, we study the effect of memory allocation schemes, immutable data, type systems, and built-in control-flow structures on the success rate of learning algorithms. We build a range of models leading up to a simple differentiable functional programming language. Our empirical evaluation shows that this language allows to learn far more programs than existing baselines.

This is slightly different, but since I had quite some exposure to graph transformation and related formalisms in my undergrad, I find this fascinating, too:
Learning Graphical State Transitions

Abstract: Graph-structured data is important in modeling relationships between multiple entities, and can be used to represent states of the world as well as many data structures. Li et al. (2016) describe a model known as a Gated Graph Sequence Neural Network (GGS-NN) that produces sequences from graph-structured input. In this work I introduce the Gated Graph Transformer Neural Network (GGT-NN), an extension of GGS-NNs that uses graph-structured data as an intermediate representation. The model can learn to construct and modify graphs in sophisticated ways based on textual input, and also to use the graphs to produce a variety of outputs. For example, the model successfully learns to solve almost all of the bAbI tasks (Weston et al., 2016), and also discovers the rules governing graphical formulations of a simple cellular automaton and a family of Turing machines.

LOOKING BEYOND AUTOMATA MODELS: TRANSDUCING AND GRAMMAR LEARNING WITH NEURAL MACHINES

2017-02-08T07:08:00.002-08:00

In linguistic applications, tasks typically are translating a sentence, or deciding whether a given string belongs to a specific language. In the past, popular models to learn rules were finite state machines, pushdown automata, and hidden Markov models. We understand these models fairly well, and they each describe a class in the Chomsky hierarchy. This makes them very apt to model formal systems. But when it comes to describing natural language and solving problems in NLP, the rules imposed by formal grammars are often too strict and limited to model human writing and speech.

In recent years, neural models outperform automata models, especially deep networks, when solving real-world tasks. Deep networks perform particularly well on large datasets. Interestingly, recent developments in parts of the deep learning community took renewed inspiration from the field of automata and formal models to improve RNN- and LSTM-based deep network for sequence prediction and transducing tasks. This isn’t the first time the two fields meet, see such as Giles et al.’s work from the early 90ies on neural stacks, but it is the first time deep networks are used in practice at large-scale, offering the best performance.

The key idea behind all proposals is to extend neural networks with memory managed by a controller. The controller, managing access and use to the memory, is built to be a differentiable operator (e.g. another kind of network with differentiable access operators). The resulting network can be trained using standard optimization algorithms and frameworks, benefiting from the same GPU acceleration other networks do, too.
To my limited knowledge, the increase in interest in these models came with Graves et al. at Deep Mind neural turing machines (NTM)., and Weston et al. at Facebook memory networks, roughly proposed at the same time. Both approaches extend neural networks with a read-write memory block. While the NTM paper focuses on program inference and solving algorithmic tasks, the memory network paper focuses on increasing performance on language problems. Since other blogs already offer nice high-level summaries on NTMs and memory networks, I will not go into more details. AMoreover, at this year’s nampi workshop at NIPS, Graves extended the idea of memory access by additionally learning how many computation steps are required to finish computation and output a decision.

The paper I am focusing on is Learning to Transduce with Unbounded Memory by Grefenstette et al. The paper’s goal is to provide a middle ground between the fully random access memory of NTM and the static memory of RNNs. The abstract says:

Recently, strong results have been demonstrated by Deep Recurrent Neural Networks on natural language transduction problems. In this paper we explore the representational power of these models using synthetic grammars designed to exhibit phenomena similar to those found in real transduction problems such as machine translation. These experiments lead us to propose new memory-based recurrent networks that implement continuously differentiable analogues of traditional data structures such as Stacks, Queues, and DeQues. We show that these architectures exhibit superior generalisation performance to Deep RNNs and are often able to learn the underlying generating algorithms in our transduction experiments.

The key data structure implemented is a “continuous” stack. Its read- and write-operations are not discrete, but on a continuum in (0,1), modeling the certainty of wanting to push or pop onto the stack. The data objects are vectors. The stack is modeled by two components: a value matrix V, and a strength vector s. The value matrix grows with each time step by appending a new row and models an append-only memory. The logical stack is extracted by using the strength vector s. A controller acts on the tuple of value matrix and strength vector (V, s). It takes in a pop signal u, a push signal d, a value v, and produces an (output) read vector r. The quantities u and d are used to update the strength vector s, whereas v is appended to the value matrix V, and the read vector r is a weighted sum of the rows of the value matrix V.
The following figure illustrates the initial push of v_1 onto the stack, a very “weak” push of v_2, and then a pop operation and another push operation of a value v_3 (you can find the exact equations and rules to modify s and read r are stated in the paper).

The next figure illustrates the setup: the memory at the center and the controller input values d for pushing, u for popping, and the value v. Moreover, the previous value matrix and previous strength vector are used. The outputs are the next value matrix and strength vector as well as the read vector. This construction a differentiable memory block containing a stack. But there are no free parameters to optimize its behavior. By viewing the previous value matrix, strength vector, and read vector as a state output of an RNN that receives an input vector i, the authors obtain a trainable system with free parameters.

But what advantage does such a system offer? To determine its effectiveness, the authors consider several simple tasks (copying a sequence, reversing a sequence, and inverting bigrams in a sequence) and tasks from linguistics (using inversion transduction grammars, a subclass of context-free grammars). The network enhanced with a stack is compared to a deep LSTM network. Overall, the stack enhanced network not only performs better but also converges faster.

Unfortunately, the authors don’t provide an analysis of the stack usage. I think it would be interesting to see how the LSTM controller learns how to use the stack and compare the results with traditional pushdown automata. In grammatical inference, the usual goal is to find the smallest possible automaton. How different is this goal from learning a stack-enhanced LSTM? Can we understand the model, and does it offer some insight? The ability to interpret automata (and their use as a specification language in formal systems) is a huge motivating factor for our own work (see e.g. our paper on interpreting automata for sequential data). What can we learn from others?

Disclaimer: The graphics are taken from the research paper; Chomsky hierarchy from wiki commons (by Dnu72)

This blog post was first published on automatonlearning.net

A blog post about blog posts about NIPS

2015-12-16T08:34:00.002-08:00

After this year's NIPS conference, a lot of people wrote summaries, pointed out their personal take-aways or favorite sessions, or shared their session notes.

Here's a (totally incomplete, and randomly ordered) list of blog posts I noticed; please feel free and comment with a link to your own post so I can add yours to the list. I will continue to expand and complete it.

I haven't had time to read and work through all of them, but I will try to add short summaries and author information to this blog post as I go through them.

https://corcra.github.io/ml/2015/12/14/NIPS2015.html
by Stephanie, @__hylandSL from Cornell

https://memming.wordpress.com/2015/12/07/nips-2015-part-1/ and https://memming.wordpress.com/2015/12/09/nips-2015-part-2/ https://memming.wordpress.com/2015/12/15/nips-2015-part-3/
https://memming.wordpress.com/2015/12/15/nips-2015-workshops/
by a computational neuroscientist, memming.com
https://blogs.princeton.edu/imabandit/2015/12/13/on-the-spirit-of-nips-2015-and-openai/
by Sebastian Bubeck from Microsoft
On 10 Deep Learning trends
http://codinginparadise.org/ebooks/html/blog/ten_deep_learning_trends_at_nips_2015.html
by @bradneuberg from Dropbox. He shared also a couple of other session notes.
https://gridworld.wordpress.com/2015/12/13/nips-2015-deep-rl-workshop/
by Marc Deisenroth (he has a couple of more articles on his blog)
http://www.zaizi.com/blog/wiml-and-nips-conference-montreal-2015
by Jayani Withanawasam
https://medium.com/@libbykinsey/my-nips-2015-highlights-810e23c9da13
by Libby Kinsey
http://betatim.github.io/posts/physics-does-nips/
by Tim Head, a physicist
http://alexhwilliams.info/itsneuronalblog/2015/12/14/nips/
by Alex Williams
http://www.danvk.org/2015/12/12/nips-2015.html
http://www.machinedlearnings.com/2015/12/nips-2015-review.html by Paul Mineiro
http://slides.com/invisibleroads/nips-2015-recap/fullscreen#/ Selected NIPS Recap by @crosscompute
http://hunch.net/?p=3001617 Interesting things at NIPS by John Langford
https://docs.google.com/document/d/1Ox4nK4GlxUo0WA-vXPmLjaIhgrggMxcGJGva_6k8-F0/ Notes by @sandhya212 from Columbia
http://www.cinjon.com/nips-2015 by Cinjon
http://blog.shakirm.com/2015/12/a-year-of-approximate-inference/ A Year of Approximate Inference by Shakir Mohamed
http://nlpers.blogspot.com/2015/12/nips-2015-retrospective.html NIPS 2015 Retrospective by Hal Daumé III

Integrating Machine Learning Models for Real-Time Prediction into your Existing Workflow (using openscoring and PMML)

2014-07-30T11:24:00.001-07:00

In today's world, understanding customers and learning from their behavior is a key component in a company's competitive edge in the market. This not only refers to lower user-retention costs in marketing through intelligently timed re-engagement and a higher lifetime value of users through clever item recommendation systems, but also extends to lower operating costs and a better user experience through modern risk and fraud management: discovering fraudulent participants in marketplaces or payments at risk are vital to the overall performance.

Especially for established companies outside the mobile- and web-service space, adopting new practices and integrating lessons learned from a thorough data analysis can be hard. Established work flows and running systems need to be changed, which can often be a painful experience---especially when outside consultants are hired to conduct the initial study and viability analysis. Their tools might not be a good fit for the company's established stack.

A good solution to integrate a new layer of data mining and machine learning models is a middleware layer, such as openscoring. It runs independently and can be accessed through a REST API it provides. Existing software does not need to extended with new libraries for data analysis, but only needs to be able to communicate via HTTP, passing on XML requests---a very low bar most systems will pass without any additions---and communication that can be implemented without dedicated machine learning specialists.

The machine learning models can be created offline, in a variety of languages such as Python or R. openscoring. A XML description language, the predictive model markup language (PMML), is then used to deploy the model on a server in the cloud. There is even a heroku ready version that can be set up with a couple of lines of code in a matter of minutes.

In the following, I will outline how a model created using the statistical language R, e.g. by a group of consultants or a in-house team, is deployed as a service, ready to be integrated in your existing frameworks.

The example is very simple: Linear regression, i.e. fitting a linear function to given data points such that a given error function is minimized. You can just open your RStudio or any other environment for R and try it out yourself.

The package for R is called pmml and can be installed using the command
> install.packages("pmml")
There is good documentation available online. Since the native output of the package is XML, make sure you have the XML library installed.

The following code snipped creates a linear regression model for a data file on my web server; please beware that it omits a number of important steps (like dealing with missing data, or normalizing the data). But it suffices to give a rough idea: A model is created and fed to the pmml-function, which in turn creates a XML description. We store the description in a file named glm-pmml.xml.

library(pmml)
library(XML)

rawDataDF <- read.CSV("http://rattle.togaware.com/audit.csv")
rawDataDF <- na.omit(rawDataDF)

target <- rawDataDF$TARGET_Adjusted

N <- length(target)
M <- N-500

data.trainingIndex <- sample(N,M)
data.trainingSet <- rawDataDF[data.trainingIndex,]
data.testSet <- rawDataDF[-data.trainingIndex,]

glm.model <- glm(data.trainingSet$TARGET_Adjusted ~ ., data=data.trainingSet, family="binomial")
glm.pmml <- pmml(glm.model, name="GLM Model", data=data.trainingSet)

xmlFile <- file.path(getwd(),"glm-pmml.xml")
saveXML(glm.pmml,xmlFile)

After creating the model and storing it in a PMML file, the next step is its deployment. There are two choices: 1) the model can be uploaded via the REST interface, or 2) it can be given as a command line parameter.
1) The request using the command line tool curl just PUTs

> curl -X PUT --data-binary @glm-pmml.xml -H "Content-type: text/xml" http://localhost:8080/openscoring/model/GLMTest

2) Via command line

> java -cp client-executable-1.1-SNAPSHOT.jar org.openscoring.client.Deployer --model http://localhost:8080/openscoring/model/GLMTest --file glm-pmml.xml

The setup of openscoring itself is straightforward and uncomplicated. Either clone the git on github and deploy it directly to heroku, or download and install it locally---the documentation of openscoring as well as Maven provides step-by-step instructions.

Using a running instance of openscoring with its model is simple: Just send requests via HTTP. For the sake of simplicity, we can just feed back the whole CSV file we used for training:

> curl -X POST --data-binary @simple_model.csv -H "Content-type: text/plain" http://localhost:8080/openscoring/model/GLMTest/csv

The answer will be a list of input-output values. Instead of using curl to send requests via the command line you can easily integrate the API with your existing software projects, e.g. to receive a score to evaluate the likelihood of fraudulent offers on your marketplace. A prominent user of openscoring is AirBnb: The young company uses decision tree models employed on openscoring servers to evaluate and catch fraudulent bookings in real-time.

Are there any drawbacks to this approach? Yes, in some cases: since the machine learning models need to be supported in the PMML language, the newest ideas presented in research papers cannot directly moved into production with openscoring and PMML. But for vast majority of use cases, this certainly does not matter a lot: while new models often have a slight edge in their specific application area as presented in papers, the transfer to a company's application will not automatically translate into the same performance advantage over traditional models. The amount of fine tuning necessary to have any advantage will outbalance any disadvantage a slightly older machine learning model will have.

Stay tuned for my follow-up article covering the use of PMML for data crunching using Hadoop.

Some intros to NoSQL databases

2013-12-29T03:21:00.001-08:00

In general, I am a bit late for the whole NoSQL party, but nevertheless here are some interesting articles:

A bunch of questions about founding a start up comany

2013-10-12T09:23:00.004-07:00

The whole internet seems to be overflowing with advice for start ups. Experts and industry veterans share a wide range of information on twitter and blogs, at meet-ups and conferences. They tend to focus on marketing, product development, metrics and financing. Much of this information is contradictory (and much of the information regarding finding investors seems sketchily focused on “luring” them in, rather than rightfully gaining their trust.)

For all the abundance — and diversity — of advice for start ups, I have not yet been able to find anything on more practical, immediate problems, particularly facing start ups in Berlin or Germany more broadly.Assuming that I am already running a landing page to catch some early adopters, and giving them access to a functional prototype/alpha for special conditions to test out and develop my product, I still have questions that I’d organize into two main groups: 1. Pre-incorporation logistics and 2. Legal and tax details of the founding process.

1. Pre-incorporation logistics:

At what point should I legally found my company? Only once I am certain that my product and business model will work out? Or should I incorporate before I handle any data from businesses, or from private customers?
If I were to collect data before legally founding my company, how can I legally transfer the prototype and the data to the company?
In Germany, having an imprint on your website and following data protection laws is very important. Failure to correctly comply can easily lead to notices from lawyers paid by competitors - without a limited liability company, how can I protect myself?
How do I handle expenses I incur before officially founding my company? What should I do about them if my plans do not materialize before legally founding? Are there any tax breaks that I can claim from pre-founding investments or expenditures?
Can I "hire" any help in advertising/marketing before founding a company?

Assuming I decide to start a German UG company (basically a limited, with some more drawbacks), this leads to another group of questions.

2. Legal and tax details:

How much collateral beyond the first necessary Euro do I need in reality? Does that have any practical impact on how my company can interact with other companies?
What other costs can I avoid? I have to pre-pay taxes, but how should I go about making good estimate of what to pay? Should I try to over or underestimate? I can avoid the IHK membership fee at the beginning?
How should I handle expenses I privately financed before founding, e.g. hosting a landing page, some marketing costs, money spent to research the market and buy publications?
How much money should I put into the company to keep it solvent, but not have more unused liquidity in it than my personal bank account can't handle? How about adding more money later on, especially when there are multiple founders? How to balance stake vs money put in?
In case I suspect that my company will be bought at some point, should I have a holding to hold the actual company, e.g. to avoid the early payment of taxes?
If I plan to have investors, do I need to take any preparations to easily enable parts of the company owned by third parties?
Should I use the "Musterprotokoll" when founding my company or should I have a custom one made? Should I use a service provider like go-ahead or firma.de to found the company, or do everything on my own?
Should I found have a German company, or an English, American, etc. one? Especially in software and SaaS, being some other place may be easier tax- and data protection-wise.

I am aware that a lot of these questions depend on what my specific enterprise will do and I will need to talk to someone professional - but who should I talk to?

A quick overview of simple encryption for end-users

2013-08-27T16:19:00.001-07:00

Recent revelations regarding PRISM and other US (as well as UK and EU) government agencies systematically collecting and processessing private information has sparked many conversations about encryption across socialnetworks. So, here is a quick overview of a few free, (mostly) open source programs that enable everyone to use high quality encryption. The encryption schemes used by the programs listed below are considered uncrackable and require, using the currently available computing power, billions of years to crack.

To encrypt your hard drive and/or private data files, I highly recommend to use TrueCrypt. It can encrypt your entire hard drive, including your operating system. Or, it can create a virtual disk that when you enable and look at it in your explorer will look and function just like a USB drive -- only, everthing you put onto the disk will be still on your harddrive, but now stored in an encypted file. Option #1, The Encrypt Everything Solution requires you to provide a password when you boot up your computer. The TrueCrypt manual provides more information on how to set up encrypted devices or fine tune some of the parameters available.

It is also possible to use truecrypt on android phones with EDS, and if the phone is rooted, it is possible to share encrypted files via Dropbox between smartphones and other devices.

To encrypt emails, as well as single files, public key cryptography is the go-to choice. This works by having every users generate two keys, a public one that anyone can know, and a private one that must stay secret. The public key can be used to create encrypted messages for the owner of the key (think of this like putting a lock onto the message) -- it can only be decrypted using the private key (the key to the lock that you put on the message). The private key can be used to create signatures of documents. This enables third parties to reliably check whether a text was authored, and is unmodified, by the owner of the private key.

Popular software that integrates this form of encryption into your email program in the openPGP standard are

gpgtools for mac, obtainable at https://gpgtools.org/
gpg4win for windows, obtainable at http://www.gpg4win.org
k-9 mail for android, obtainable at https://play.google.com/store/apps/details?id=com.fsck.k9

These programs come with an extensive, 190 page manual, although using the program is really simple and easy due to the plugins for Thunderbird and Apple's mail program.

To encrypt chat sessions, I highly recommend using OTR. It is a plugin for pidgin (windows, linux) and adium (mac), an opensource chat client that supports a wide range of chat protocols, e.g. google talk, msn, facebook, xmpp, icq, and many more. It is also available in gibberbot for Android. Using the skype4pidgin plugin in pidgin or adium, it is possible to encrypt the text chat of skype, too. Unfortunately, it does not help to secure voice communication. There are some guides, including video tutorials for set up.

(Another interesting feature: the plugin not only offers encryption, but also enables plausibly deniablity. If used correctly, by just looking at the encrypted stream of exchanged messages, it is not possible to attribute authorship to the messages.)

For push notification based instant messaging on smartphones, I recommend Threema. The system I described above (OTR) requires users to be online to send messages - but whatsapp and others do not require both parties to be online at the same time. Threema avoids this issue by using a scheme similar to the public key encryption in emails.

Unfortunately, it costs a couple of bucks (~1.8 €), but has no further charges. It basically is an encrypted version of whatsapp. The only drawback is, of course, no intercommunication with other messengers. It is also closed source, meaning it is hard to check what the app actually does, but the cryptography is provided by an open source library NaCl.

Surfing anonymously is a bit harder, and there is a choice of VPN providers. They all are centralized, i.e. there is one party that knows everything you do. There are a few peer to peer solutions, and the best and probably most famous on is the TOR project.
The Tor project offers a a lot and is actually used in China, Egypt and other Arabic countries to enable and protect members of the opposition. There is an amazing talk "How governments have tried to block Tor" by one of the creators, describing the arms race with China and other countries on en-/disabling access to the TOR network - once a user is in, it is almost impossible to track his activities.

The Multi-linear Jigsaw of "Candidate Indistinguishability Obfuscation" for functional software encryption (possibly part 1)

2013-07-30T15:39:00.004-07:00

This evening I noticed a few retweets about a code obfuscation technique that was reported as being new and groundbreaking. I was intrigued and read a good article article, but was unsatisfied with the level of detail and the number of unanswered questions I was left with: "What is the concept of obfuscation they use; isn't there a proof of impossibility?" "Does it work for all programs?" "How secure, and how provable is this technique?" and "What does 'multilinear jigsaw puzzle' in detail mean?" as well es my curiosity regarding the 'how' of their construction. To answer these questions, I took a look at the paper itself and took some more detailed notes which you can find below. In short, they have a precise notion of security for their understanding of obfuscation as well as a progression of generalizing and securing their core idea.

The concept of obfuscating and its security:

The issue the paper contributes to is as follows: can one make a program, while preserving its functionality, make it unintelligible (so that looking at it doesn't give you a whole lot of information)? There is a result that roughly states that it is almost impossible to have an "encrypted simulation" of a program to obfuscate it, since it can be shown that one can construct efficient unobfuscater that extracts the information used to make the program unintelligible.
A solution to this dilemma is given by a slightly different formulation of this problem, called the indistinguishability obfuscation. Instead of resorting to simple models of computations such as Turing machines, it uses circuits. Given a particular class of circuits $\mathcal{C}$, then an indistinguishability obfuscator $i\mathcal{O}$ should guarantee that for two equivalent ciruits $C_1$ and $C_2$ the two distributions $i\mathcal{O}(C_1)$ and $i\mathcal{O}(C_2)$ are computationally indistinguishable. It has been an open question, whether such an obfuscator exsists for all polynomial sized circuits.
The guarantee of the obfuscator $i \mathcal{O}$ is formalized by security parameters,; the cirucuit class of the obfuscator is actually $\{ C_\lambda \}$. For encoded circuit equipped with a security parameter, e.g. $i\mathcal{O}(\lambda, C)$, there is for any distinguisher $D$ a negligible function $\alpha$ and it holds: for all obfuscations $C_1, C_2$ of the same circuit $C \in \mathcal{C}_\lambda$, the probability of $D$ distinguishing it is bounded by $\alpha(\lambda)$.

The computation model:

The paper proposes an indistinguishability obfuscator for circuits of the class $NC^1$, that is the class of all circuits that are polynomial in size, and have a logarithmic (specifically: $log^1 n$) depth; one can think of a polynomial number of parallel processors with each a logarithmic runtime. It is not known whether this class equals P, but it can be shown that $NC \subset P$ by sequentializing the computations. For another idea about the class: $AC = NC$, where $AC^i$ contains all boolean circuits with depth $O(log^i n)$ and polynomial number of AND/OR gates that admit an arbitrary number of inputs.
The neat feature of $NC^1$ used for the later construction is giving by Barrington's theorem: Every circuit $C$ of $NC^1$ can be transformed into a collection of $k$ square matrices $M^0_1, \ldots M^0_k$ and $M^1_1, \ldots M^1_k$ and model the computation of the circuit, given input $x$ of length $\ell$ by a matrix product $C(x) = 0 \Longleftrightarrow \prod_{i=1}^k M_i^{x f(i)} = I$ with a pre-defined $f: [k] \rightarrow [\ell ]$.

The core construction:

Besides the need for additional security, the matrix computation will be encoded into $k$ groups $G_i$: if an entry of a matrix $M^0_i$ is $\alpha$, e.g. at $(1,1)$, it is encoded as $g_i^\alpha$. Using a multilinear map, the product can be represented in a single group $G_T$.

The ominous multi-linear jigsaw puzzle is described as follows: given a mutilinear map system over groups of prime order p $e: G_1 \times \ldots \times G_k \rightarrow G_T$, a valid multinear form is given by any expression involving operations in $G_T$, the multilinear form and the operations within each group for the parameters of the multilinear map. The papers gives a sample expression for the case of $k = 3$ as $w_1 \cdot e(x_, y_3, z_1 z_2)^2 \cdot e(x_2^3 x_4, y_1^2, z_2 z_5^3) \cdot w^2_3)$, where $x_i \in G_1$, $y_i \in G_2$ and so an, $w_i \in G_T$.

Group elements $g$ then can be viewed as puzzle pieces for the puzzle given by such an expression. A solution is given when the expression yields a unit $g_T \in G_$. The puzzle thus has a generator outputting system parameters $prms$ and some nonempty sets of elements $S_i = \{ x_1^{(i)}, \ldots \} \subset G_i$ and the validator inputs $(prms, S_1, \ldots, S_k, S_T, \prod)$ where the last tuple element is a valid multilinear form. It gives a positiv answer if the form $\prod$ with the given elements gives a unit element of $S_T$.

In order to prove security, the paper makes hardness assumptions of the form: for $g_1, \ldots, g_T$ generators for $G_I$ such that for a form $e$ with $e(g_1, \ldots) = g_T$ it is impossible to distinguish tuples of expotential products of the generators.
The obfuscation scheme:
This construction then is used in a Witness encryption like scheme:

We observe here an analogy to witness indistinguishable proofs: if a statement being proven only has a unique witness, then a witness-indistinguishable proof does not need to hide the witness. The way witness indistinguishability can be used is by explicitly constructing statements that can have multiple witnesses. Similarly, we will use indistinguishability obfuscation by constructing circuits that inherently have multiple equivalent forms. We use this analogy to build our main application of functional encryption.

This is used as

Given an $NP$ Language $L$, a witness encryption scheme for $L$ is an encryption scheme that takes as input an instance $x$ and a message bit $b$, and outputs a ciphertext $c$. If $x \in L$ and $w$ is a valid witness for $x$, then a decryptor can use $w$ to decrypt $c$ and recover $b$. However, if $x \not \in L$, then an encryption of 0 should be computationally indistinguishable from an encryption of 1.

The Indistinguishablity Obfuscation for $NC^1$ implies Witness encryption for an $NP$-Complete language. The takes proceeds to argue for $L=SATISFIABILITY$, using the function $F_{x,b}(w)$ defined by:

$F_{x,b}(w) = b$ if w is a valid witness for x
$F_{x,b}(w) = \perp$

yields a witness scheme because for $F_{x,b}(w)$ and $SATISFIABILITY$, $F_{x,b}(w)$ is in $NC^1$.
The remainder:
This finishes up this post, being possibly part 1, since the paper continues:

to solve the open problem by lifting the $NC^1$ construction to obtain a construction for all polynomial sized circuits
provide functional encryption schemes for those circuits
obtains a "meaningful" simulation based security for function encryption
provides security proofs against several classes of attacks

But I figure that if someone wants to know these details too, they'd have already read the paper before arriving here -- while my questions along the lines of "What are they doing?", "Does it work for all programs?", "How secure, and how provable is this?" are answered sufficiently for now.
The actual paper is at http://eprint.iacr.org/2013/451

Categorial constructions (Part 1)

2013-07-29T17:59:00.001-07:00

Reading up on a paper, I discovered that I will need Day's convolution to construct tensors in a bicategory of monoidal supported profunctors. The hom-categories of these to $Set$ then capture supported pre-categories as a partial monoid.

So slowly working toward it, I flesh out some of my notes here:

Usually, one encounters convolution in electrical engineering and in image processing; the convolution of two functions $f$ and $g$, denoted by the convolution operator $*$ as $(f * g)$ is defined as

\[ (f*g)(t) = \int_{-\infty}^{\infty} f(\tau) f(t - \tau) d \tau \]

where $f, g: M \rightarrow \mathbb{C}$ are maps from a group to complex numbers. It can be thought of as a moving window, giving by one of the function, that inspects the values of the other function. This definition can be extended to convolutions on functors $F$ on a monoidal category $M$ to the category of sets $Set$, $F: M \rightarrow Set$.

In the standard setting, convolution yields a commutative algebra without identity on the linear space of (suitably) measureable functions. For the extension, the functor category $Set^M$ of functors $F: M \rightarrow Set$ yields a monoidal category; Day's convolution is its tensor product.

A simple example to see how it works is given by graded sets in a categorical setting: given the discrete category $\mathbb{N}$ with natural numbers as objects and only identify mappings as morphisms, where addition plays the role of the monoidal product, the graded sets then can be represented by functors $F: \mathbb{N} \rightarrow Set$. The convolution in the category then is

\[ (F*G)(n) = \sum_{i+j=n} F(i) \times G(j) = \sum_{i,j} F(i) \times G(j) \times hom_{\mathbb{N}(n, i \otimes j) \]

Where $\otimes$ is the addition of natural numbers. Moving on to a more general setting, one wants to replace $\mathbb{N}$ by a general monoidal category $C$. The formula for the convolution, given two presheaves $F, G: C^{op} \rightarrow Set$ is defined as

$ (F*G)(e) = \int^{c,d \in Obj(C)} F(c) \times G(d) \times hom_C(e, c \otimes d)$

In that expression, the convolution product is given by a coend $\int$ of the functor under the integral symbol. The coend of an functor $F$ in $Set$ is an object $e$ with a universal dinatural transformation $\zeta: F \stackrel{..}{\rightarrow} e$. In this case, the notion of dinatural transformation relaxes the requirements of a natural transformation: usually, for a natural transformation $\alpha: F \rightarrow G$ between functors F and G, $\alpha$ depends on some variable $x$ co-/contravariantly. A dinatural, or in this case the slightly more restrictive notion of an extranatural transformation requires either F or G to depend on some variable both co- and contravariantly. It is constituted by a collection of morphisms $\alpha_c: F(c,c) \rightarrow G(c,c)$ such that for every morphism $f: c \rightarrow c'$ in $C$ the hexagon identity holds:

$G(c,f)\alpha_cF(f,c) = G(f,c')\alpha_{c'} F(c',f):F(c',c) \rightarrow G(c,c')$

In this setting, the coend object is an object of $Set$. The Day's convolution has some nice properties regarding the preservation of colimits, as well as some interesting relations to the Yoneda embedding. The next posts will contain more on the properties on the convolution and possibly the Yoneda lemma, but also mainly focus on recovering supported precategories in a more abstract setting.

Mahout

2013-07-27T10:06:00.000-07:00

A nice intro slideset to Mahout, a mapreduce enabled hadoop machine learning library in java:

Introduction to Mahout and Machine Learning from Varad Meru

Writing Systems; Miss Korea and facial analysis

2013-04-29T08:36:00.000-07:00

In a blog post, the relationship between the complexity of writing systems and its associated culture is discussed. While I do not agree with some arguments, it opens an interesting perspective.

On another note, there is an interesting (mathematical) analysis of the top 20 Miss Korea contestants and the similarity of their faces.

Auctioneers and High Performance

2013-04-22T06:13:00.002-07:00

There is an interesting article/blog post on the architecture of the LMAX exchange. They prefer a single thread model with event sourcing over an actor driven model. Betfair, a company related to the LMAX owners, at least for a while, used an actor, in memory model for sports betting. These issues are only relevant when handling very high volumes of trades, but certainly might become increasingly interesting for exchanges handling crypto currencies like bitcoin, litecoin or ppcoin.

Quick permutations

2013-04-06T17:16:00.002-07:00

itertools for python are fun:

import itertools

partb= list(itertools.imap(lambda x: "".join(x), itertools.combinations('aApe',3)))
parta = list(itertools.imap(lambda x: "".join(x), itertools.permutations('gRrAet!1',5)))

print '\n'.join(list(itertools.imap(lambda x: "".join(x), (itertools.product(parta, partb)))))

But in the end, this post is just to test out the syntax highlighting feature in javascript.

On Animal Intelligence, Human Behaviour and Econometrics

2012-09-21T15:05:00.000-07:00

Quite a while since the last post; here a few things I read in the meantime

On animal intelligence:

On humans:

Xerox optimizes hiring of its telephone support staff by evaluating a questionnaire on potential candidates' personality aiming at keeping them on the job long enough to make the training pay out
some tricks/guidelines on human interaction mostly regarding conversations

Moreover, there is a free course on computational economics (course material, coursera videos), mostly pretty basic stuff with support of MS Excel as well asR.I'm also working through a book on econometric analysis by William Greene which offers a better insight into analysing markets and their driving factors.

JP Morgan

2012-05-19T09:57:00.000-07:00

Recently, JP Morgan reported rather biggish losses due to only a few trades/positions. According to rumors, hedgefunds and speculators already took a piece of the cake, since positions are not closed yet. It's not completely known which these are, but apparently they involve the the IG9, a credit default swap index including 125 american companies. You can find more information on it at markit CDX and their product description page. Basically, it's one of the largest and most liquid CDS products. You would want to buy these products to hedge risk on bonds issued by the companies included in the index. Conversely you sell it, if you want to bet on the solvency of the companies. In this case, you get some money up front for selling it and a continuous payments during the contract period (10 years). As soon as a company fails to meet its liabilities, the total loss on the company is calculated, e.g. if the company recovers at 30% after filing for bancrupcy, the 70% loss is mutliplied by the weight of the company in the index (all have 0.8%) gives the amount of money you need to pay to cover for the losses.
Moreover, these products create a leverage and thus opens the possiblity to hedge delta trades by buying on the index. Apparently, this kind of trade caused the problems at JP Morgan. As far as I know, there is no easy access to these products using your everyday discount broker.

List of links to news regarding JP Morgans trade:

http://online.wsj.com/article/SB10001424052702303879604577412613778263918.html

A bit of Computation, Math and Psychology

2012-04-15T12:44:00.000-07:00

Some statistics: Verbal intelligence by demographic: blog post
An implementation of reversible computation gates using crabs: article and paper
blog post on the optimal base for a number system w.r.t to number of digits in base and length of numbers
High performance correlation techniques for time series (watch out, .ppt file)

Models for Cognition: Belief vs Connectionism; links on writing style

2012-03-14T09:08:00.000-07:00

There's an interesting article about the consequences of connectionist models for the theory of beliefs. I think it's interesting that one counterexample is taken as a proof for the non-existence of beliefs, whereas a lot of further contraints (for biological and evolutionary reasons) might apply to require the construction to be more uniform/unique.

Another set of links regarding style of writing papers/thesis: Nine cirlces of latex hell, essential guide to latex and a rant on Strunk's Elements of Style.

STOC Papers

2012-02-14T06:57:00.000-08:00

A blog post with links to the accepted STOC 2010 papers. Quite some intesting topics!

Architecture: Hedonistic sustainability

2012-01-28T12:18:00.000-08:00

I've been only twice to Copenhagen, but I really liked it there. That's of course because the Danish people are very nice, but also because I really like how the city feels.
There's a great TEDtalk on architecture by some Danish with focus on sustainability: Link to TED page.

I strongly suggest to not watch the video in the embedded video frame size!

Market Makers & Prediction Markets

2012-01-27T16:53:00.000-08:00

A while ago I posted on the idea of futarchy and followed up with a post on implementation and issues of virtual stock markets.

I only posted links on auction markets, i.e. where one party makes an offer, another one a request and the system finds a match. That only works good for systems with high liquidity. Especially on prediction markets with combinatorical outcomes (e.g. of the form "if person A becomes the candidate for party 1, then party 2 will win the election" or even more complex constructions) this is difficult: you need to find people making similar opposite bets to match. A way around of this is to use a market maker instead of an auctioneer. It takes the trades directly instead of leading a negotiation between to parties. The price is set automatically by the system. This, of course, also has drawbacks. In a real life system, the market maker provides liquidity and thus is at risk losing some money. Moreover, the pricing of the goods depends on parameters of the market maker. Wrong values for thick or thin (i.e. markets with many/few participants) might make the price either bounce up and down or move only tiny bits.

Uncertainity Principle(s)

2012-01-07T05:37:00.000-08:00

Most people know a formulation of the uncertainity principle in quantum mechanics (by Heisenberg), where it basically gives a bound (in terms of the standard deviations of ~) for simultaneous measurements of complementary properties (i.e. measurement operators with non-negative commutator).

There are a number of other places where the principce turns up. It comes from an application of the cauchy schwarz inequality to the fourier transformation. Here's a set of (german) slides from a lecture. Recently Terry Tao posted on a a formulation of the principle due to Mongomery, which has applications in analytic number theory.

On Human Brain Size; the Conciousness and Anaesthesia

2012-01-03T17:28:00.000-08:00

A happy new year to all readers. I just got two articles with some references on further resources:

In near future, I will post some more math; I just haven't read all the things I stumbled on.

edit: let me squeeze in another link to an article:

Language learning is fast when words are connected with movements/gestures, which is also true for abstract words with no obvious gesture for it.

On (implementation issues of) Virtual Stock Markets

2011-12-24T06:29:00.000-08:00

After my recent post on prediction markets, I decided to implement a small auctioneer for virtual stock markets with two parties making deals, i.e. not a market maker mechanism but a (traditional) double auction. But, despite the simple idea behind a bid/ask driven market, the implementation has to take into account quite a number of details: can you buy/sell one unit or multiple units of a good at a time? Does trading occur at discrete events or is it continuous? Is pricing uniform (all trade at the same equilibirum price) or discriminatory (individual matching of bid/ask orders)? And, if one the two options is chosen, how is the price determined?

Beside the double auction system, bidding can take other forms: Auctions and Bidding: A Guide for Computer Scientists
Everything you wanted to know about double auctions, but were afraid to (bid or) ask
And finally a paper on two multi unit k-double auction algorithms

Reading Speed: Chinese vs English

2011-12-22T08:26:00.000-08:00

I always wondered about mankind's languages and writing systems, one of the reasons I looked into Lojban (quite) a while ago. In an earlier post about writing systems I expressed my fascination about non-linear systems. But even with linear systems, we have alphabetic, syllabic and logographic systems. But it turns out the our systems are optimal in the sense that our cognitive abilities won't let us process more optimized systems, at least that is indicated by a study on reading speed with Chinese vs English - two major examples of logographic and alphabetic writing systems.

Futarchy: applying prediction markets

2011-12-14T08:34:00.000-08:00

R. Hanson suggests to use prediction markets to make better use of information to evaluate strategies in politics. He calls the combination of democracy and speculative market information processing futarchy. There is a short manifesto and a full paper (PDF).

The central idea is: Use democracy to express what you want, use prediction markets to evaluate how to reach these goals. People can give strategies which are traded after paying a small fee; when they seem to be efficient the get a payback, otherwise they loose the fee. Thus good strategies are rewarded, bad ones are not rewarded but cost an extra fee. Augmented GDP and other indicators give a measured value to the state of the country.