The Cost of Learning Directed Cuts

author: Thomas Gartner, Fraunhofer IAIS
published: Sept. 5, 2007,   recorded: August 2007,   views: 3030

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Classifying vertices in digraphs is an important machine learning setting with many applications. We consider learning problems on digraphs with three characteristic properties: (i) The target concept corresponds to a directed cut; (ii) the total cost of finding the cut has to be bounded a priori; and (iii) the target concept may change due to a hidden context. For one motivating example consider classifying intermediate products in some process, e.g., for manufacturing cars or the control flow in software, as faulty or correct. The process can be represented by a digraph and the concept is monotone: Typical faults that appear in an intermediate product will also be present in later stages of the product. The concept may depend on a hidden variable as some pre-assembled parts may vary and the fault may occur only for some charges and not for others. In order to be able to trade off between the cost of having a faulty product and the costs needed to find the cause of the fault, tight performance guarantees for finding the bug are needed.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: