title: Determining Probability from a Graph

text:
# Question
Title: Determining Probability from a Graph
Lets say I have node A that connects to 10 other nodes. 6 of those nodes have Property 1 and the other 4 have Property 2. How can I easily determining the probability of landing on a node with property 1 randomly while traversing the graph?

# Abstract Example

To clarify this problem, I'm trying to choose the most probable path.

I have a node $v$ with 10 edges going out, and 6 of the nodes on the other end have a certain property $A$, while 4 have a certain property $B$. Now, each of the 10 nodes also has 10 edges going out, and at the end there are 10 nodes, some with property $A$, some with property $B$. The key here is that each property denotes **an occurrence of something.** Using multiple nodes here is basically a replacement for weighted edges. Rather than having an edge with weight 6 leading to $A$, I have 6 occurrences of $A$. I know this sounds counterintuitive, but this is actually a smaller part of a much, much large problem.

I want to find the most likely sequence of something occurring. We can see that there is a 0.6 probability of $A$ occurring. How can I easily determine that?

Basicslly, the question comes down to how can I traverse a graph of probabilities made from a graph of occurrences without having to completely generate a new graph. The brute force method to this would be to start at $v$, count the number of occurrences of $A$ and the number of occurrences of $B$, determine the probability of each, and then on a new graph have an edge from $v$ to $A$ with a weight 0.6. Adter that, you would then go to each occurrence of A, make a list of the difference occurrences branching from that, find the probability of each (with the many occurrences of $A$ acting as one node), then on the new graph, add an edge to each occurrence.

This may seem like a lot of work, but with the algorithm that I am designing, each node may have a dozen properties. I want to be able to quickly traverse the graph taking the most likely path through certain properties, which could be different for each property of every combination of properties.

# Applied Example

Now, let's say that each node on this graph represents an event. Each event can have 9 different properties, and each event is dependent on the last one. For the sake of argument, let's that that the property being considered here is property 4. That doesn't really matter, I'm only noting it to point out that different properties lead to different simplified graphs (more below).

On *Level 0* of the first graph (the black graph), we have event 1 takes occurs. Causing event 1 to occur causes a set of 13 other events to occur on *Level 1*, $\\{A,A,A,A,A,A,B,B,B,B,C,C,D\\}$. We can see that out of all of the events, $A$ is the most common result for property 4.

Now that we know what property to look for, we can look at the events on *Level 2.* The first occurrence of $A$ causes a set of events where property 4 is $\\{E,G,G\\}$, the second occurrence of $A$ causes a set of events where property 4 is $\\{E,F,G\\}$, and so on. Now, we have all these separate nodes, but we can pretend that they are actually one big node since we are only looking at one property.

Because of this, the set of property 4 of events that occur on *Level 2* is $\\{E,G,G,E,F,G,G,H,I,G,G,G,G,E,F,G\\}$. The highest probability of the next event is that of $G$ where the probability is $9/16$.

This yields us the simplified graph shown below:

This shows us the most likely value of property 4 after we initiate event 1 and allow it to go two steps. If event 1 occurs, the most likely value for property 4 will be $A$. After another event in the chain reaction occurs, the most likely value of property 4 will be $G$.

And before you ask, **no, a longest-path algorithm is not appropriate for this application.** It would take another 3 pages to explain why that is, but basically, it doesn't matter if $D$ has the lowest probability but the events after it all have very high probabilities, we need to look at each edge independently.

# Methods that Won't Work

One possible method I could use would be to render a graph for each separate property, but that would just be too much. I could generate the graph for property 4 and yield the graph in the second image, but if I added one more occurrence anywhere in the original graph, I would have to regenerate the graph for every single property, which is too much work when you are dealing with tens or hundreds of thousands of nodes.

So, the question remains: is there a tried and true algorithm for calculating probabilities for the next level as I move along the graph, or will I have to develop something on my own?

# Answer
Let me first rephrase your problem as I understand it. You have a tree of random events. Every event consists of choosing one of a set of child events; every child has the same probability but may have different child events of their own. The children are grouped by some classifier. You want to have efficient access to the group reached by the most likely path of *groups*, not individual children.

I suggest you stick to your idea of the compressed tree of groups but keep it around and maintain it. In a sense, you use it as overlay over the actual graph:

<sup>\[source\]</sup>

The dotted lines represent the original tree, the solid green ones the overlay tree, weighted by the number of original child nodes of the respective group. Note that you can have access to both if you keep references to both roots. You find the desired group ("property" in your notation) by greedily following the edge with maximum weight among all outgoing edges, starting in $I$.

Maintaining this overlay tree is easy: upon adding a node on some level, add it to the appropriate group, adjust the weights and proceed recursively. In pseudo code, this is what the overlay tree might look like:

```
class Node {
  val label : String
  val children : List[Node]
}

class OverlayNode {
  val label : String
  val internal : List[Node]
  val children : Map[String,OverlayNode]

  def weight = children.size

  def insert(n : Node) {
    assert n.label == this.label
    internal ++ n
    foreach ( c in n.children ) {
      if ( children hasKey c.label )
        children(c.label).insert(c)
      else
        children ++ (new OverlayNode(c.label, c))
    }
  }

  def find_max {
    if ( children.size == 0 )
      return this
    else
      return (children argmax {c => c.weight}).find_max
  }
}

```

---

Note that the whole thing does *not* yield correct probabilities, anyway; you count nodes on every level, assuming they occur with the same probability, but that is not correct as siblings can have different amount of children. In the example, the probability to get $C$ if you had $A$ in the first round is *not* $0.5$ as your method determines -- two $C$ are child of them same $A$ and thus compete over the same slot! The precise formula is

$\qquad \displaystyle \begin{align} \operatorname{Pr}(C \mid A) &= \frac{\sum\_{u \text{ type } A} \sum\_{v \text{ of type }C \text{ under } u} \operatorname{Pr}(u)\operatorname{Pr}(v \mid u)}{\operatorname{Pr}(A)} \\ &= \frac{\frac{1}{5}\cdot\frac{1}{3} + \frac{1}{5}\cdot\frac{1}{3} + \frac{1}{5}\cdot\frac{1}{2}}{\frac{3}{5}} \\ &= \frac{7}{18} \end{align}$

This is more complicated to compute than raw counting, but you can still use the idea of the overlay tree. Maintenance will be more expensive but that is something you can not get around without further assumptions on the trees. Note that using the precise formula enables you to switch to non-uniform child distributions without too much hassle.
> 5 votes

---
Tags: graphs, probability-theory
---


# Question
Title: What techniques exist for energy-efficient computing and networking?
I am currently reviewing the potentials of cloud computing regarding energy efficiency and green IT. In connection with this review I am having a look on techniques for increasing energy-efficiency in data centers (computing), hardware, networking and storage devices.

Specificially for computing/servers I have found already a few:

* energy-aware scheduling techniques utilizing frequency and voltage scaling
* virtualization to consolidate server resources
* energy-saving hardware, e.g. ACPI, several processor techniques, especially for mobile devices etc.

However, for networking devices it is rather hard to get information about energy-saving technologies. I have read that people are thinking about new protocols and alternative routing methods to be able to switch off hardware if the network is under low load. Does anyone know of such examples?

Which other points should be added, either for networking or computing

# Answer
> 4 votes
I only know very little about this topic. But from the algorithmic point of view there is a very nice review article from Susanne Albers, which is probably a good starting point.

---
Tags: reference-request, computer-architecture, operating-systems, computer-networks, power-consumption
---


# Question
Title: Most efficient algorithm to print 1-100 using a given random number generator
We are given a random number generator `RandNum50` which generates a random integer uniformly in the range 1–50. We may use only this random number generator to generate and print all integers from 1 to 100 in a random order. Every number must come exactly once, and the probability of any number occurring at any place must be equal.

What is the most efficient algorithm for this?

# Answer
I thought (so it can be wrong :-) of this $O(N^2)$ solution that uses the Fisher-Yates shuffle. In order to keep uniform distribution with *good approximation* (see EDIT section below) at every iteration you can use this trick to produce a value `krand` between $0$ and $k-1$:

```
 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

```

The Fisher-Yates algorithm becomes:

```
arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

```

### EDIT:

As pointed out by Erick the `krand` function above doesn't return a truly uniform distribution. There are other methods that can be used to get a better (arbitrarily better) and faster approximation; but (up to my knowledge) the only way to get a truly uniform distribution is to use the rejection sampling: pick $m = \lceil \log\_2(k) \rceil$ random bits and if the number $r$ obtained is less than $k$ return it, otherwise generate another random number; a possible implementation:

```
function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}

```
> 3 votes

# Answer
Since other folks have given approximate solutions and solutions involving taking indeterminate numbers of deviates, how about a proof that there is no such algorithm that's guaranteed to only require a finite number of `RandNum50()` calls?

As others have noted, printing the numbers from 1-100 in random order is equivalent to printing a random permutation of these numbers; there are 100! of these permutations, and so any particular permutation must be output with probability $\frac{1}{100!}$.

But if we knew that our algorithm used at most $k$ calls to `RandNum50` for some $k$, then we could argue as follows: firstly, pad out those computation paths that make fewer than $k$ calls to `RandNum50` to make additional dummy calls (that is, calls where the returned value is irrelevant), so that all computation paths make precisely $k$ calls. Any given sequence of $k$ results from our calls to `RandNum50` must result in some output permutation, and so we can build an 'outcomes table' that maps any given sequence $(r\_1, r\_2, \ldots, r\_k)$ of results from our calls into a particular output permutation. Since each of these outcomes is equally likely (each of them has probability $\displaystyle\frac{1}{50^k}$), then the probability of getting any particular permutation out of our algorithm must be of the form $\displaystyle\frac{c}{50^k}$ for some $c$. But $\displaystyle\frac{1}{100!}$ can't be of this form, because $100!$ doesn't divide $50^k$ for any $k$ (for instance, 3 divides $100!$ but can't divide any number of the form $50^k$). This means that no possible distribution of outcomes to random-number calls can produce a uniform permutation.
> 4 votes

# Answer
The previous solutions are not optimal. The complexity is exactly $n\log n + O(1)$ in calls to RandNum50 and is described in some detail here, using as a source of random bit (as suggested by Vor):

```
if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

```

The basic idea is that you save a lot of bits if you generate a uniform between $1$ and $n!$, and then using factorial base decomposition, instead of generating a sequence of uniforms ranged up to $1$, then $2$, then $3$, etc., $n$. This is actually, as I mention in the post, the topic of a paper I have submitted!

If you do not know how to generate a uniform, as suggested in that post, from a random bit, you could also generate an approximation of the uniform directly, in this way (which is equivalent to Vor's "trulyrand", but faster):

```
P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...

```

going as far as you need to go. This is developing $P$ in base $50$. Then simply truncate $P$, i.e., $Q=P\mod n$, in your case $n=100!$. This value is not completely random, but it is a measure of uniformity that is often used. Or, as Vor suggests, you can reject if $P\>n$. Then with this value, you can do the factorial base expansion as described in the post.
> 3 votes

# Answer
I haven't done the analysis to confirm how uniform (or not) this would be, and it could be adjusted to be a true shuffle, but could you just choose, from a starting array of the `i`th index = `i + 1`, the `(k + RandNum50() + RandNum50() - 1) mod (100 - k)` index, with removal, for `k` = 0..99?

This "pushes" the peak in the `RandNum50() + RandNum50()` distribution forward uniformly.

I'm pretty sure this is not quite right as I've stated it because the 0 index (1) is not obtainable from the first choice and I cannot quickly see an alternative 1..50 + 1..50 adjustment that produces 0..99.

**Update**

To fix the issue I noted, I effectively used `RandNum100` as mentioned in the question comments to randomally initialise the first `k` offset.

This produces a distribution with a significant wave at the front.

Instead of advancing by 1 I used another `RandNum50` to increment that first `k`. This produces a result that is random enough for me, but it is still not "truly" random, as can be easily seen if you change K to 2.

Testing VB.NET code where I catered for any even K. Note it is O(K), 6K+2 in fact.
> 1 votes

---
Tags: algorithms, integers, randomness, random-number-generator
---


# Question
Title: Order preserving encoding of strings to numbers
I want to encode strings as real numbers while preserving order. The order of the strings is the lexicographic order (as used in phone books); the order of the numbers is the standard order.

Is there an general (i.e. no additional conditions such as e.g. known max string size) encoding with this property?

# Answer
(I assume that by lexicographic order, you mean lexicographic order. Phone books may have all kinds of oddities due to ordering proper names, such as sorting `McDonald` near `MacDonald`.)

Suppose your strings only contained the characters `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8` and `9`. The mapping from the string $s$ to the decimal number `0.`$\\!\\!s$ is monotonic.

If you have $n$ characters in your alphabet, use base $n+1$.

This encoding accommodates infinite strings too, but you need to use base $n+2$ and skip the largest digit as well as the smallest digit (the largest string beginning with `1` is `1888…` $\mapsto 0.1888\ldots$ which is smaller than `2` $\mapsto 0.2 = 0.1999\ldots$).
> 6 votes

---
Tags: order-theory
---


# Question
Title: Standard or Top Text on Applied Graph Theory
I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the field? I have Cormen et al.

# Answer
> 4 votes
For digraphs in particular, there's Band-Jensen & Gutin's "Digraphs: Theory, Algorithms and Applications". It covers quite a bit of material.

The first edition is free to download now that the second edition is out (There's a link to the pdf on their page). Of course if you've got access to a Springerlink account, you can get the second edition instead!

Apart from being free, while I'm not sure of its popularity (especially considering it's "relatively" young), it's a weighty tome, with extensive coverage from basics to quite advanced topics and from both practical and theoretical perspectives.

The other advantage is that it's one of the few (perhaps only?) full coverage texts specifically on digraphs, rather than a being a general graph theory book with material on digraphs.

# Answer
> 5 votes
I would take a look at the free book by Bondy and Murty: Graph Theory with Applications. This book is less-algorithmic and more graph-theoretical than other resources recommended here. There is also a newer version of the book, which is not available for free on the net, but is extremely well-written and with updated notation. In comparison to other free books on graph theory (as for example Diestel), Bondy/Murty uses a less formal approach to prove and explain the theory.

The reason I have used it, is because it is the primary text-book in the course on Graph Theory at The Technical University of Denmark, lectured by Carsten Thomassen, in which I have been assistant teacher for 2 years.

# Answer
> 3 votes
There is always the free Algorithmic Graph Theory which covers graph algorithms, data structures, traversals, and several other topics. If it doesn't have what you're looking for, at least you're not out anything.

# Answer
> 3 votes
Have a look at (the non free) Algorithmic Graph Theory by Alan Gibbons. It's an oldie but quite widely used in CS, it has a computational approach but does also cover the theory. At around 250 pages it's not too intimidating and is well respected.

# Answer
> 2 votes
There is the book "Managing and Mining Graph Data" from Charu C. Aggarwal.

It contains (among others):

* Graph Mining: Laws and Generators
* Graph Data Management and Mining
* Graph Indexing
* Graph Reachability Queries
* Graph Matching
* Graph Classification

As the title suggests it concentrates on graph data and algorithms for this type of data. I don't know if this is what you are searching for, but I can really recommend this book:

Managing and Mining Graph Data

EDIT: Since one comment asked for "evidence" for the relevance of my answer, I would like to point out the following:

* Charu Aggarwal is one of the guiding lights in the field of Data Mining (Top 20 Authors).
* The book is very well written and easy to understand, even with little previous knowledge.
* There is a review of this book from the ACM stating a recommodation of reading it.
* And finally: I like it :D

---
Tags: algorithms, graphs, reference-request, education, books
---


# Question
Title: Equality testing of arrays and integers in a procedural language
In terms of references and their implementation on the heap and the stack, how is equality testing for arrays different from that for integers?

This is to do with Java programming, if you have a stack and a heap, would equality testing for example `j == i` be the same for arrays and for integers? I understand that arrays, are stored in the heap and the stack, as it holds bulks of data, but integers are only stored in the stack and referenced in the heap.

I understand for equality testing `j==i` (variables) the stack pointer will point to the same location.

I'm confused on how `j==i` would be different for array and integers.

Could someone explain?

# Answer
> 3 votes
Integers are stored in one word of memory and there is a primitive machine code instruction for testing their equality. Most programming languages lift this instruction to the syntax, as with `i == j` in Java (where `i` and `j` are of type `int`).

Arrays are stored in multiple contiguous words in memory. In order to test the equality of two arrays, the program needs to iterate through each pair of memory locations and test the equality of the elements stored in them.

Some programming languages hide the distinction between these to operations by allowing the syntax `==` to be used for testing the equality of two arrays (one can do this in C++, for instance, or Ruby). Other programming languages, such as Java, do not.

# Answer
> 3 votes
The idea of "stack" and "heap" is incoherent in my view. It is best not to think in those terms.

The real difference is between

* locations that are named by (variable) symbols in the program (call them **named locations**) and
* locations (or groups of locations) whose references are stored in other locations (call them **referenced locations**).

If you want, you can think of named locations sitting in a "stack" and referenced locations sitting in a "heap". But that would be mere terminology. It does not reflect what an implementation might actually do.

In Java, when you declare an integer variable:

```
int i;

```

you are creating a named location. An integer such as 23, say, will be stored in that location. Note that only *one location* is created!

On the other hand, when you declare an integer array:

```
int a[10];

```

you are creating a named location `a` and, *in addition*, a block of 10 referenced locations for the elements of the array. The named location `a` stores a *reference* to the block of the 10 locations. (Note that 11 locations are now created. In addition to the 10 locations for the array elements, an *extra location* for the reference to the array!) This corresponds to the picture that you have drawn in the question. For integer variables, there is no reference stored anywhere. So, your picture is wrong for integer variables.

I think of Java as an extremely confusing language from this point of view. The declarations `int i;` and `int a[10];` look so similar, but what they mean is *entirely different*!

Coming back to the question, when you compare two integer variables using `i == j`", you are asking "are the integers stored in the two named locations the same?". When you compare two array variables using `a == b`, you are asking the question "are the references stored in the two named locations *a* and *b* the same?" If *a* and *b* store references to two different blocks of locations both of which might contain the same integers, the comparison `a == b` would still come out false. Why? The comparison `a == b` doesn't look at the actual blocks of locations at all. It just checks to see whether they are the same block. This kind of thing is often called **reference equality** or **shallow equality**.

It is not really your fault if you are totally confused. When hackers design programming languages, this is the kind of mess they create!

---
Tags: programming-languages, arrays, semantics, equality, memory-management
---


# Question
Title: What are staged functions (conceptually)?
In a recent CACM article \[1\], the authors present an implementation for *staged functions*. They use the term as if it was well-known, and none of the references looks like an obvious introduction.

They give a short explanation (emphasis mine and reference number changed; it's 22 in the original)

> In the context of program generation, multistage programming (MSP, staging for short) as established by Taha and Sheard \[2\] **allows programmers to explicitly delay evaluation of a program expression to a later stage** (thus, staging an expression). The present stage effectively acts as a code generator that composes (and possibly executes) the program of the next stage.

However, Taha and Sheard write (emphasis mine):

> **A multi-stage program is one that involves the generation, compilation, and execution of code, all inside the same process.** Multi-stage languages express multi-stage programs. Staging, and consequently multi-stage programming, address the need for general purpose solutions which do not pay run-time interpretive overheads.

They than go on to several references to older work allegedly showing that staging is effective, which suggests that the concept is even older. They don't give a reference for the term itself.

These statements seem to be orthogonal, if not contradictory; maybe what Rompf and Odersky write is an application of what Taha and Sheard propose, but maybe it is another perspective on the same thing. They seem to agree that an important point is that programs (re)write parts of themselves at runtime, but I do not know whether that is a necessary and/or sufficient ability.

So, what is *staging* respectively are interpretations of staging in this context? Where does the term come from?

---

1. Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs by T. Rompf and M. Odersky (2012)
2. MetaML and multi-stageprogramming with explicit annotations by W. Taha and T. Sheard (2000)

# Answer
> 25 votes
To the best of my knowledge, the term *staged computation* was first used by Bill Scherlis in this paper. Prior to that, the term "partial evaluation" was used for much the same concept, but the idea of staged computation is subtly different. Both the ideas are related to Kleene's S-m-n theorem.

If you have a function $\phi(m,n)$ of two arguments, but you know one argument, say $m$, then you can perform some of the computation of the function right away using the knowledge of the first argument. What you are then left with is a function $\phi\_m(n)$ whose computations only depend on the second, unknown, argument.

The idea of partial evaluation is to compute the specialized function $\phi\_m(n)$ *automatically*. Given the code for the original function $\phi$, partial evaluation does static analysis to determine which bits of the code depend on $m$ and which bits depend on $n$, and transforms it to a function $\phi'$ which, given $m$, constructs $\phi\_m$. The second argument $n$ can then be fed to this specialized function.

The idea of staged computation is to think about the function $\phi'$ first. It is called a "staged" function because it works in multiple stages. Once we give it the first argument $m$, it constructs the code for the specialized function $\phi\_m$. This is the "first stage." In the second stage, the second argument is provided to $\phi\_m$ which does the rest of the job.

So, the job of partial evaluation is to transform the code for an ordinary function $\phi$ to a staged function $\phi'$. Scherlis envisaged that this transformation could be done by more general mechanisms than the earlier partial evaluation methods. The subject of "staged computation" now deals with issues such as:

* How to define staged functions?
* What programming languages and type systems should be used for defining staged functions?
* What is the semantics of such languages?
* How do we ensure the coherence and correctness of staged functions?
* What techniques are useful for automatically or semi-automatically constructing staged functions?
* How do we prove the correctness of such techniques?

Staged computation can be very important in practice. In fact, every compiler is in effect a staged computation. Given a source program, it constructs a translated and optimized target program, which can then take the actual input and calculate the result. It is hard to write staged computation programs in practice because we have to juggle the multiple stages and make sure that the right things are done at the right time. Everybody who has written a compiler has struggled with such issues. It is also hard to write programs that write other programs, may they be machine language programs (compilers), SQL queries (database manipulations) or HTML/Server Pages/Javascript code (web applications) and myriads of other applications. The researchers in staged computation aim to create good languages and tools that make it easier and safer to create such applications.

# Answer
> 11 votes
Although the other answers are technically correct, I don't think they give a correct understanding of why computer scientists are interested in staged functions.

By creating staged functions, you define programs that generate programs. One of the big goals of modern practical language theory is to maximise potential reuse. We want to make it possible to write libraries that are not just useful functions and objects, but which help programmers by providing higher order architectural constructions.

It would be great if we could get rid of all boilerplate code. We should be able to minimise the specification language. If we want an event driven dispatcher, for instance, communicating to other dispatchers with a given thread design, we should be able to specify that compactly, and all IO listeners and queue object and thread connections should be able to be built from that specification.

Domain languages tend to be those compact representations we are looking for. When people work in a domain for a while, the language they use tends to drop most duplication of info and become a lean specification. So this theory of staging tends to become a translation system from domain languages to the execution language.

Compilers are technically stagers, but it misses the goal. The goal of modern staging is to allow building programs that build programs to maximise reuse and automate program construction wherever possible. It would be great if one day functional requirements of a program are the program.

See "Generative Programming" by Czarnecki and Eisenecker (ISBN-13: 978-0201309775).

# Answer
> 5 votes
The answer is given in the technical perspective piece for the article in question \[1\]. The problem under consideration is the area of tension between general and specific code:

> Programs can be written to be either general-purpose or special-purpose. General-purpose code has the advantage of being usable in a variety of situations, whereas special-purpose code might be written in a way that takes advantage of unique characteristics of the execution environment and thus gain efficiency at the cost of reusability.

Of course we want to resolve this tension, that is achieve general code *and* specific implementation:

> We can ask the question: Is it possible to write code so that it is general-purpose but then have it automatically specialize itself to the situation at hand during execution?

This has given rise to the idea of having (general) programs (re)write themselves at runtime to accomodate for a specific situation:

> As a result, an important direction of research has involved the search for language and compiler technology that can allow programmers to write general-purpose code that is then correctly and efficiently turned into high-performance specialized code at run-time.

I guess Java's JIT is a good example. One particular idea is multi-stage programming, which Lee explains like this:

> In this line of research, one of the core ideas is the concept of staging. We imagine the execution of a program proceeding in a series of stages, each one calculating values that are used by later stages. What we seek, then, is to write the program code so that somehow these stages are made apparent. If this is accomplished, then we can arrange for the later-stage code to be compiled into code generators that optimize against the results of earlier-stage computations.

That is, "staging" is a way of looking at suitable functions/code that identifies phases in the computation/execution which can be simplified knowing the results of former phases. "Delaying" computation as in the first quote in the question may be a necessary side effect in order to separate stages properly, but it is not the point.

Rompf and Odersky mention fast fourier transform as an example which may be instructive.

---

1. The fox and the hedgehog: technical perspective by Peter Lee (2012)

---
Tags: terminology, programming-languages, meta-programming
---


title: Semantic clustering

text:
# Question
Title: Semantic clustering
I have a very specific question about semantic clustering.

I have a list of words/phrases. I want to run an intelligent semantic clustering algorithm on this list. Please let me know what the available options are. Definitely I am looking for NLP based algorithms.

Simple, open-source, easy-to-use solutions will be highly appreciated. The semantic part is extremely important here.

# Answer
There are a lot of different approaches that you could take. While the commenters are right, coming up with a distance metric is important, based on my own experience, finding good representations of your words/phrases is going to be significantly more important.

Most of the "semantic" clustering algorithms that immediately come to mind are document level, not word or phrase level. This would include things like the closely related LSA, PLSA, and LDA, or neural network based approaches such as Semantic Hashing. This list is by no means exhaustive, any unsupervised machine learning approach to topic modeling could probably be thought of as doing document level semantic clustering.

I'm not sure how well the above approaches would work at the phrase level. I'm not going to say they won't, but I suspect the performance would be quite poor, since you are going to have a bunch of really (really!) sparse term vectors.

At the phrase level there are several techniques that seem promising. Simple techniques, such as just clustering n-grams are unlikely to yield useful results, so we'll rule that out right off the bat. A significantly better option would be to use learned word/phrase embeddings and then run some standard clustering algorithm (such as k-means) over these. Collobert and Weston have done some really interesting work in this vein. Their paper A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning or the related work Word representations: A simple and general method for semi-supervised learning by Turian et al would be a good place to start. Turian has a number of different word embeddings available on his website for download here, which may allow you to sidestep the overhead involved in learning such embeddings yourself.

Another option is to hand engineer features or a distance metric using a resource such as Wordnet. This certainly seems like a reasonable approach and a google search for "wordnet semantic distance" yields numerous results. I can't point you in any particular direction here though. Hope this helps.
> 6 votes

---
Tags: algorithms, strings, string-metrics, natural-language-processing, ontologies
---


# Question
Title: Looking for a book that derives and constructs a model checking application
I am teaching myself program verification and am currently learning proof assistants. I have the book Handbook of Practical Logic and Automated Reasoning which gives the proofs necessary for the understanding of such a system, but more importantly for me it also gives an implementation of the necessary algorithms as OCAML source.

I know that some of the tools listed in Wikipedia: Model Checking tools and YAHODA: Verifications Tools Database are open source, but I also prefer it when the theory, proofs, algorithms and source code are presented at the same time reinforcing each other, and in a progression building up to a final application.

Is there such a book for model checking?

EDIT

I may have found what I am looking for in Mathematical Logic for Computer Science with Prolog source. As I don't have the book, does anyone know if this book fits the requirement?

# Answer
John Harrison's book is an exception in going all the way from theory to practice and making all the source code available. I think you will find it difficult to find an equivalent book for model checking, but there are a few that achieve a close approximation.

* Principles of Model Checking by Baier and Katoen contains a lot of examples and pretty detailed algorithmic description.
* The SPIN Model Checker by Gerard Holzmann is a very different treatment from the author of one of the earliest model checkers. He has maintained the tool for about thirty years and has a "programmatic" approach.

A better bet may be to follow the course notes and lab assignments of some courses available online. At least you will find the theory, practice and examples, even though they are not organised in a book.

Finally, this is not entirely what you asked for, but since you have been studying logic and now model checking, you will invariably run into references to abstract interpretation, which is the basis of static program analysis and is intimately connected to model checking (though this connection is not always explicit in the model checking literature).

* Patrick Cousot's MIT Course is a tour de force covering everything from lattice theoretic foundations to the complete implementation of a static analyzer for a simple language. His course material includes all the code and exercises.
> 8 votes

---
Tags: reference-request, formal-methods, proof-assistants, model-checking
---


title: Complexity of computing $n^{n^2}$

text:
# Question
Title: Complexity of computing $n^{n^2}$
What is the complexity of computing $n^{n^2},\\;n \in \mathbb{N}$?

# Answer
> 12 votes
By using the fast Fourier transform, multiplications on $k$-bit numbers can be done in time $\tilde{O}(k)$ (where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute $n^{n^2}$ with $O(\log n)$ multiplications, and each multiplication involves no number larger than $n^{n^2}$, which has roughly $n^2 \log\_2 n$ bits. So the total amount of time required is $\tilde{O}(n^2(\log n)^2)=\tilde{O}(n^2)$.

# Answer
> 3 votes
**Edited in response to comments**  The time to compute $f(n) = n^{n^2}$ can be decomposed into the time required to compute $f\_1(n) = n^2$ and that required to perform $n ^ {f\_1(n)}$. I'll assume that multiplying an $m$ bit number by an $n$ bit number takes exactly $mn$ time by the school book method ; additions, etc. are constant time. As a result, computing $n^2$ takes $\log\_2^2 (n)$ time.

Suppose that we use binary exponentiation for computing $f(n)$. Binary exponentiation does two kinds of operations in computing $f(n)$: squaring the current product, and multiplying the current product by $n$, according to whether the current bit in the binary expansion of $n^2$ is 0 or 1. In the worst case, $n^2$ is a power of two, so that binary exponentiation repeatedly squares its current product until it reaches the answer.Note that $n^2$ has $m'=\lceil 2 \log\_2(n) \rceil $ bits, so that the number of such squarings is $m= m'-1$. This is the case we analyze further below.

The first squaring takes $t\_1=\log\_2^2(n)$ time, resulting in a $o\_1=2 \log\_2(n)$-bit product . The second squaring takes in two $o\_1$ bit numbers and runs in $t\_2=o\_1^2$ time, resulting in a $o\_2=2o\_1$-bit product. Continuing, the $i$-th step takes $t\_i = 4^{i-1}\log^2\_2 n$ time and outputs a $o\_i=2^{i} \log\_2 (n)$ -bit product. This process stops at the $m$-th step; as a result, it takes time

$T \_{exp} =\sum \_{\[1..m\]} t\_i = \log\_2 ^2 (n) \sum\_{\[1..m\]} 4^i = \frac{4^m -1} {3} \log\_2 ^2 n$.

When the initial squaring cost is included, we find we need time at most

${T\_{exp} + \log\_2^2{n}}$

*Note*

* I omitted some floors and ceilings in the computations, hoping they would not materially affect the answer.
* I deliberately omitted an $O$-based analysis in favour of an exact upper bound just to be rigorous.
* The above reasoning also makes clear why my earlier analysis was flawed. The $O$ notation was used in a fast-and-loose way, and it conveniently omitted constants so that, for instance, $\sum t\_i $ magically became $O(\log n)$.
* The multiplications can be always speeded up by FFT and other methods.

---
Tags: complexity-theory, integers, number-theory
---


# Question
Title: Difference between "information" and "useful information" in algorithmic information theory
According to Wikipedia:

> Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible self-contained representation of that string.

What is the analogous informal rigorous definition of "useful information"? Why is "useful information" not taken as the more natural or more fundamental concept; naively it seems a purely random string must by definition contain zero information, so I'm trying to get my head around the fact that it is considered to have maximal information by the standard definition.

# Answer
> 12 votes
The central concept here is Kolmogorov complexity, and more specifically compressibility. To get a intuitive feeling of compressibility, consider two strings $A \in \mathbb{B}^\*$ and $B \in \mathbb{B}^\*$, where $\mathbb{B} = \\{ 0,1 \\}$. Let

> $A = 1010$ $1010$ $1010$ $1010$, and
>
> $B = 1011$ $0110$ $0111$ $1001$.

Note that $|A| = |B| = 16$. How could we quantify how much information $A$ or $B$ has? If we think about classical information theory, in general, transmitting a string of length $n$ takes $n$ bits on average. However we cannot say how many bits we need to transmit a *specific* string of length $n$.

**Why is the information content of a random string not zero?**

On a closer look, we can see that in fact $A = 10^8$. However, it is much harder to say if $B$ has any obvious patterns in its structure, at least it *seems* and *feels* more random than $A$. Because we can find a pattern in $A$, we can easily compress $A$ and represent it with less than $16$ bits. Likewise, since it is not easy to detect any patterns in $B$, we cannot compress it as much. Therefore we can say that $B$ has more information than $A$. Moreover, a random string of length $n$ has maximal information since there is no way we can compress it, and hence represent it with less than $n$ bits.

**What is useful information, then?**

For *useful information*, yes, there is a definition using a Turing machine $T$. The useful information in $x \in \mathbb{B}^\*$ is

$$\min\_T \space \\{\space l(T) + C(x|T) : T \in \\{ T\_0, T\_1, ... \\} \\},$$

where $l(T)$ denotes the length of a self-limiting encoding for a Turing machine $T$. The notation is usually such that $C(x)$ denotes the Kolmogorov complexity of $x$ and $C(x|y)$ the conditional Kolmogorov complexity of $x$ given $y$.

Here $T$ embodies the amount of useful information contained in $x$. What we could ask is which such $T$ to select among those that satisfy the requirement. The problem is to separate a shortest program $x^\*$ into parts $x^\* = pq$ s.t. $p$ represents an appropriate $T$. This is actually the very idea that spawned minimum description length (MDL).

# Answer
> 4 votes
It could be because "useful" is hard to define. Say we have a highly-structured, information-rich message $x$ which can be compressed at most by a factor of $\alpha$ to the message $y$. Intuitively, $x$ and $y$ contain the same amount of useful information; indeed, they contain the same amount of information according to the usual definition. Now imagine a prefix $z$ of $x$ of the same length as $y$; it should contain no more useful information than $x$, hence, no more than $y$. However, $y$ is more "random" than $z$, since $z$ can be compressed and $y$ can't. So if we try to associate "useful" information with compressibility, we could run into the following paradox: a prefix of a message could have higher "useful" information than the entire message, seemingly a contradiction.

# Answer
> 4 votes
From a less formal point of view, I think it may help if you detach yourself from the word "random," as you're correct that a set of truly random bits don't store any information in a practical sense. (If I encrypt a set of names and send the encrypted values to you, they may have very high Kolmogorov complexity but it's not going to help you figure out the names).

But think about it in this way. If you see a website in a foreign language (say Swedish, assuming you don't speak it) it's going to look more or less random. There will be some order to the words, but not much. However, if you look at a webpage with text that looks like this: 123456123456123456123456... and so on, you'll be able to understand it more quickly. If you don't speak Swedish you'll probably be able to get much more out of it, even if the Swedish webpage said the equivalent of "the first six numbers repeated sequentially". The websites contain the same information, but one looks random to you. And for the amount of space, the one you understand is way less efficient than the Swedish webpage, even though it stores the same information. You may not find this information "useful" because it's in Swedish, but the information is still there.

The notion of "information" is meant to be universal, so what looks like random--and therefore useless--bits to you may store a great deal of information to someone else. The measure of information is intended to be an intrinsic property of the string, and cannot depend on what does and doesn't make sense to you, and what you can and can't interpret.

Another (more technical) point that may help is that I'm being slightly disingenuous here. As Juho points out, information *is* defined relative to who's interpreting it. You may find the Swedish webpage completely useless as a vehicle for information, but someone who speaks Swedish may find it to have a great deal of information. The definition does reflect this. However, from the mathematics we can learn that the difference between the shortest (most informative for the space) webpage to communicate this website to you and the shortest webpage that can communicate it to someone who speaks Swedish can differ only by an additive constant. Why? Because for you, as a non-Swedish speaker, the shortest way to store the page that you can understand is "the first six integers repeated sequentially." This may be quite a bit longer than the Swedish. (Bear with me here and assume that Swedish is super short and efficient whereas English is very long and wasteful).

But even if you were able to speak Swedish, you'd only be able to cut an additive constant from the length! Why? Because you could always go buy a Swedish-English dictionary. Then the super-short Swedish webpages would make sense to you. Sure, they only make sense when you have the dictionary, but the dictionary has a constant length. So $$(\mbox{Most efficient representation of information in English}) \leq (\mbox{Most efficient representation in Swedish}) + (\mbox{Length of Swedish-English dictionary})$$. This is getting a bit off-topic from your original question, but the point I'm trying to make is that it doesn't matter too much who is reading the information. The random-looking Swedish webpage was not "useful" to you, but it's "useful" to someone else, and you're only a constant amount of information away from being able to make use of it yourself.

---
Tags: information-theory, terminology, kolmogorov-complexity
---


# Question
Title: Do non-computable functions grow asymptotically larger?
I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all non-computable functions grow asymptotically larger than computable ones?

**Edit:**

Great answers below but I would like to explain in plainer english what I understand of them.

If there was a computable function f that grew faster than the busy beaver function, then this means that the busy beaver function is bounded by f. In other words, a turing machine would simply need to run for f(n) many steps to decide the halting problem. Since we know the halting problem is undecidable, our initial presupposition is wrong. Therefore, the busy beaver function grows faster than all computable functions.

# Answer
> 14 votes
If you take any noncomputable set of natural numbers, the characteristic function of the set takes only the values $\\{0,1\\}$ and is noncomputable. So it is not the case that every noncomputable function grows very quickly, they can even be bounded.

The Busy Beaver function grows more quickly than every computable function because it is constructed to do so. The proof that it is noncomputable proceeds by first proving that it grows faster than any computable function.

More generally, say that a set $A \subseteq \mathbb{N}$ has "hyperimmune-free degree" if every function computable from $A$ is bounded by a computable function. Certainly every computable set has hyperimmune-free degree. It is known that there are also many noncomputable sets that have hyperimmune-free degree. So it is not the case that everything noncomputable will have to compute some fast-growing function.

However, it is also the case that an r.e. set that is noncomputable will *not* have hyperimmune-free degree. If $B$ is r.e., and enumerated by index $e$, the function $f$ such that $f(n) = k$ if $e$ enumerates $n$ in $k$ steps, and $f(n) = 0$ if $e$ does not enumerate $n$, is computable from $B$ but this function is bounded by a computable function if and only if $B$ is computable.

# Answer
> 5 votes
If a function $f$ grows faster (or slower) than any function in a set $F$ of functions, that is $f \in \omega(g)$ (or $o(g)$) for all functions $g \in F$, then clearly $f \notin F$. This is what is used to show that the busy-beaver function is not computable. Another example is the proof that the -- computable and total -- Ackermann function is not primitive recursive.

The reverse does not necessarily hold. The Halting problem function takes values in $\\{0,1\\}$ so it is in $O(1)$¹; clearly there are computable functions growing as fast and faster.

There are certainly sets of functions for which runtime is both a necessary and sufficient membership criterion, namely those that are *characterised* by runtime, such as

$\qquad \displaystyle \mathrm{Poly} = \\{f : \mathbb{N} \to \mathbb{N} \mid \exists k.\\, f \in O(n^k)\\}$.

---

1. That only makes a limited amount of sense. The parameter of the HP function is a Turing machine encoding and a natural number; its size is no measure of how complicated it is to decide halting.

---
Tags: computability, asymptotics
---


# Question
Title: Can bottom-up architectures be effectively programmed in top-down paradigms?
The subsumption architecture, proposed by Rodney Brooks in 1986, is a "bottom-up" approach, in which robots are designed using simple hierarchical models. These models build upon and subsume the lower modules to form a final product. For example, a robot can be given a "find opening" module which is subsumed by a more abstract "find doorway" module, which is then itself subsumed by an "exit the playing field" module.

Now, obviously, in a more "object-oriented" design, we could have started the design with the "exit the playing field module", but for sake of argument, assume some of the more primitive components (as "functions") will likely get reused in other higher concepts.

Realizing that implementing this robot in a procedural language (or a functional one, for that matter) could be the simplest, but is it counterproductive to try to conceive of a subsumption architecture-based robot in an object-oriented programming paradigm? (realizing also that it's perhaps difficult to weigh a software engineering paradigm against a robotics one) To obtain a solution, is there some form of "adapter" that can be implemented for increasing the effectiveness of using what may be two conflicting paradigms?

# Answer
> 3 votes
I would like to generalize this into a more common scenario. This I believe makes sense since the particulars of subsumption architecture are perhaps not a primary aspect in the question (and the same problems occur in non-robotic fields as well).

In general software archtitecture there is a bi-directional approach, or multi-paradigm approach, as in the question. The bottom most layer of an operating environment is generally written bottom up. Very specific code bits are written to driver very specific hardware elements on the system. These are then combined to form higher level components. I suspect we could easily describe this as a subsumption approach if we simply describe our robot as the system itself, and the goals to control specific aspects of that system. Though I'm not sure it is improtant to do so.

From the top-down most applications are written in higher level languages, or described in terms of an abstract machine. This is quite far removed from the bottom most libraries which will actually be doing the work.

At some point these two layers have to meet -- actually they meet at many locations in a variety of scenarios. This where you have to "adapt" the layers to be suitable for the other layer. The term "adapter" here is 100% correct. There is indeed a software pattern called "adapter" which is used for this purpose.

Aside from specific adapters we can actually consider the entire toolchain of any modern programming. The compiler itself, along with the liner and an execution VM, are the primary interface between the two layers. That is, a high level language is written in one domain, and the compiler is what allows it to work in the lower level domains.

If you are looking specifically for paradigm effectivness, consider that high-level languages exist for imperative programming (C++), functional programming (Haskell), and declarative programming (Prolog). These paradigms all ultimately work on the same underlying low-level libraries.

Is the question in robotics much different? No, I don't believe so. Indeed if the same ideas were formulated today I don't think they'd have a robotic specific term (subsumption architecture) as there is no strong difference from normal software architecture. You even indicate in your last paragraph both a functional and imperative paradigm for controlling a robot. I would however use a domain specific language to be used -- and again, the vast assortment of domain specific languages is further evidence that multiple paradigms can be efficiently adapted to each other.

---
Tags: programming-languages, artificial-intelligence, algorithm-design, object-oriented
---


# Question
Title: How do I classify my emulator input optimization problem, and with which algorithm should I approach it?
Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) as:

**What methods exist to find local optimums on extremely large combinatorial search spaces?**

## Background

In the tool-assisted superplay community we look to provide specially-crafted (not generated in real-time) input to a video game console or emulator in order to minimize some cost (usually time-to-completion). The way this is currently done is by playing the game frame-by-frame and specifying the input for each frame, often redoing parts of the run many times (for example, the recently published run for *The Legend of Zelda: Ocarina of Time* has a total of 198,590 retries).

**Making these runs obtain their goal usually comes down to two main factors: route-planning and traversal.** The former is much more "creative" than the latter.

Route-planning is determining which way the player should navigate overall to complete the game, and is often the most important part of the run. This is analogous to choosing which sorting method to use, for example. The best bubble sort in the world simply isn't going to outperform a quick-sort on 1 million elements.

In the desire for perfection, however, traversal (how the route is carried out) is also a huge factor. Continuing the analogy, this is how the sorting algorithm is implemented. Some routes can't even be performed without very specific frames of input. This is the most tedious process of tool-assisting and is what makes the production of a completed run takes months or even years. It's not a *difficult* process (to a human) because it comes down to trying different variations of the same idea until one is deemed best, but humans can only try so many variations in their attention-span. The application of machines to this task seems proper here.

**My goal now is to try to automate the traversal process in general for the Nintendo 64 system**. The search space for this problem is *far* too large to attack with a brute-force approach. An n-frame segment of an N64 run has 230n possible inputs, meaning a mere 30 frames of input (a second at 30FPS) has 2900 possible inputs; it would be impossible to test these potential solutions, let alone those for a full two-hour run.

However, I'm not interested in attempting (or rather, am not going to even try to attempt) total global optimization of a full run. Rather, **I would like to, given an initial input, approximate the *local* optimum for a particular *segment* of a run (or the nearest *n* local optimums, for a sort of semi-global optimization)**. That is, given a route and an initial traversal of that route: search the neighbors of that traversal to minimize cost, but don't degenerate into trying all the cases that could solve the problem.

My program should therefore take a starting state, an input stream, an evaluation function, and output the local optimum by minimizing the result of the evaluation.

## Current State

Currently I have all the framework taken care of. This includes evaluating an input stream via manipulation of the emulator, setup and teardown, configuration, etc. And as a placeholder of sorts, the optimizer is a very basic genetic algorithm. It simply evaluates a population of input streams, stores/replaces the winner, and generates a new population by mutating the winner stream. This process continues until some arbitrary criteria is met, like time or generation number.

**Note that the slowest part of this program will be, by far, the evaluation of an input stream**. This is because this involves emulating the game for *n* frames. (If I had the time I'd write my own emulator that provided hooks into this kind of stuff, but for now I'm left with synthesizing messages and modifying memory for an existing emulator from another process.) On my main computer, which is fairly modern, evaluating 200 frames takes roughly 14 seconds. As such, I'd prefer an algorithm (given the choice) that minimizes the number of function evaluations.

I've created a system in the framework that manages emulators concurrently. As such **I can evaluate a number of streams at once** with a linear performance scale, but practically speaking the number of running emulators can only be 8 to 32 (and 32 is really pushing it) before system performance deteriorates. This means (given the choice), an algorithm which can do processing while an evaluation is taking place would be highly beneficial, because the optimizer can do some heavy-lifting while it waits on an evaluation.

As a test, my evaluation function (for the game *Banjo Kazooie*) was to sum, per frame, the distance from the player to a goal point. This meant the optimal solution was to get as close to that point as quickly as possible. Limiting mutation to the analog stick only, it took a day to get an *okay* solution. (This was before I implemented concurrency.)

After adding concurrency, I enabled mutation of A button presses and did the same evaluation function at an area that required jumping. With 24 emulators running it took roughly 1 hour to reach the goal from an initially blank input stream, but would probably need to run for days to get to anything close to optimal.

## Problem

**The issue I'm facing is that I don't know enough about the mathematical optimization field to know how to properly model my optimization problem**! I can roughly follow the conceptual idea of many algorithms as described on Wikipedia, for example, but I don't know how to categorize my problem or select the state-of-the-art algorithm for that category.

**From what I can tell, I have a combinatorial problem with an extremely large neighborhood**. On top of that, **the evaluation function is extremely discontinuous, has no gradient, and has many plateaus**. Also, there aren't many constraints, though I'll gladly add the ability to express them if it helps solve the problem; I would like to allow specifying that the Start button should not be used, for example, but this is not the general case.

## Question

**So my question is: how do I model this? What kind of optimization problem am I trying to solve? Which algorithm am I suppose to use?** I'm not afraid of reading research papers so let me know what I should read!

Intuitively, a genetic algorithm couldn't be the best, because it doesn't really seem to learn. For example, if pressing Start seems to *always* make the evaluation worse (because it pauses the game), there should be some sort of designer or brain that learns: "pressing Start at any point is useless." But even this goal isn't as trivial as it sounds, because sometimes pressing start *is* optimal, such as in so-called "pause backward-long-jumps" in *Super Mario 64*! Here the brain would have to learn a much more complex pattern: "pressing Start is useless except when the player is in this very specific state *and will continue with some combination of button presses*."

It seems like I should (or the machine could learn to) represent input in some other fashion more suited to modification. Per-frame input seems too granular, because what's really needed are "actions", which may span several frames...yet many discoveries are made on a frame-by-frame basis, so I can't totally rule it out (the aforementioned pause backward-long-jump requires frame-level precision). It also seems like the fact that input is processed serially should be something that can be capitalized on, but I'm not sure how.

**Currently I'm reading about (Reactive) Tabu Search, Very Large-scale Neighborhood Search, Teaching-learning-based Optimization, and Ant Colony Optimization.**

Is this problem simply too hard to tackle with anything other than random genetic algorithms? Or is it actually a trivial problem that was solved long ago? Thanks for reading and thanks in advance for any responses.

# Answer
From the information you give in your question, I can not see how to apply standard optimisation methods (that I know of). Your objects are not that complicated (more on that later) but your target function is a nasty one: its values are defined by an external system out of your control, it is unlikely to have any nice properties, and so on. Therefore, I think using genetic algorithms is not an unfeasible and maybe even a good approach here; they often work better than other methods if you have no clue about your problem's structure. There is much to consider about

* object space,
* target function and
* parameters of your genetic algorithm,

so allow me elaborate.

## What are your objects?

You have answered that already: your are looking at a sequence of actions, each of which takes up one frame. I think this may be too fine grained; maybe try a sequence of actions, each with a duration (in number of frames). This would allow to have mutations like "walk a bit longer" to have different probabilities than "insert a press of A" in a natural way. Try out what works best; you may have to revisit this item after thinking about the other ingredients.

## What is your target function?

This one is really crucial. What to you want to optimize? Time to goal? Number of different actions? The number of collected stars? A combination of several factors? As soon as you get multiple targets, things get hairy -- there (usually) are no longer optima!

You mentioned time to goal. This is likely not a good target function at all. Why? Because most sequences will not even reach the goal so they will bottom-line to some constant, creating a fitness landscape like this (conceptual sketch in one dimension):

\[source\]

There are huge areas where the target funtion is $0$. Genetic algorithms are all about *signals*: small changes in the solution have to indicate an improvement (or decline) in quality if and only if the change is "directed" towards an optimal solution (ideally). If that is not the case (drastically), you have little more than a random search, hitting a good solution with probability near $0$. What does that mean for our target function? It has to be something that improves whenever a solution improves slightly, *even if overall quality is still low*. So what about

$\qquad \displaystyle \frac{1}{1 + \text{final distance to goal}} + \frac{1}{1 + \text{time to goal}}$

using "infinity" as time to goal if the goal is not reached, that is set the second summand to $0$. As long as the goal is not reached, getting nearer moves fitness up to $1$. All sequences that reach the goal have a baseline of $1$ and improve further the faster they are.

So how do you measure distance? Linear distance may look tempting but has its problems; again, wrong signals may be sent. Consider this simple scenario:

\[source\]

Every sequence that starts with a jump to the upper corridor improves until it reaches a spot just above the goal, but it can never actually get to the goal! Even worse, among all sequences that do not reach the goal, those that go up are as good as those that go down, so the GA can not reject sequences that are clearly doomed. In other words, linear distance creates particularly bad local optima which can trap the GA if there are dead ends in the level.

Therefore, I suggest you overlay a grid over your level and connect neighbour points if the game character can get from one to the other. Then you compute distance-from-goal by the length of the shortest path from the point nearest to where the sequence lands the character to the point nearest to the goal. This is easy to compute and walking into deadends (local optima) is immediately punished¹. Of course you need access to level data, but I assume you have those.

## How does your GA work?

Now we can get to the actual genetic algorithm. The key considerations are population, selection, reproduction/mutation and stopping criterion.

### Population

How *large* is your population going to be? If it is too small, it may not provide the diversity necessary to reach a good solution. If it is too large, you are more likely to carry around useless junk, slowing down the process.

How do you *initialise* your population? Do you pick random action sequences? If so, of which length? Do you have a (small) number of manually generated, reasonable solutions to seed with, maybe such that reach the goal?

### Selection

Which individuals are selected for survival/reproduction? The $k$ best? Do you hold tournaments? Do you decide an individual's survival randomly with respect to its fitness? Do you want the best to survive in any case or can they die (may be useful to leave local optima)²?

The core concept here is selection pressure: how hard is it to survive? Make it too small and you don't weed out crap solutions. Make it too high and you make change (in particular moving between local optima) hard.

### Reproduction and Mutation

Once you have selected your survivors of one round, you have to create the next generation from them (do the parents survive and are part of the next generation?). There are two major strategies: mutation and recombination.

Mutation is quite clear, although the specifics can differ. For every position in an individual's sequence, mutate it with some probability. You can do this independently for every position, or choose the number of mutations randomly, or you can perform different mutations with different probabilities (such as inserting a new element, removing one, changing one, ...). Mutation is usually about *small* changes.

Recombination, that is combining aspects of two or more solutions to a new one, is more tricky but can allow *big* steps, that is leaving one "fitness mountain" and move directly to the slope of another (which may be higher). A classic idea is the crossover; I don't know whether that makes sense here (it seems to me that swapping the prefix of a given sequence for something else will most likely devalue the suffix). Maybe you can use knowledge about the level and positions of the game character at different points in the sequence to guide this, that is create crossover points only where the character is at the same position in both sequences.

### Termination

When do you stop? After $N$ generations? When the maximum fitness has not improved since $k$ rounds? Do you stop early if some fitness (with above function, $1$) has not been reached after $n$ rounds in order to eliminate useless initial populations early?

---

As you can see, all these things intertwine to influence the actual performance. If you run multiple populations in parallel, you can even think about implementing genetic drift due to migration and/or catastrophes. There is little theory to guide your way, so you have to try out different setups and look where it gets you. Hopefully, what works for one level will also work for others. Happy tinkering!

Nota bene: Have look at BoxCar 2D in the light of the above. They do some things pretty well (others, not so) and you can get an intuition for how a GA's parameters can influence its performance.

---

1. Actually, constructing a sequence greedily using this fitness, that is choosing the action that minimises distance-to-goal out of all possible next action, may work quite well. Try that before using GA!
2. Of course, you as observer always remember the best solution ever encountered.
> 6 votes

# Answer
For more details on Teaching-learning-based optimization (TLBO) method and its code, refer to the following paper:

> An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems by R. Venkata Rao and V. Patel; International Journal of Industrial Engineering Computations 3 (4): 535–560 (2012)

For additional reading:
> 1 votes

---
Tags: reference-request, machine-learning, combinatorics, optimization, search-problem
---


# Question
Title: Counting with constant space bounded TMs
The problem, coming from an interview question, is:

> You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the count of occurrence of that number till that moment. Give a suitable Data structure/algorithm to implement this system.

The stream is infinite, so if fixed size data structures re used, i.e. primitive types in Java or C, they will overflow. So there is the need to use data structures that have a size that grows over time. As pointed by the interviewer, the memory occupied by those data structures will diverge.

The model of computation is a Turing machine with three tapes:

* infinite read-only one-way input tape;
* constant space bounded read-write two way work tape;
* infinite write-only one-way output tape.

The main reason to choose the model above is that in the real world there is virtually no limit to the quantity of input that can be acquired using a keyboard or a network connection. Also, there is virtually no limit to the quantity of information that can be displayed on amonitor over time. But memory is limited and expensive.

I modeled the problem as the problem to recognize the language L of all couples (number,number of occurrences so far).

As a corollary of the Theorem 3.13 in Hopcroft-Ullman I know that every language recognized by a constant space bounded machine is regular.

But, in any given moment, the language L is a finite language, because the number of couples to be recognized is finite: 60001. So I can't use the pumping lemma for regular languages to prove that such language is not regular.

Is there a way I can complete my proof?

The original question is here.

# Answer
Let me give an explanation which does not differ in content from the accepted answer, but brings the question back to the realm of regular languages.

The language you are dealing with can be defined as follows. Let $s \in \Sigma^{\mathbb{N}}$ be a (countably) infinite string of symbols from some finite alphabet $\Sigma$, and let $s\[1:i\]$ be the prefix of the first $i$ symbols in $s$. In your case $s$ is the input and and $\Sigma$ is the nonnegative positive integers $\\{0, \ldots, 60000\\}$. $L(s)$ can be defined as a language of triples $(s\[1:i\], a, j)$ where $(s\[1:i\], a, j) \in L(s)$ if and only if there are $j$ occurrences of $a$ in $s\[1:i\]$. Convince yourself, using the pumping lemma, that for any fixed $s$, $L(s)$ is not regular. Then convince yourself that if a bounded memory Turing machine could solve your problem, it could also recognize the non-regular language $L(s)$. This argument ought to work even if we fix $a$ and define a similar language $L(s, a)$.

These kinds of examples are the reason why our computational model of choice (our = the algorithms community) is the word RAM machine, and we assume that word size grows with input size. This is supposed to model the fact that as the instances we face in reality grow, so does the memory of our computers. Of course, at some point we'll face physical limits of the hardware: there is only so much memory that can be accessed fast by a single/finitely many processors. One way to go beyond these limits is memory hierarchies and the modeling becomes more complicated, but there is some very nice theory as well (see external memory models and cache-oblivious algorithms).
> 7 votes

# Answer
For simplicity assume, you don't have 600.000 numbers but only 1. At some time $i$ a certain number of `1`s have been sent. We call this number the *prefix* of the stream. There are infinitely many possible prefixes.

Since there is only a constant size work tape, the TM can have at most a constant number of configurations. Thus, there are at least two different prefixes, that would *lead* to the same configuration. In both cases the TM has to output the same number, for any following request. Hence the TM can not compute the desired function.

I hope this is convincing, although it is not super-formal.
> 5 votes

---
Tags: regular-languages, turing-machines, finite-automata, space-complexity, streaming-algorithm
---


# Question
Title: Generating inputs for random-testing graph algorithms?
When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness. Modern testing frameworks can generate inputs automatically given the algorithms signature, with some restrictions.

If the inputs are numbers, lists or strings, generating such inputs in straight-forward. Trees are harder, but still easy (using stochastic context-free grammars or similar approaches).

How can you generate random graphs (efficiently)? Usually, picking graphs uniformly at random is not what you want: they should be connected, or planar, or cycle-free, or fulfill any other property. Rejection sampling seems suboptimal, due to the potentially huge set of undesirable graphs.

What are useful distributions to look at? Useful here means that

* the graphs are likely to test the algorithm at hand well and
* they can be generated effectively and efficiently.

I know that there are many models for random graphs, so I'd appreciate some insight into which are best for graph generation in this regard.

If "some algorithm" is too general, please use shortest-path finding algorithms as a concrete class of algorithms under test. Graphs for testing should be connected and rather dense (with high probability, or at least in expectation). For testing, the optimal solution would be to create random graphs around a shortest path so we *know* the desired result (without having to employ another algorithm).

# Answer
> 16 votes
**Random graphs with small world topology**

In graphs with *small world topology*, nodes are highly clustered yet the path length between them is small. A topology like this can make search problems very difficult, since local decisions quickly propagate globally. In other words, shortcuts can mislead heuristics. Further is has been shown that many different search problems have a small world topology.

Watts and Strogatz \[1\] propose a model for small world graphs. First, we start with a regular graph. Disorder is introduced into the graph by randomly rewiring each edge with probability $p$. If $p=0$, the graph is completely regular and ordered. If $p=1$, the graph is completely random and disordered. Values of $0 \< p \< 1$ produce graphs that are neither completely regular nor completely disordered. Graphs don't have a small world topology for $p=0$ and $p=1$.

Watts and Strogatz start from a ring lattice with $n$ nodes and $k$ nearest neighbours. A node is chosen from the lattice uniformly at random, and a rewired edge is reconnected to it. If rewiring would create a duplicate edge, it is left untouched. For large, sparse graphs they demand $n \gg k \gg \ln(n) \gg 1$, where $k \gg \ln(n)$ ensures the graph remains connected.

The model of Watts and Strogatz is somewhat popular, but does have certain drawbacks. Walsh \[2\] investigates the effects of randomization and restart strategies in graphs generated using the model. There's also a paper by Virtanen \[3\], which covers other models motivated by the need of realistic modeling of complex systems.

**Random simple planar graphs**

Generating random simple planar graphs on $n$ vertices uniformly at random can be done efficiently. The number of planar graphs with $n$ vertices, $g\_n$, can be determined using generating functions. The value of $g\_n$ for $1 \leq n \leq 9$ is $1,2,8,64,1023,32071,1823707,163947848$ and $20402420291$, respectively. Since the numbers are too complicated, one is not expected to find a closed formula for them. Giménez and Noy \[4\] give a precise asymptotic estimate for the growth of $g\_n$: $$g\_n \sim g \cdot n^{-7/2} \gamma^n n!,$$ where $g$ and $\gamma$ are constants determined analytically with approximate values $g \approx 0.42609$ and $\gamma \approx 27.22687$.

The proof of the result leads to a very efficient algorithm by Fusy \[5\]. Fusy gives an approximate size random generator and also a exact size random generator of planar graphs. The approximate size algorithm runs in linear time while the exact size algorithm runs in quadratic time. The algorithms are based on decomposition according to successive levels of connectivity: planar graph $\rightarrow$ connected $\rightarrow$ 2-connected $\rightarrow$ 3-connected $\rightarrow$ binary tree.

The algorithms then operate by translating a decomposition of a planar graph into a random generator using the framework of Boltzmann samplers by Duchon, Flajolet, Louchard and Schaeffer \[6\]. Given a combinatorial class, a Boltzmann sampler draws an object of size $n$ with probability to $x^n$, where $x$ is certain real parameter tuned by the user. Furthermore, the probability distribution is spread over all the objects of the class, with the property that objects of the same size have the same probability of occurring. Also, the probability distribution is uniform when restricted to a fixed size.

For a lightweight introduction, see a presentation by Fusy.

---

\[1\] D.J. Watts and S.H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440-442, 1998.

\[2\] Toby Walsh. Search in a small world. Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99-Vol2), pages 1172-1177, 1999.

\[3\] Satu Virtanen. Properties of nonuniform random graph models. Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, 2003.

\[4\] O. Giménez and M. Noy. Asymptotic enumeration and limit laws of planar graphs, arXiv math.CO/0501269. An extended abstract has appeared in Discrete Mathematics and The- oretical Computer Science AD (2005), 147-156.

\[5\] E. Fusy. Quadratic and linear time generation of planar graphs, Discrete Mathematics and Theoretical Computer Science AD (2005), 125-138.

\[6\] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Boltzmann sampler for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 13(4-5):577-625, 2004.

---
Tags: algorithms, graphs, randomness, software-testing
---


# Question
Title: Algorithms for two and three dimensional Knapsack
I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work?

By 2D (3D) Knapsack I mean I have a square (cube) and a I have list of objects, all data are in centimeters and are at most 20m.

# Answer
Knapsack can be solved by dynamic programming in *pseudo-polynomial* time $O(nW)$ with $n$ the number of objects and $W$ the size of the knapsack. So, as long as your container is small (numerically), you can solve the problem efficiently. Note that you can adjust $W$ by changing resolution; no need to measure a shipping container to the µm, but meters are probably to coarse (depending on your objects).

Knapsack can also be approximated arbitrarily well in polynomial time (see polynomial-time approximation schemes).

However, Knapsack only considers fitting numbers into another number; it does not care about geometrics. If you need to "puzzle", you need another problem; considering Tetris, this is probably much harder than Knapsack.
> 1 votes

# Answer
GREEDY will always find a reasonable solution, but not necessarily the optimal one. Simply put the largest object which will fit each time in the knapsack. Stop when no more objects will fit.
> 0 votes

---
Tags: algorithms, complexity-theory, np-complete, computational-geometry, knapsack-problems
---


title: Is MAX-SAT NP-hard?

text:
# Question
Title: Is MAX-SAT NP-hard?
Is the MAX-SAT problem NP-hard? From the Wikipedia page:

> The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete

I see that a given SAT problem can be reduced to a MAX-SAT problem: just solve the MAX-SAT problem for the boolean formula to see if all clauses can be satisfied. If yes, the SAT problem has the answer "yes", otherwise "no".

**Question 1:** What confuses me is that we have an optimization problem here, and no decision problem. So, can also optimization problems be considered as NP-hard? It only needs to be shown that the (optimization) problem can be reduced in polynomial-time to the SAT problem (or another NP-hard problem)?

**Question 2:** To reduce the SAT problem to MAX-SAT, we have to find a function $f$, which is computable in polynomial time, and with $p \text{ in } \text{SAT} \Leftrightarrow f(p) \text{ in } \text{MAX-SAT}$.

This is the definition I know about reduction. But here, we clearly can not find such a function $f$ since MAX-SAT is not a decision problem. How can a reduction be shown here?

# Answer
The decision problem related to MAX-SAT is, given a formula $\phi$ and a number $k$, decide whether there is an assignment satisfying at least $k$ of the clauses. This is clearly NP-hard since it can be used to solve SAT, and on the other hand, also in NP, since it is easy to verify the properties of a good assignment. Hence it is NP-complete.
> 9 votes

---
Tags: complexity-theory, reductions
---


title: Semantic similarity in text

text:
# Question
Title: Semantic similarity in text
Is there a relatively simple way of telling if two pieces of text are semantically similar?

Some assumptions that are valid:

* It is all english
* I have a list of all the *important* nouns

Are there any strategies that I should pursue? Looking for something that is relatively computationally cheap, though something that could be scaled to improve accuracy at the expense of computational power would be a bonus.

**Note:**

Assume that there are not enough posts for some type of probabilistic analysis, but some type of NN might be feasible (I think, just don't know enough about it).

# Answer
> 4 votes
Here's a simple technique.

Train an LDA using something like MALLET over your collection of texts. For each pair of documents you want to compare, obtain the topic distributions and compute the Hellinger distance between them.

Things you can tweak include term weighting, the LDA hyperparameters, and the metric for comparing distributions. Term weighting would obviate both the need for a list of important words, and the restriction to only English.

---
Tags: algorithms, natural-language-processing, ontologies
---


title: Period in postulate; what does it mean?

text:
# Question
Title: Period in postulate; what does it mean?
While I am learning a lot from others here at the Computer Science site, I must admit that I don't get as much out of some questions and answers since I typically don't understand the theorems to the level necessary. I am currently reading How To Prove It - A Structured Approach which is starting to make the theorems easier to read, but still does not get me to the point of being able to understand the theorems to the point that they add great insight to the question or answer.

For this question Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

there is a use of a peroid in the premise.

> $\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\\, c \in V. a \leq c \land c \leq b\right)$

What does the period mean? I would be expecting either a comma to mean conjuction or or to mean disjunction, but not a period. I don't see how this could be converted to logical statements.

Note: Jukka Suomela has already provided the answer in this CS meta question.

# Answer
After an $\exists$ the period can be read as "such that". For example, $\exists x\in \mathbb{N}. x\>4$ can be read as "there exists a natural $x$ such that $x$ is greater than 4."

After a $\forall$ it can be read as "it is the case that". For example, $\forall x\in\mathbf{N}. x + 1\> x$ can be read as "for all natural numbers $x$, it is the case that $x+1$ is greater than $x$.

Generally one can omit "it is the case that" and the sentence still works.
> 7 votes

---
Tags: terminology, logic
---


# Question
Title: Example using Penetrance & Branching Factor in State-space Heuristic Search
I need an example for how to calculate penetrance and branching factor of the search tree in in state-space heuristic search. The definitions are as following. *Penetrance* $P$ is defined by

$\qquad \displaystyle P = \frac{L}{T}$

and *branching factor* $B$ is defined by

$\qquad \displaystyle \frac{B}{(B-1)} \cdot (B^L – 1) = T$

where $L$ is the length of the path from the root to the solution and $T$ the total number of nodes expanded.

# Answer
Consider the following search tree. Your heuristic search algorithm starts the search at the root node. Unexpanded nodes are marked gray.

For some reason, the heuristic is being guided towards the left-most subtree, when in fact the goal node is in the right-most subtree, marked with green.

Nodes that have been expanded are marked red. After the appealing left-most subtree turned out to be a dead-end, the heuristic is now luckily being guided directly towards the goal. From the situation of the previous figure, we'll expand a total of three new nodes before arriving at the goal.

From the figure above, the length of the path to the goal is $3$. There are $17$ expanded nodes. Therefore, the **penetrance** is $3/17 \approx 0.43$.

The **branching factor** is the maximum number of successors of any node. For example, the branching factor of a binary tree is $2$ since each node has at most two children. Likewise, in the above search tree the branching factor is $3$.

What you seem to be interested in is not the branching factor, but the **effective branching factor** $B^\*$ which is a way to characterize the quality of a heuristic. If the total number of expanded nodes is $T$, and the length of the path to the goal is $L$ (this is more commonly known as *depth*), then $B^\*$ is the branching factor that a uniform tree of depth $L$ would have in order to contain $T+1$ nodes. Therefore,

$$T+1 = 1 + B^\* + (B^\*)^2 + \cdots + (B^\*)^L.$$

If you plug-in the values we obtained in search, that is, $T=17$ and $L=3$, you get $B^\* \approx 2.165$. This is exactly the same value you get from using your equation; it's just merely a different representation for the same thing.

The effective branching factor can vary across instances, but is somewhat constant for hard enough problems. A well-designed heuristic would have a value of $B^\*$ close to $1$, allowing fairly large problems to be solved reasonable cheaply.
> 4 votes

---
Tags: artificial-intelligence, search-algorithms
---


# Question
Title: Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.
The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing

$\qquad \begin{align\*} T(n) & \leq 2(c \lfloor n/2 \rfloor ) + n \\ &\leq cn +n \\ &=O(n) \quad \quad \quad \longleftarrow \text{ wrong!!} \end{align\*}$

since $c$ is constant.The error is that we have not proved the *exact* form of the inductive hypothesis.

Above I have exactly quoted what the book says. Now my question is why cannot we write $cn+n=dn$ where $d=c+1$ and now we have $T(n) \leq dn$ and hence $T(n) = O(n)$?

Note:

1. The correct answer is $T(n) =O(n \log n).$
2. The book I am referring here is *Introduction to algorithms* by Cormen et al., page 86, 3rd edition.

# Answer
> 7 votes
The authors give the answer:

> The error is that we have not proved the *exact form* of the inductive hypothesis, that is, that $T(n) \leq cn$.

Granted, that is hard to understand if you are not used to do inductions (right), because they do not do the induction explicitly/rigorously. In short: you need to have *one* constant $c$ for all $n$, but this (un)proof constructs many (one per $n$).

---

In long, remember what $T(n) \in O(n)$ means:

$\qquad \displaystyle \exists c \in \mathbb{N}.\\, \exists n\_0 \in \mathbb{N}.\\, \forall n \geq n\_0.\\, T(n) \leq cn$

or, equivalently,

$\qquad \displaystyle \exists c \in \mathbb{N}.\\, \forall n \in \mathbb{N} T(n) \leq cn$.

The second form works better for an induction as you know the anchor. So you need *one* constant $c$ that provides an upper bound for *all* $n$.

Let's inspect what the induction does:

* Induction anchor: The anchor of $T$ is not explicitly given, but it's constant, so we find a suitable $c$.
* Induction hypothesis: There is some $c$ so that $T(k) \leq cn$ for all $k\leq n$, for some arbitrary but fixed $n$.
* Inductive step: as shown in the question, construct $d \> c$ so that $T(n+1) \leq dn$.

So, in effect, we construct a *new* constant for every $n$. That does not fit the definition of $O$ at all! And, worse, it is completely meaningless: *every* function can be "bounded" by *any other* function if you can adjust the factor with $n$.

Regarding the induction proof, $c$ has to be part of the claim (and it is, hidden in the $O$), that is bound "outside" of the induction. Then, the same $c$ shows up in anchor, hypothesis and step. See the last part of this answer for an example.

---
Tags: proof-techniques, asymptotics, recurrence-relation, landau-notation, induction
---


title: Inferring refinement types

text:
# Question
Title: Inferring refinement types
At work I’ve been tasked with inferring some type information about a dynamic language. I rewrite sequences of statements into nested `let` expressions, like so:

```
return x; Z            =>  x
var x; Z               =>  let x = undefined in Z
x = y; Z               =>  let x = y in Z
if x then T else F; Z  =>  if x then { T; Z } else { F; Z }

```

Since I’m starting from general type information and trying to deduce more specific types, the natural choice is refinement types. For example, the conditional operator returns a union of the types of its true and false branches. In simple cases, it works very well.

I ran into a snag, however, when trying to infer the type of the following:

```
function g(f) {
  var x;
  x = f(3);
  return f(x);
}

```

Which is rewritten to:

```
\f.
  let x = undefined in
    let x = f 3 in
      f x

```

HM would infer $\mathtt{f} : \mathtt{Int} \to \mathtt{Int}$ and consequently $\mathtt{g} : (\mathtt{Int} \to \mathtt{Int}) \to \mathtt{Int}$. The actual type I want to be able to infer is:

$$\mathtt{g} : \forall \tau\_1 \tau\_2. \\:(\mathtt{Int} \to \tau\_1 \land \tau\_1 \to \tau\_2) \to \tau\_2$$

I’m already using functional dependencies to resolve the type of an overloaded `+` operator, so I figured it was a natural choice to use them to resolve the type of `f` within `g`. That is, the types of `f` in all its applications together uniquely determine the type of `g`. However, as it turns out, fundeps don’t lend themselves terribly well to variable numbers of source types.

Anyway, the interplay of polymorphism and refinement typing is problematic. So is there a better approach I’m missing? I’m currently digesting “Refinement Types for ML” and would appreciate more literature or other pointers.

# Answer
> 9 votes
You've stumbled on the fact that inference of static invariants for higher-order languages is quite difficult in practice, in addition to being undecidable in theory. I'm not sure what the definitive answer to your question is, but note several things:

* Polymorphism and refinement types behave poorly together, as you have noted, in particular the notion of most general type is lost. A consequence of this is that analyses based on refinement types in the presence of polymorphism may need to chose between whole-program analysis (as opposed to compositional analysis) and the use of heuristics to decide which type you want to assign to your program.
* There is a strong relationship between inferring refinement types and:

1. Computing the abstract interpretation of your program
    2. Computing loop invariants in an imperative language.

With this in mind, here are a few disorganized references on the inference of refinement types. Note that there are many differing flavors of refinement types: I tend to be more interested in refinements of inductive datatypes, so this list may be skewed in that direction.

1. Start with the classics: Relational Abstract Interpretation of Higher-Order Functional Programs by Cousot & Cousot. This explains how to extend abstract interpretation to higher-order programs using relational semantics.
2. Liquid Types by Rhondon, Kawaguchi and Jhala. This is very evolved work, that combines HM and a type of predicate refinement to infer security annotations (array bound checks for instance) for ML style programs. The inference proceeds in 2 steps; the first is HM inference of type annotations, which guide the choice of refinements to perform.
3. I should probably also mention the work by Fournet, Swarmy, Chen, Strub... on $F^\*$, an extension of $F^\\#$ which seems similar to the liquid types approach, but with the goal of verifying cryptographic protocols and algorithms for distributed computing. I'm not sure how much published work there is on the inference of annotations in this case.
4. There is a nice paper by Chin and Khoo on inference of a specific kind of refinement types: types with size annotations.
5. The ATS programming language is a system which allows various refinements and provides facilities for writing programs with them. However the annotations may be arbitrarily complex (and thus undecidable) and therefore may require user interaction. I believe that there is a form of inference for these types, I'm not sure which article to recommend however.
6. Last, but not least The Cartesian Product Algorithm, by Ole Agesen. While not mentioning refinement types explicitly, this seems to be the work closest to solving the problem you seem to have. Don't be fooled by the mention of parametric polymorphism in the abstract: they look to infer *concrete types*, which are just tuples of possible atomic types. Emphasis is given on efficiency. I recommend reading this article first to see if it solves your problem.

Side note: type inference in the presence of intersection types can be very undecidable: in the simplest form, $\lambda$-terms with intersection type are exactly the strongly normalizing terms. Tread softly around them :)

---
Tags: programming-languages, logic, type-theory, type-inference
---