Take the 2-minute tour ×

This is a supervised learning problem.

I have a directed acyclic graph (DAG). Each edge has a vector of features X, and each node (vertex) has a label 0 or 1. The task is to find a cost function w(X), so that the shortest path between any pair of nodes has the highest ratio of 1s to 0s (minimum classification error).

The solution must generalize well. I tried logistic regression, and the learned logistic function predicts fairly well the label of a node giving the features of a incoming edge. However, the graph's topology is not taken into account by that approach, so the solution in the whole graph is non-optimal. In other words, the logistic function is not a good weight function given the problem setup above.

Although my problem setup is not the typical binary classification problem setup, here is a good intro to it: http://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work

Here are some more details:

  1. Each feature vector X is a d-dimensional list of real numbers.
  2. Each edge has a vector of features. That is, given the set of edges E = {e1, e2, .. en} and set of feature vectors F = {X1, X2 ... Xn}, then edge ei is associated to vector Xi.
  3. It is possible to come up with a function f(X), so that f(Xi) gives the likelihood that edge ei points to a node labeled with a 1. An example of such function is the one I mentioned above, found through logistic regression. However, as I mentioned above, such function is non-optimal.

SO THE QUESTION IS: Given the graph, a starting node and an finish node, how do I learn the optimal cost function w(X), so that the ratio of nodes 1s to 0s is maximized (minimum classification error)?

share|improve this question
Can you possibly elaborate on what you tried and what you mean by "it doesn't work"? –  carlosdc Nov 5 '12 at 2:16
The graph seems to only have two nodes i.e. node for label 0 and node for label 1 ?! However, those nodes are sepearate and that means that there is no actual graph? Would you elaborate more on your model and selected graph representation? –  soufanom Nov 5 '12 at 18:38
@carlosdc. Ok, I elaborated on my logistic regression approach, which didn't work on my toy data. Thanks. –  Diego Nov 14 '12 at 19:14
That's from the kaggle competition, right? –  Daniel Velkov Nov 14 '12 at 19:23
don't quite understand your question. 1. in your logistic approach, what if a node has two incoming edges, how would your input feature looks like? 2. you said it's a DAG, so when you do the shortest path between any pair of nodes, the path must follow the DAG topology (directed), right? 3. can you elaborate on the cost function and its goal? The current statement does not make sense to me. thanks. –  greeness Nov 14 '12 at 19:56
show 3 more comments

2 Answers

up vote 0 down vote accepted

This looks like a problem where a genetic algorithm has excellent potential. If you define the desired function as e.g. (but not limited to) a linear combination of the features (you could add quadratic terms, then cubic, ad inifititum), then the gene is the vector of coefficients. The mutator can be just a random offset of one or more coefficients within a reasonable range. The evaluation function is just the average ratio of 1's to 0's along shortest paths for all pairs according to the current mutation. At each generation, pick the best few genes as ancestors and mutate to form the next generation. Repeat until the ueber gene is at hand.

share|improve this answer
This is a new and nice idea. But obviously labels (1's and 0's) need to be used to get the evaluation function to work. –  dvail Nov 27 '12 at 1:52
add comment

This is not really an answer, but we need to clarify the question. I might come back later for a possible answer though.

Below is an example DAG.

enter image description here

Suppose the red node is the starting node, and the yellow one is the end node. How do you define the shortest path in terms of

the highest ratio of 1s to 0s (minimum classification error) ?

Edit: I add names for each node and two example names for the top two edges.

It seems to me you cannot learn such a cost function that takes feature vectors as inputs and whose output (edge weights? or whatever) can guide you to take a shortest path toward any node considering the graph topology. The reason is stated below:

  • Let's assume you don't have the feature vectors you stated. Given a graph as above, if you want to find all-pair-shortest-path with respective to the ratio of 1s to 0s, it's perfect to use Bellman equation or more specifically Dijkastra plus a proper heuristic function (e.g., percentage of 1s in the path). Another possible model-free approach is to use q-learning in which we get reward +1 for visiting a 1 node and -1 for visiting a 0 node. We learn a lookup q-table for each target node one at a time. Finally we have the all-pair-shortest-path when all nodes are treated as target nodes.

  • Now suppose, you magically obtained the feature vectors. Since you are able to find the optimal solution without those vectors, how come they will help when they exist?

  • There is one possible condition that you can use the feature vector to learn a cost function which optimize edge weights, that is, the feature vectors are dependent on the graph topology (the links between nodes and the position of 1s and 0s). But I did not see this dependency in your description at all. So I guess it does not exist.

share|improve this answer
Thanks for the example. The shortest path in any graph is frequently specified using a cost function w(.) that assigns a weight to each edge. I am asking how to find a cost function w(X), that depends on the vector of features X at each edge, so that the shortest path based on that weight function maximizes the ratio of 1s to 0s (you can quickly see that there are two paths where that ratio is maximum in your example above). Note, however, that the weight function that I want to find depends on the vector of features at each edge ONLY, and doesn't "know" what the label at each node is. –  Diego Nov 19 '12 at 23:57
"It seems to me you cannot learn such a cost function that takes edge weights as inputs". As I stated several times, the cost function takes feature vectors as inputs, not weights. Now, I am aware of the fact that I can use Dijkstra to find the path that maximizes the 1s to 0s ratio, but that's not the problem. The problem is finding a function that, without using the labels at each node (0 or 1), but only the feature vectors, it assigns weights to edges so that the shortest path has the maximum ratio of 1s to 0s. Please read the problem and understand it before saying it doesn't make sense. –  Diego Nov 20 '12 at 19:30
interesting. Where did you state that without using the labels at each node,but only... in your problem statement??? You even provide a supervised-learning example to show what you have tried, how could you do that without the labels 1 and 0s ... Yes, I don't understand your question, but I dont' think you undertand your own question, at least you did not state the problem in a clear way at the first place. –  greeness Nov 20 '12 at 21:24
That's true, I am just a beginner of supervised learning. I am totally wrong to be here to help. I will shut up. –  greeness Nov 21 '12 at 0:34
add comment

Your Answer


