Submodular learning and covering with response-dependent costs

DOI10.1007/978-3-319-46379-7_9zbMATH Open1398.68456arXiv1602.07120OpenAlexW3023755868MaRDI QIDQ1663646FDOQ1663646

Sivan Sabato

Publication date: 22 August 2018

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the response to the action. We propose a natural greedy algorithm for response-dependent costs. We bound the approximation factor of this greedy algorithm in active learning settings as well as in the general setting. We show that a different property of the cost function controls the approximation factor in each of these scenarios. We further show that in both settings, the approximation factor of this greedy algorithm is near-optimal among all greedy algorithms. Experiments demonstrate the advantages of the proposed algorithm in the response-dependent cost setting.

Full work available at URL: https://arxiv.org/abs/1602.07120

zbMATH Keywords

submodular functionsinteractive learningoutcome costs

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A threshold of ln n for approximating set cover
• An analysis of the greedy algorithm for the submodular set covering problem
• Submodular functions and electrical networks
• An analysis of approximations for maximizing submodular set functions—I
• Approximating decision trees with value dependent testing costs
• Trading off Worst and Expected Cost in Decision Tree Problems

Cited In (2)

• Approximating decision trees with priority hypotheses
• Approximating decision trees with priority hypotheses

This page was built for publication: Submodular learning and covering with response-dependent costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663646)