17 views

Skip to first unread message

Oct 6, 2006, 2:19:30 PM10/6/06

to caml...@inria.fr

Bonjour,

I would like the type-checker to infer the type inside exceptions (or

at least to help me in the "guess a type and test" loop).

More specifically, here is my problem:

I have a program that computes the optimal solution of the minimal

cardinality subset-sum problem with multiplicities. In simple words it

gives the minimum number of coins you need to reach a given amount of

money.

val smc : int -> int list -> int list list * int = <fun>

# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;

- : int list list * int =

([[75; 75; 75; 1]; [122; 64; 10; 10; 10; 10]; [198; 10; 10; 5; 1; 1; 1]],

198105)

The programs gives all the solutions it found, the last one being the

optimal (with the total number of backtracks). The best solution is

kept by side-effects on a global variable.

type environment = {

mutable solutions : int list list;

mutable backtracks : int;

mutable card : int

}

exception Fail

let rec min_card env = fun to_reach chosen candidates ->

if (to_reach = 0) then

match compare env.card (List.length chosen) with

| n when n <= 0 ->

env.backtracks <- env.backtracks + 1;

raise Fail

| _ ->

env.solutions <- chosen :: env.solutions;

env.card <- List.length chosen;

raise Fail

else

match candidates with

| [] ->

env.backtracks <- env.backtracks + 1;

raise Fail

| x :: tail when x > to_reach -> min_card env to_reach chosen tail

| x :: tail ->

try

min_card env (to_reach - x) (x :: chosen) candidates

with Fail ->

min_card env to_reach chosen tail

let rec smc = fun to_reach list ->

let env = { solutions = []; backtracks = 0; card = max_int } in

try

min_card env to_reach [] (List.sort (fun x y -> compare y x) list)

with Fail -> (List.map List.rev env.solutions, env.backtracks)

Now I want the program not to return all the solutions but only the

first solution it found and a list of continuations that I can launch

again if a better solution is required.

Therefore I add a second exception

type continuation = ...

exception Solution of int * continuation list

And I collect the continuations from the try ... catch when the left

tree happens to contain a solution

try

explore left subtree

with

| Fail -> explore right subtree

| Solution (s, cont) ->

let c = function () -> explore right subtree in

raise Solution (s, c :: cont)

Not knowing the type of the continuation, I just tried unit -> int

Here is the detailed code

type continuation = unit -> int

exception Solution of int * continuation list

let rec min_card env = fun to_reach chosen candidates ->

if (to_reach = 0) then

match compare env.card (List.length chosen) with

| n when n <= 0 ->

env.backtracks <- env.backtracks + 1;

raise Fail

| _ ->

env.solutions <- chosen :: env.solutions;

env.card <- List.length chosen;

raise (Solution (List.length chosen, []))

else

match candidates with

| [] ->

env.backtracks <- env.backtracks + 1;

raise Fail

| x :: tail when x > to_reach -> min_card env to_reach chosen tail

| x :: tail ->

try

min_card env (to_reach - x) (x :: chosen) candidates

with

| Fail -> min_card env to_reach chosen tail

| Solution (s, continuation) ->

let c = fun () -> min_card env to_reach chosen tail in

raise (Solution (s, (c :: continuation)))

I first wrap without catching the exceptions and test

let smc = fun to_reach list ->

let env = { solutions = []; backtracks = 0; card = max_int } in

min_card env to_reach [] list

# val smc : int -> int list -> int = <fun>

# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;

Exception: Solution (7, [<fun>; <fun>; <fun>; <fun>; <fun>; <fun>; <fun>]

Seems correct.

Now I try to extract the integer

let smc = fun to_reach list ->

try

let env = { solutions = []; backtracks = 0; card = max_int } in

min_card env to_reach [] list

with Solution (c, l) -> c

# val smc : int -> int list -> int = <fun>

# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;

- : int = 7

Correct.

Now I try to extract the continuation list

let smc = fun to_reach list ->

let env = { solutions = []; backtracks = 0; card = max_int } in

try

min_card env to_reach [] list

with Solution (c, l) -> l

This expression has type continuation list but is here used with type int

Ok. I have to correct the type of continuation by hand

lets try [type continuation = unit -> (unit -> int)]

This expression has type continuation list but is here used with type

unit -> int

lets try [type continuation = Cont of (unit -> continuation)]

and [let c = Cont (fun () -> ... ) in raise Solution (s, c :: cont)]

This expression has type continuation list but is here used with type

continuation

lets try [type continuation = Cont of (unit -> continuation list)]

# val smc : int -> int list -> continuation list = <fun>

# smc 226 [198; 122; 90; 75; 64; 54; 53; 10; 5; 1];;

- : continuation list =

[Cont <fun>; Cont <fun>; Cont <fun>; Cont <fun>; Cont <fun>; Cont <fun>;

Cont <fun>]

Great ! Now I want the solution, its cardinality and the continuation list

lets try ...

Diego Olivier

_______________________________________________

Caml-list mailing list. Subscription management:

http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list

Archives: http://caml.inria.fr

Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Bug reports: http://caml.inria.fr/bin/caml-bugs

Oct 6, 2006, 4:23:44 PM10/6/06

to caml...@inria.fr

On 10/6/06, Diego Olivier FERNANDEZ PONS <diego.fern...@etu.upmc.fr>

wrote:

wrote:

> I would like the type-checker to infer the type inside exceptions (or

> at least to help me in the "guess a type and test" loop).

I'd like it to infer the types of record-fields as well :)

Oct 10, 2006, 6:37:10 AM10/10/06

to ketty .

Quoting "ketty ." <kattl...@gmail.com>:

>> I would like the type-checker to infer the type inside exceptions (or

>> at least to help me in the "guess a type and test" loop).

>

> I'd like it to infer the types of record-fields as well :)

WISH GRANTED.

type ('a, 'b, 'c) environment = {

mutable solutions : 'a;

mutable backtracks : 'b;

mutable objective : 'c

}

let min_card = fun env ... -> ...

# val min_card :

(int list list, int, int) environment ->

int -> int list -> int list -> int list * int list continuation list =

<fun>

The typechecker inferred the type of your record-fields.

Polymorphic exceptions are forbidden because they could break the type

system, leading to a ['a -> 'b] type. That is why I asked for "type

inference" or any kind of useful help and not for "polymorphic

exceptions". I would accept the compiler to deny the use of the

exception if it is not monomorphic.

Oct 11, 2006, 6:54:37 PM10/11/06

to Diego Olivier FERNANDEZ PONS

Diego Olivier FERNANDEZ PONS a écrit :

> Now I want the program not to return all the solutions but only the

> first solution it found and a list of continuations that I can launch

> again if a better solution is required.

> Now I want the program not to return all the solutions but only the

> first solution it found and a list of continuations that I can launch

> again if a better solution is required.

I don't really understand what you are doing: why do you generate a list

of continuations instead of a single one? Don't you want a kind of lazy

list?

> Here is the detailed code

> [...]

> Great ! Now I want the solution, its cardinality and the continuation list

Does this code really do what you expect? Did you take into

consideration multiple executions of your continuations? I am rather

unconfident with your single mutable variable...

> lets try ...

Is this the end of your mail?

--

Stephane Glondu

Oct 13, 2006, 8:27:38 AM10/13/06

to Stéphane Glondu

Bonjour,

Quoting Stéphane Glondu <st...@glondu.net>:

> I don't really understand what you are doing: why do you generate a list

> of continuations instead of a single one?

Reordering the continuations to continue the computation in an other

branch than the deepest try ... fail is a classical technique in

combinatorial optimization. The way you order your continuations

defines a "node ordering strategy", most usual being :

- stack -> depth first search

- queue -> limited discrepancy search

- priority queue -> best first search

> Don't you want a kind of lazy list?

I first wrote a code that solves the problem completely.

Then I modified the code to handle continuations of the form (unit ->

somthing)

Then I replaced (unit -> something) with a lazy list

Finally I kept the list of continuations but send it back by function

return instead of an exception [And type inference DOES work in that

case !]

I am "complaining" because the compile DOES infer types within

exceptions but does not allow you to let him fix the type the way he

needs. It only says "It is not what I was expecting, so your function

won't compile, sorry".

As far as I understand the reason is to avoid polymorphic exceptions

but this could have been done just forbidding the final result to be

polymorphic or typechecking and not compiling, or giving me a way to

just typecheck without creating the value.

> Does this code really do what you expect?

Reasonably

>> lets try ...

>

> Is this the end of your mail?

Unless you want a complete log of everything I tried when developping

that code...

Diego Olivier

Oct 13, 2006, 8:46:51 AM10/13/06

to caml...@yquem.inria.fr, caml...@inria.fr

On Fri, Oct 13, 2006 at 02:23:17PM +0200, Diego Olivier FERNANDEZ PONS wrote:

> Quoting St??phane Glondu <st...@glondu.net>:

> >I don't really understand what you are doing: why do you generate a list

> >of continuations instead of a single one?

> Reordering the continuations to continue the computation in an other

> branch than the deepest try ... fail is a classical technique in

> combinatorial optimization. The way you order your continuations

> defines a "node ordering strategy", most usual being :

> - stack -> depth first search

> - queue -> limited discrepancy search

> - priority queue -> best first search

> Quoting St??phane Glondu <st...@glondu.net>:

> >I don't really understand what you are doing: why do you generate a list

> >of continuations instead of a single one?

> Reordering the continuations to continue the computation in an other

> branch than the deepest try ... fail is a classical technique in

> combinatorial optimization. The way you order your continuations

> defines a "node ordering strategy", most usual being :

> - stack -> depth first search

> - queue -> limited discrepancy search

> - priority queue -> best first search

Can you give some pointer about this technique ... I guess I've already

seen/used it, but maybe in disguise... is this related with delimited

continuations and some kind of lookahead technique to detect failures

and backtrack ?

thanks!

:)

p

--

++ Blog: http://blog.rsise.anu.edu.au/?q=pietro

++

++ "All great truths begin as blasphemies." -George Bernard Shaw

++ Please avoid sending me Word or PowerPoint attachments.

See http://www.fsf.org/philosophy/no-word-attachments.html

Oct 14, 2006, 4:01:41 PM10/14/06

to Pietro Abate

Quoting Pietro Abate <Pietro...@anu.edu.au>:

>> Reordering the continuations to continue the computation in an other

>> branch than the deepest try ... fail is a classical technique in

>> combinatorial optimization. The way you order your continuations

>> defines a "node ordering strategy", most usual being :

>> - stack -> depth first search

>> - queue -> limited discrepancy search

>> - priority queue -> best first search

>

> Can you give some pointer about this technique ... I guess I've already

> seen/used it, but maybe in disguise... is this related with delimited

> continuations and some kind of lookahead technique to detect failures

> and backtrack ?

This topic is shared by a lot of domains including combinatorial

optimization [linear (integer) programming, constraint programming,

dedicated algorithms], automatic theorem proving [SAT and related],

incremental computation [self-adjusting algorithms], functional

programming, data structures, etc.

I will divide my answer in several parts :

1. Relation with (limited) continuations

2. Reordering continuations

3. Implementing reversibility : copying vs trailing

1. Relation with (limited) continuations

Basically, you did a computation (e.g. computed some shortest path),

where you used the fact that x = 2 and you want to go back to a previous

state where x != 2 because :

- not knowing the value of x, you did the hypothesis x = 2 and now

want to try its negation [implicit enumeration algorithms]

- the data of you program changed and now x = 3 [self adjusting

algorithms]

- any other reason (e.g. debugging)

In combinatorial optimization, we call this REVERSIBILITY (talk about

its links with persistence later).

Unlike (delimited) continuations, you don't need to go back to any

possible previous state but only to specific points. These points are

named CHOICE POINTS and can only be placed on some "events" which is

the minimum granularity of your backtracking algorithm.

This is similar to the Caml debugger (events and jumps).

Programming languages for combinatorial optimization integrate some

facilities to declare choice points (in other words continuation

"holes") and provide a set of possible events on

DECISION VARIABLES (typically when the domain of the variable changes).

All this is then translated by the underlying algorithm to a low-level

implementation that can use several techniques (call/cc, exceptions,

persistence, reified continuations, etc.)

Example: OPL (The Optimization Programming Language, Pascal van Hentenryck

MIT Press 1996) introduces two constructions [dvar] and [try] that

allows you to write (simplified syntax)

dvar x [0..3] // possible events

dvar y [0..3] // possible events

subject to

x + y == 2

search

forall v in x, try (x == v) // continuation holes

Compare this with a much more complex continuation framework

integrated to a general purpose language like

R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry:

A Monadic Framework for Delimited Continuations

I can now answer to the first question

> is this related with delimited continuations

Yes but I would say that we use these techniques (continuations,

persistent data structures, backtracking monads, exceptions) more

than contribute to their study.

2. Reordering continuations

In an implicit enumeration algorithm, all the possible continuations

have to be visited (that is the "enumeration" part of the name) but

some orders may be better than others because one accumulates

information while visiting the continuations and this allow the

algorithm to prove that visiting some continuations is useless (that

is the "implicit" part of the name).

Usually you have for an optimization problem:

- a global lower and upper bound (that improves while the algorithm

runs)

- local lower and upper bounds (that depend on your position in the

tree, in other words the sequence of decision that have been take to

arrive to that point e.g. x1 == 0, x2 == 3, y3 == 0, all other

unknown).

If you are minimizing, and the local lower bound is already higher

than the global upper bound, you can prune all the branch. All those

continuations won't be visited.

There are tons of search strategies according to the type of problem

you are solving. They all combine

- a variable ordering (this gives the shape to the tree)

- a node ordering (this says how the nodes are visited)

As I said before, the most usual node orderings are depth first,

limited discrepancy and best-first. You will find a good entering

point with the original LDS paper (on the web)

William D. Harvey, Matthew L. Ginsberg

Limited Discrepancy Search (IJCAI 1995)

> Is this related to [...] some kind of lookahead technique to detect

> failures and backtrack ?

I would not call that lookahead but rather using statistical

correlation between the data and the position in the tree of the

optimal solution to find it soon.

3. Implementing reversibility

There are two classical ways to implement reversibility in

combinatorial optimization engines : copy and trailing

A copy engine just maintains a copy of the decision variables for all

opened nodes. When you jump from a node to another, you just have to

select the correct version.

In functional languages, the simplest implementation is combining

recursive calls (and exceptions) with persistent data structures.

Example : Alain Frish's sudoku solver

But some engines written in imperative languages also work that way

Example : Gecode in C++ (Alice is its SML frontend).

In the trailing technique, there is a single state (current state)

that has to be synchronized every time the "focus" is moved in the

search tree. Usually this leads to stamped version arrays data

structures, that save all the local differences in a TRAIL.

Within trailing engines, the state your program would have in another node is

distributed in the central memory. To jump to another node you have to

"replay" the paths in the search tree: you physically undo the

modifications until the lowest common ancestor between the current

node and the desired node and you do again all the "forward" decisions

needed to reach the node.

An example of trailing engine in a functional language is FaCiLe

(Pascal Brisset et Nicolas Barnier, Caml).

An example of trailing for self-adjusting algorithms is given by

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Kanat Tangwongsan.

An Experimental Analysis of Self-Adjusting Computation (PLDI 2006)

The original LDS paper is written supposing that the underlying engine

uses trailing to implement reversibility.

There is also something named "semantic backtracking". To keep it

short, instead of physically restoring the state, you restore it

logically, in other words you change your current state in order to be

semantically equivalent to the state you want to reach.

Imagine a fixed-size queue implemented by an array with a first and

last pointer. Then any "translated" array is semantically equivalent,

so instead of physically restoring the queue you had, you can put the

elements back in a "forward" way.

Pascal Van Hentenryck and Viswanath Ramachandran

Backtracking without trailing in CLP (R) (TOPLAS 1995)

Diego Olivier

Oct 16, 2006, 5:33:15 AM10/16/06

to Pietro Abate

Bonjour,

Here is some code that shows the effect of reordering continuations in

a combinatorial problem. The first one is the minimum cardinality

subset-sum problem, the second returns the order in which the leaves

of the search tree are visited.

Each time a solution is found, the number of failures is printed. This

gives an idea of how much time was spent to find the solution.

(* subsetsum in depth first search *)

# let p = smc 47 [39;32;20;19;16;9;1] in solve p (new stack);;

0 fails : 39 1 1 1 1 1 1 1 1

8 fails : 32 9 1 1 1 1 1 1

47 fails : 20 16 9 1 1

61 fails : 20 9 9 9

118 fails : 19 19 9

- : int list list * int =

([[39; 1; 1; 1; 1; 1; 1; 1; 1]; [32; 9; 1; 1; 1; 1; 1; 1]; [20; 16; 9; 1; 1];

[20; 9; 9; 9]; [19; 19; 9]],

457)

(* subset sum in limited discrepancy search *)

# let p = smc 47 [39;32;20;19;16;9;1] in solve p (new queue);;

0 fails : 39 1 1 1 1 1 1 1 1

0 fails : 32 9 1 1 1 1 1 1

16 fails : 19 19 9

- : int list list * int =

([[39; 1; 1; 1; 1; 1; 1; 1; 1]; [32; 9; 1; 1; 1; 1; 1; 1]; [19; 19; 9]], 459

The second example builds a tree which leaves are labelled from 0 to

2^n - 1 from left to right. The order in which the leaves are visited

is returned.

# let p = label 4 in solve p (new stack);;

- : int list * int =

([0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15], 0)

# let p = label 4 in solve p (new queue);;

- : int list * int =

([0; 8; 4; 2; 1; 12; 10; 9; 6; 5; 3; 14; 13; 11; 7; 15], 0)

Here is the complete code

class type ['a] continuationQueue =

object

method push : 'a -> unit

method pop : 'a

method is_empty : bool

method length : int

end

class ['a] queue =

(object

val contents = (Queue.create () : 'a Queue.t)

method push = fun x -> Queue.push x contents

method pop = Queue.pop contents

method is_empty = Queue.is_empty contents

method length = Queue.length contents

end : ['a] continuationQueue)

class ['a] stack =

(object

val contents = (Stack.create () : 'a Stack.t)

method push = fun x -> Stack.push x contents

method pop = Stack.pop contents

method is_empty = Stack.is_empty contents

method length = Stack.length contents

end : ['a] continuationQueue)

type 'a environment = {

mutable backtracks : int;

mutable objective : int;

mutable queue : 'a queue

}

exception Fail

type 'a continuation = Cont of (unit -> 'a)

let rec print_list = function

| [] -> print_newline()

| x :: tail -> print_int x; print_string " "; print_list tail

let rec min_card env = fun to_reach chosen candidates ->

if (to_reach = 0) then

match compare env.objective (List.length chosen) with

| n when n <= 0 ->

env.backtracks <- env.backtracks + 1;

raise Fail

| _ ->

env.objective <- List.length chosen;

print_int env.backtracks;

print_string " fails : ";

print_list (List.rev chosen);

(List.rev chosen)

else

match candidates with

| [] ->

env.backtracks <- env.backtracks + 1;

raise Fail

| x :: tail when x > to_reach -> min_card env to_reach chosen tail

| x :: tail ->

let c = Cont (fun () -> min_card env to_reach chosen tail) in

env.queue#push c;

min_card env (to_reach - x) (x :: chosen) candidates

let smc = fun to_reach list ->

function env ->

let c = Cont (function () -> min_card env to_reach [] list) in

env.queue#push c; env

let rec label_nodes env = fun count remaining_depth ->

match remaining_depth with

| 0 -> count

| n ->

let c = Cont (fun () -> label_nodes env (2 * count + 1) (n - 1)) in

env.queue#push c;

label_nodes env (2 * count) (n - 1)

let label = function depth ->

function env ->

let c = Cont (fun () -> label_nodes env 0 depth) in

env.queue#push c; env

let rec solve_rec = function env ->

if env.queue#is_empty then []

else

let Cont c = env.queue#pop in

try

let s = c () in

s :: solve_rec env

with Fail -> solve_rec env

let solve = fun f queue ->

let env = { backtracks = 0; objective = max_int; queue = queue } in

let solutions = solve_rec (f env) in

(solutions, env.backtracks)

Oct 17, 2006, 8:42:03 AM10/17/06

to Francisco José Valverde Albacete

Bonjour,

I am not sure I understood all of your comments but I can at least answer

to a few of them

[Francisco Valverde a écrit]

> It is also the technique to find alternative recognition hypotheses

> in most speech recognizers (hypothesis graph search with dynamical

> reordering & pruning of nodes & backtrack, in a nutshell).

Parsers and combinatorial optimization engines are equivalent in the

sense that for every combinatorial problem you can find a grammar and

a string which solutions are the solutions of the combinatorial

problem (think of Prolog) and reciprocally under some reasonable

hypothesis. This is true for anything that gets close to NP-completeness

but in this case both problems are really closely related.

Parsing Techniques explain how to compile a non-deterministic stack automaton

(e.g. an LR grammar with conflicts, an ambiguous grammar) to an

exception based implicit enumeration algorithm (i.e. a recursive

ascent parser implemented with a set of recursive functions).

Parsing Techniques - A Practical Guide

Dick Grune and Ceriel J.H. Jacobs (1990) on the web

A few years ago I put on my web page a few toy LR parser written in

that way and an Early parser (in which continuations reified to lists

are executed in a breath-first-search way and is some sense memoized).

There are working parsers that use this technique, including

- Frown, an LALR(k) parser generator for Haskell

Ralf Hinze, Ross Paterson

- The Essence parser generator for Scheme

Mike Sperber (uses partial evaluation instead of code generation)

Both come with interesting papers.

The general idea is that the definition of the search space

(construction of a stack automaton) and its exploration (optimistic -> depth

first search = LR, pessimistic -> breath first search = Earley) are

two orthogonal things.

The Tomita parsers are a bit more difficult since they are equivalent to

a form of memoization inside an implicit enumeration algorithm (or

conversely a form of duplication at ambiguous points inside a

deterministic algorithm).

Speech recognition is a more complicated because of uncertainty but it

is the same idea.

> Explicit management of the continuation queue/stack/whatever is a

> boon I didn't expect, though! If you come up with a library or

> modular solution please let me know.

It is rather specific to constraint programming but there is a paper that

describes a system that allows you to specify in a declarative way the

order in which the continuations will be executed. The trick is to

lift the combinatorial engine to the search tree: the execution order

of the continuations is itself a combinatorial program (I believe they

do not bootstrap the solver however but use an ad-hoc mini-solver instead).

ToOLS: A Library for Partial and Hybrid Search Methods (2003)

Simon de Givry, Laurent Jeannin

Proceedings CPAIOR '03 (on Citeseer)

It is only applicable when the continuations are restricted enough to

carry a clear semantics. If you are looking for more low-level things

you should have a look to Oleg's work, and related papers.

Native delimited continuations in (byte-code) OCaml

http://okmij.org/ftp/Computation/Continuations.html#caml-shift

> I'm looking forward to hearing more about your research, as always.

Well I can at least explain what I have been trying to do ultimately

with continuations and memoization.

Pisinger introduced a very fast class of algorithms for knapsack

problems which are an hybridisation of implicit enumeration (branch and

bound) and dynamic programming.

Knapsack Problems

Hans Kellerer, Ulrich Pferschy, David Pisinger

Springer 2004

[Good overview : New trends in exact algorithms for the 0-1 knapsack

problem. EJOR 123 (2000), on the web]

I want to automatically derive similar algorithms from any implicit

enumeration algorithms thanks to memoization.

There is an additional problem related to combinatorial optimization:

computing an average solution (50% of the optimum) takes 1s,

a good solution (90%) 1 minute, an excellent solution (99%) 1 hour,

the optimal solution 1 day, and the optimality proof 1 week.

But you usually don't need the optimal solution to a subproblem, only

a good enough "lower bound" that enables you either to cut the branch

or to decide to dive in it.

- From the memoization point of view, one has to generalize the

value table to a improving pair of bounds + continuation stack

instead of memo : (int -> int) -> int -> int

you need memo : (int -> int * continuation queue) -> (int, int) ref *

continuation queue

if you want the confidence interval [lower bound..upper bound] of a

subproblem to be refined, you just execute a few more continuations.

- From the implicit enumeration point of view, one has to order the

continuations in a "structured stack" where the continuations are

indexed by the sub-problems they are solving, and add a cache.

You also need to use the relations between the subproblems: the

optimal solution of a more constrained problem is an upper bound of

the optimal solution of a less contrained problem.

For instance:

min cardinality subsetsum 15 [17;13;7;5;2] == 2

min cardinality subsetsum 15 [17;15;13;12;11;7;5;2;1] == 1

This gives you upper and lower bounds form the keys of the table and

the cached partial results.

I had the idea when reading papers on adaptive functional programming,

specially those of U. Acar (http://ttic.uchicago.edu/~umut/papers/index.html)

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Kanat Tangwongsan.

An Experimental Analysis of Self-Adjusting Computation (PLDI 2006)

Diego Olivier

Oct 19, 2006, 3:39:02 AM10/19/06

to caml...@yquem.inria.fr

Hello

I look for references to usage of ocaml in Data Mining, Knowleadge

Discovery. Inductive Logic Programming, Vector support Machines and

related topics. I have browsed the net but entries are sparse.

I would like to try using Ocaml in these areas and want to avoid

double work.

Axel

------------------------------------------------------------------------

-------------------------

Dr.rer.nat. Dipl.Ing.Axel Poigné

Fraunhofer Institut Intelligente Analyse- und Informationssysteme - IAIS

Department Knowledge Discovery

Schloss Birlinghoven

D-53754 Sankt Augustin

Tel.: +49 (0) 2241 14 - 2440

Fax: +49 (0) 2241 14 - 42440

e-Mail: axel....@ais.fraunhofer.de

web: http://www.ais.fraunhofer.de/~ap

------------------------------------------------------------------------

------------------------

Oct 19, 2006, 10:11:48 AM10/19/06

to Dr. Axel Poigné

On 10/19/06, Dr. Axel Poigné <axel....@iais.fraunhofer.de> wrote:

>

> I look for references to usage of ocaml in Data Mining, Knowleadge

> Discovery. Inductive Logic Programming, Vector support Machines and

> related topics. I have browsed the net but entries are sparse.

>

> I would like to try using Ocaml in these areas and want to avoid

> double work.

>

>

> I look for references to usage of ocaml in Data Mining, Knowleadge

> Discovery. Inductive Logic Programming, Vector support Machines and

> related topics. I have browsed the net but entries are sparse.

>

> I would like to try using Ocaml in these areas and want to avoid

> double work.

>

You may have already found AIFAD (Automated Induction of Functions over

Algebraic Datatypes), a symbolic machine learning program, which generalizes

induction of decision trees to structured values, and is pretty efficient

even on large amounts of data. You can find the sources and documentation

here:

It's also available as a Godi-package, which makes it easier to install,

because it depends on other libraries.

We use Lacaml, a fairly complete and convenient binding to BLAS/LAPACK, here

at Jane Street Capital for implementing numeric algorithms to analyse very

substantial amounts of financial data. I unfortunately cannot give you

details about this work. You can get Lacaml through Godi or download it

here:

http://www.ocaml.info/home/ocaml_sources.html#LACAML

Best regards,

Markus

--

Markus Mottl http://www.ocaml.info markus...@gmail.com

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu