Material Detail

The Cost of Learning Directed Cuts

The Cost of Learning Directed Cuts

This video was recorded at 5th International Workshop on Mining and Learning with Graphs (MLG), Firenze 2007. 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.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.