2021 [ nach oben ]

Quinzan, Francesco; Doskoč, Vanja; Göbel, Andreas; Friedrich, Tobias Adaptive Sampling for Fast Constrained Maximization of Submodular FunctionsArtificial Intelligence and Statistics (AISTATS) 2021: 964–972
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a \(p\)-system side constraint, and it achieves a \((p + O({\sqrt{p}}))\)-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a \(p + O(1))\)-approximation when the given side constraint is a \(p\)-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.
@inproceedings{doskoc2021adaptive, abstract = {Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a \(p\)-system side constraint, and it achieves a \((p + O({\sqrt{p}}))\)-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a \(p + O(1))\)-approximation when the given side constraint is a \(p\)-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.}, author = {Quinzan, Francesco and Doskoč, Vanja and Göbel, Andreas and Friedrich, Tobias}, booktitle = {Artificial Intelligence and Statistics (AISTATS)}, keywords = {aistats andreasgoebel francescoquinzan tobiasfriedrich vanjadoskoc year2021}, pages = {964-972}, title = {Adaptive Sampling for Fast Constrained Maximization of Submodular Functions}, year = 2021 }

Berger, Julian; Böther, Maximilian; Doskoč, Vanja; Gadea Harder, Jonathan; Klodt, Nicolas; Kötzing, Timo; Lötzsch, Winfried; Peters, Jannik; Schiller, Leon; Seifert, Lars; Wells, Armin; Wietheger, Simon Learning Languages with Decidable HypothesesComputability in Europe (CiE) 2021: 25–37
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In \emph{language learning in the limit}, the most common type of hypothesis is to give an enumerator for a language, a \(W\)-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely \emph{programs for characteristic functions} (called \(C\)-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal \(C\)-index. In this first analysis of learning with \(C\)-indices, we give a structured account of the learning power of various restrictions employing \(C\)-indices, also when compared with \(W\)-indices. We establish a hierarchy of learning power depending on whether \(C\)-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation. Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.
@inproceedings{berger2021learning, abstract = {In \emph{language learning in the limit}, the most common type of hypothesis is to give an enumerator for a language, a \(W\)-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely \emph{programs for characteristic functions} (called \(C\)-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal \(C\)-index. In this first analysis of learning with \(C\)-indices, we give a structured account of the learning power of various restrictions employing \(C\)-indices, also when compared with \(W\)-indices. We establish a hierarchy of learning power depending on whether \(C\)-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation. Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.}, author = {Berger, Julian and Böther, Maximilian and Doskoč, Vanja and Gadea Harder, Jonathan and Klodt, Nicolas and Kötzing, Timo and Lötzsch, Winfried and Peters, Jannik and Schiller, Leon and Seifert, Lars and Wells, Armin and Wietheger, Simon}, booktitle = {Computability in Europe (CiE)}, keywords = {arminwells cie jannikpeters jonathangadeaharder julianberger larsseifert leonschiller maximilianboether nicolasklodt simonwietheger timokoetzing vanjadoskoc winfriedloetzsch year2021}, pages = {25-37}, title = {Learning Languages with Decidable Hypotheses}, year = 2021 }

Doskoč, Vanja; Kötzing, Timo Mapping Monotonic Restrictions in Inductive InferenceComputability in Europe (CiE) 2021: 146–157
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In \emph{inductive inference} we investigate computable devices (learners) learning formal languages. In this work, we focus on \emph{monotonic} learners which, despite their natural motivation, exhibit peculiar behaviour. A recent study analysed the learning capabilities of \emph{strongly monotone} learners in various settings. The therein unveiled differences between \emph{explanatory} (syntactically converging) and \emph{behaviourally correct} (semantically converging) such learners motivate our studies of \emph{monotone} learners in the same settings. While the structure of the pairwise relations for monotone explanatory learning is similar to the strongly monotone case (and for similar reasons), for behaviourally correct learning a very different picture emerges. In the latter setup, we provide a \emph{self-learning} class of languages showing that monotone learners, as opposed to their strongly monotone counterpart, do heavily rely on the order in which the information is given, an unusual result for behaviourally correct learners.
@inproceedings{doskoc2021mapping, abstract = {In \emph{inductive inference} we investigate computable devices (learners) learning formal languages. In this work, we focus on \emph{monotonic} learners which, despite their natural motivation, exhibit peculiar behaviour. A recent study analysed the learning capabilities of \emph{strongly monotone} learners in various settings. The therein unveiled differences between \emph{explanatory} (syntactically converging) and \emph{behaviourally correct} (semantically converging) such learners motivate our studies of \emph{monotone} learners in the same settings. While the structure of the pairwise relations for monotone explanatory learning is similar to the strongly monotone case (and for similar reasons), for behaviourally correct learning a very different picture emerges. In the latter setup, we provide a \emph{self-learning} class of languages showing that monotone learners, as opposed to their strongly monotone counterpart, do heavily rely on the order in which the information is given, an unusual result for behaviourally correct learners.}, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {cie timokoetzing vanjadoskoc year2021}, pages = {146-157}, title = {Mapping Monotonic Restrictions in Inductive Inference}, year = 2021 }

Doskoč, Vanja; Kötzing, Timo Normal Forms for Semantically Witness-Based Learners in Inductive InferenceComputability in Europe (CiE) 2021: 158–168
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In \emph{inductive inference}, we study learners (computable devices) inferring formal languages. In particular, we consider \emph{semantically witness-based} learners, that is, learners which are required to \emph{justify} each of their semantic mind changes. This natural requirement deserves special attention as it is a specialization of various important learning paradigms. As such, it has already proven to be fruitful for gaining knowledge about other types of restrictions. In this paper, we provide a thorough analysis of semantically converging, semantically witness-based learners, obtaining \emph{normal forms} for them. Most notably, we show that \emph{set-driven globally} semantically witness-based learners are equally powerful as their \emph{Gold-style semantically conservative} counterpart. Such results are key to understanding the, yet undiscovered, mutual relation between various important learning paradigms of semantically converging learners.
@inproceedings{doskoc2021normal, abstract = {In \emph{inductive inference}, we study learners (computable devices) inferring formal languages. In particular, we consider \emph{semantically witness-based} learners, that is, learners which are required to \emph{justify} each of their semantic mind changes. This natural requirement deserves special attention as it is a specialization of various important learning paradigms. As such, it has already proven to be fruitful for gaining knowledge about other types of restrictions. In this paper, we provide a thorough analysis of semantically converging, semantically witness-based learners, obtaining \emph{normal forms} for them. Most notably, we show that \emph{set-driven globally} semantically witness-based learners are equally powerful as their \emph{Gold-style semantically conservative} counterpart. Such results are key to understanding the, yet undiscovered, mutual relation between various important learning paradigms of semantically converging learners.}, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {cie timokoetzing vanjadoskoc year2021}, pages = {158-168}, title = {Normal Forms for Semantically Witness-Based Learners in Inductive Inference}, year = 2021 }

Berger, Julian; Bleidt, Tibor; Büßemeyer, Martin; Ding, Marcus; Feldmann, Moritz; Feuerpfeil, Moritz; Jacoby, Janusch; Schröter, Valentin; Sievers, Bjarne; Spranger, Moritz; Stadlinger, Simon; Wullenweber, Paul; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Fine-Grained Localization, Classification and Segmentation of Lungs with Various DiseasesCVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
The fine-grained localization and classification of various lung abnormalities is a challenging yet important task for combating diseases and, also, pandemics. In this paper, we present one way to detect and classify abnormalities within chest X-ray scans. In particular, we investigate the use of binary image classification (to distinguish between healthy and infected chests) and the weighted box fusion (which constructs a detection box using the proposed boxes within range). We observe that both methods increase the performance of a base model significantly. Furthermore, we improve state of the art on lung segmentation, even in the presence of abnormalities. We do so using transfer learning to fine-tune a UNet model on the Montgomery and Shenzhen datasets. In our experiments, we compare standard augmentations (like crop, pad, rotate, warp, zoom, brightness, and contrast variations) to more complex ones (for example, block masking and diffused noise augmentations). This way, we obtain a state-of-the-art model with a dice score of 97.9\%. In particular, we show that simple augmentations outperform complex ones in our setting.
@inproceedings{berger2021finegrained, abstract = {The fine-grained localization and classification of various lung abnormalities is a challenging yet important task for combating diseases and, also, pandemics. In this paper, we present one way to detect and classify abnormalities within chest X-ray scans. In particular, we investigate the use of binary image classification (to distinguish between healthy and infected chests) and the weighted box fusion (which constructs a detection box using the proposed boxes within range). We observe that both methods increase the performance of a base model significantly. Furthermore, we improve state of the art on lung segmentation, even in the presence of abnormalities. We do so using transfer learning to fine-tune a UNet model on the Montgomery and Shenzhen datasets. In our experiments, we compare standard augmentations (like crop, pad, rotate, warp, zoom, brightness, and contrast variations) to more complex ones (for example, block masking and diffused noise augmentations). This way, we obtain a state-of-the-art model with a dice score of 97.9\%. In particular, we show that simple augmentations outperform complex ones in our setting.}, author = {Berger, Julian and Bleidt, Tibor and Büßemeyer, Martin and Ding, Marcus and Feldmann, Moritz and Feuerpfeil, Moritz and Jacoby, Janusch and Schröter, Valentin and Sievers, Bjarne and Spranger, Moritz and Stadlinger, Simon and Wullenweber, Paul and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {CVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR)}, keywords = {bjarnesievers fgvc@cvpr januschjacoby julianberger marcusding martinbuessemeyer moritzfeldmann moritzfeuerpfeil moritzspranger paulwullenweber sarelcohen simonstadlinger tiborbleidt tobiasfriedrich valentinschroeter vanjadoskoc year2021}, title = {Fine-Grained Localization, Classification and Segmentation of Lungs with Various Diseases}, year = 2021 }

Kißig, Otto; Taraz, Martin; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Drug Repurposing for Multiple COVID Strains using Collaborative FilteringICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
The ongoing COVID-19 pandemic demands for a swift discovery of suitable treatments. The development of completely new compounds for such a novel disease is a challenging, time intensive process. This amplifies the relevance of drug repurposing, a technique where existing drugs are used to treat other diseases. A common bioinformatical approach to this is based on knowledge graphs, which compile relationships between drugs, diseases, genes and other biomedical entities. Then, graph neural networks (GNNs) are used for the drug repurposing task as they provide a good link prediction performance on such knowledge graphs. Building on state-of-the-art GNN research, Doshi \& Chepuri (2020) construct the remarkable model DR-COVID. We re-implement their model and extend the approach to perform significantly better. We propose and evaluate several strategies for the aggregation of link predictions into drug recommendation rankings. With the help of clustering of similar target diseases we improve the model by a substantial margin, compiling a top-100 ranking of candidates including 32 currently being in COVID-19-related clinical trials. Regarding the re-implementation, we offer more flexibility in the selection of the graph neighborhood sizes fed into the model and reduce the training time significantly by making use of data parallelism.
@inproceedings{kissig2021repurposingcollaborativefiltering, abstract = {The ongoing COVID-19 pandemic demands for a swift discovery of suitable treatments. The development of completely new compounds for such a novel disease is a challenging, time intensive process. This amplifies the relevance of drug repurposing, a technique where existing drugs are used to treat other diseases. A common bioinformatical approach to this is based on knowledge graphs, which compile relationships between drugs, diseases, genes and other biomedical entities. Then, graph neural networks (GNNs) are used for the drug repurposing task as they provide a good link prediction performance on such knowledge graphs. Building on state-of-the-art GNN research, Doshi \& Chepuri (2020) construct the remarkable model DR-COVID. We re-implement their model and extend the approach to perform significantly better. We propose and evaluate several strategies for the aggregation of link predictions into drug recommendation rankings. With the help of clustering of similar target diseases we improve the model by a substantial margin, compiling a top-100 ranking of candidates including 32 currently being in COVID-19-related clinical trials. Regarding the re-implementation, we offer more flexibility in the selection of the graph neighborhood sizes fed into the model and reduce the training time significantly by making use of data parallelism.}, author = {Kißig, Otto and Taraz, Martin and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {ICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR)}, keywords = {martintaraz mlpcp@iclr ottokissig sarelcohen tobiasfriedrich vanjadoskoc year2021}, title = {Drug Repurposing for Multiple COVID Strains using Collaborative Filtering}, year = 2021 }

2020 [ nach oben ]

Doskoč, Vanja; Kötzing, Timo Cautious Limit LearningAlgorithmic Learning Theory (ALT) 2020: 251–276
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We investigate language learning in the limit from text with various \(\mathit{cautious}\) learning restrictions. Learning is \(\mathit{cautious}\) if no hypothesis is a proper subset of a previous guess. While dealing with a seemingly natural learning behaviour, cautious learning does severely restrict explanatory (syntactic) learning power. To further understand why exactly this loss of learning power arises, Kötzing and Palenta (2016) introduced weakened versions of cautious learning and gave first partial results on their relation. In this paper, we aim to understand the restriction of cautious learning more fully. To this end we compare the known variants in a number of different settings, namely full-information and (partially) set-driven learning, paired either with the syntactic convergence restriction (explanatory learning) or the semantic convergence restriction (behaviourally correct learning). To do so, we make use of normal forms presented in Kötzing et al. (2017), most notably strongly locking and consistent learning. While strongly locking learners have been exploited when dealing with a variety of syntactic learning restrictions, we show how they can be beneficial in the semantic case as well. Furthermore, we expand the normal forms to a broader range of learning restrictions, including an answer to the open question of whether cautious learners can be assumed to be consistent, as stated in Kötzing et al. (2017).
@inproceedings{doskoc2020cautious, abstract = {We investigate language learning in the limit from text with various \(\mathit{cautious}\) learning restrictions. Learning is \(\mathit{cautious}\) if no hypothesis is a proper subset of a previous guess. While dealing with a seemingly natural learning behaviour, cautious learning does severely restrict explanatory (syntactic) learning power. To further understand why exactly this loss of learning power arises, Kötzing and Palenta (2016) introduced weakened versions of cautious learning and gave first partial results on their relation. In this paper, we aim to understand the restriction of cautious learning more fully. To this end we compare the known variants in a number of different settings, namely full-information and (partially) set-driven learning, paired either with the syntactic convergence restriction (explanatory learning) or the semantic convergence restriction (behaviourally correct learning). To do so, we make use of normal forms presented in Kötzing et al. (2017), most notably strongly locking and consistent learning. While strongly locking learners have been exploited when dealing with a variety of syntactic learning restrictions, we show how they can be beneficial in the semantic case as well. Furthermore, we expand the normal forms to a broader range of learning restrictions, including an answer to the open question of whether cautious learners can be assumed to be consistent, as stated in Kötzing et al. (2017).}, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {alt timokoetzing vanjadoskoc year2020}, pages = {251-276}, title = {Cautious Limit Learning}, year = 2020 }

Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, Francesco Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic SettingsEuropean Conference on Artificial Intelligence (ECAI) 2020: 435–442
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.
@inproceedings{doskoc2020nonmonotone, abstract = {We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.}, author = {Doskoč, Vanja and Friedrich, Tobias and Göbel, Andreas and Neumann, Aneta and Neumann, Frank and Quinzan, Francesco}, booktitle = {European Conference on Artificial Intelligence (ECAI)}, keywords = {andreasgoebel anetaneumann ecai francescoquinzan frankneumann tobiasfriedrich vanjadoskoc year2020}, pages = {435-442}, publisher = {{IOS} Press}, title = {Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings}, year = 2020 }

2018 [ nach oben ]

Doskoč, Vanja Confident Iterative Learning in Computational Learning TheoryCurrent Trends in Theory and Practice of Computer Science (SOFSEM) 2018: 30–42
[ Abstract ] [ BibTeX ] [ Download ]
 
In inductive inference various types of learning have emerged. The main aim of this paper is to investigate a new type of learning, the confident iterative learning. Given a class to be learnt, the idea here is to merge the following two concepts. For confidence, we require the learner to converge on any set, however, it only needs to be correct on the sets in the class. To be iterative, we restrict the learner’s memory on previ- ous inputs and calculations to its last hypothesis. Investigating the new learner, we will provide negative and positive examples, as well as some properties the confident iterative learner possesses. This will peak at a classification theorem for certain types of classes. Next, we will introduce and compare different types of confidence, focus- ing on the learner’s behaviour on sets outside of the class. Lastly, we will focus on the possible hypotheses. Introducing learning with respect to hypothesis spaces, we will provide examples witnessing that exact, class preserving and class comprising learning are different.
@conference{doskoc2018confident, abstract = {In inductive inference various types of learning have emerged. The main aim of this paper is to investigate a new type of learning, the confident iterative learning. Given a class to be learnt, the idea here is to merge the following two concepts. For confidence, we require the learner to converge on any set, however, it only needs to be correct on the sets in the class. To be iterative, we restrict the learner’s memory on previ- ous inputs and calculations to its last hypothesis. Investigating the new learner, we will provide negative and positive examples, as well as some properties the confident iterative learner possesses. This will peak at a classification theorem for certain types of classes. Next, we will introduce and compare different types of confidence, focus- ing on the learner’s behaviour on sets outside of the class. Lastly, we will focus on the possible hypotheses. Introducing learning with respect to hypothesis spaces, we will provide examples witnessing that exact, class preserving and class comprising learning are different.}, author = {Doskoč, Vanja}, booktitle = {Current Trends in Theory and Practice of Computer Science (SOFSEM)}, keywords = {sofsem vanjadoskoc year2018}, pages = {30-42}, title = {Confident Iterative Learning in Computational Learning Theory}, year = 2018 }