这是一个监督学习问题。
我有一个有向无环图（DAG）。每条边都有一个特征向量X，每个节点（顶点）有一个标签0或1。任务是找到一个成本函数w(X)，使得任意一对节点之间的最短路径具有最高的1与0的比例（最小分类错误）。
解决方案必须具有良好的泛化能力。我尝试过逻辑回归，学习到的逻辑函数能够相当准确地预测给定进入边的特征的节点标签。然而，这种方法没有考虑图的拓扑结构，因此在整个图上的解决方案并非最优。换句话说，鉴于上述问题设置，逻辑函数不是一个好的权重函数。
虽然我的问题设置并非典型的二元分类问题设置，但这里有一个很好的介绍：http://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work
这里提供更多细节：
- 每个特征向量X是一个d维的实数列表。
- 每条边都有一个特征向量。也就是说，给定边的集合E = {e1, e2, .. en}和特征向量的集合F = {X1, X2 … Xn}，那么边ei与向量Xi相关联。
- 可以设计一个函数f(X)，使得f(Xi)给出边ei指向标签为1的节点的可能性。我上面提到的通过逻辑回归找到的函数就是一个例子。然而，正如我上面提到的，这样的函数并非最优。
所以问题是：给定图、起始节点和结束节点，如何学习最优的成本函数w(X)，以最大化节点1与0的比例（最小化分类错误）？
回答：
这看起来是一个遗传算法具有极大潜力的问题。如果你将所需的函数定义为例如（但不限于）特征的线性组合（你可以添加二次项，然后是三次项，无限延伸），那么基因就是系数向量。变异器可以只是在一个合理范围内对一个或多个系数进行随机偏移。评估函数只是根据当前变异计算所有节点对的最短路径上1与0的平均比例。在每一代中，选择最佳的几个基因作为祖先，并通过变异形成下一代。重复这一过程，直到得到超级基因。
