The Cost of Learning Directed Cuts
published: Sept. 5, 2007, recorded: August 2007, views: 3029
Report a problem or upload filesIf 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.
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !