@article{1856,
abstract = {The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification under the input assumption, synthesize a system that optimizes the measured value. For safety specifications and quantitative measures that are defined by mean-payoff automata, the optimal synthesis problem reduces to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be achieved in polynomial time. For general omega-regular specifications along with mean-payoff automata, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. Our algorithm constructs optimal strategies that consist of two memoryless strategies and a counter. The counter is in general not bounded. To obtain a finite-state system, we show how to construct an ε-optimal strategy with a bounded counter, for all ε > 0. Furthermore, we show how to decide in polynomial time if it is possible to construct an optimal finite-state system (i.e., a system without a counter) for a given specification. We have implemented our approach and the underlying algorithms in a tool that takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. We present some experimental results showing optimal systems that were automatically generated in this way.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara and Singh, Rohit},
journal = {Journal of the ACM},
number = {1},
publisher = {ACM},
title = {{Measuring and synthesizing systems in probabilistic environments}},
doi = {10.1145/2699430},
volume = {62},
year = {2015},
}
@inproceedings{1857,
abstract = {Sharing information between multiple tasks enables algorithms to achieve good generalization performance even from small amounts of training data. However, in a realistic scenario of multi-task learning not all tasks are equally related to each other, hence it could be advantageous to transfer information only between the most related tasks. In this work we propose an approach that processes multiple tasks in a sequence with sharing between subsequent tasks instead of solving all tasks jointly. Subsequently, we address the question of curriculum learning of tasks, i.e. finding the best order of tasks to be learned. Our approach is based on a generalization bound criterion for choosing the task order that optimizes the average expected classification performance over all tasks. Our experimental results show that learning multiple related tasks sequentially can be more effective than learning them jointly, the order in which tasks are being solved affects the overall performance, and that our model is able to automatically discover the favourable order of tasks. },
author = {Pentina, Anastasia and Sharmanska, Viktoriia and Lampert, Christoph},
location = {Boston, MA, United States},
pages = {5492 -- 5500},
publisher = {IEEE},
title = {{Curriculum learning of multiple tasks}},
doi = {10.1109/CVPR.2015.7299188},
year = {2015},
}
@inproceedings{1858,
abstract = {We study the problem of predicting the future, though only in the probabilistic sense of estimating a future state of a time-varying probability distribution. This is not only an interesting academic problem, but solving this extrapolation problem also has many practical application, e.g. for training classifiers that have to operate under time-varying conditions. Our main contribution is a method for predicting the next step of the time-varying distribution from a given sequence of sample sets from earlier time steps. For this we rely on two recent machine learning techniques: embedding probability distributions into a reproducing kernel Hilbert space, and learning operators by vector-valued regression. We illustrate the working principles and the practical usefulness of our method by experiments on synthetic and real data. We also highlight an exemplary application: training a classifier in a domain adaptation setting without having access to examples from the test time distribution at training time.},
author = {Lampert, Christoph},
location = {Boston, MA, United States},
pages = {942 -- 950},
publisher = {IEEE},
title = {{Predicting the future behavior of a time-varying probability distribution}},
doi = {10.1109/CVPR.2015.7298696},
year = {2015},
}
@inproceedings{1859,
abstract = {Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut.
In this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes.
We show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm. },
author = {Shah, Neel and Kolmogorov, Vladimir and Lampert, Christoph},
location = {Boston, MA, USA},
pages = {2737 -- 2745},
publisher = {IEEE},
title = {{A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle}},
doi = {10.1109/CVPR.2015.7298890},
year = {2015},
}
@inproceedings{1860,
abstract = {Classifiers for object categorization are usually evaluated by their accuracy on a set of i.i.d. test examples. This provides us with an estimate of the expected error when applying the classifiers to a single new image. In real application, however, classifiers are rarely only used for a single image and then discarded. Instead, they are applied sequentially to many images, and these are typically not i.i.d. samples from a fixed data distribution, but they carry dependencies and their class distribution varies over time. In this work, we argue that the phenomenon of correlated data at prediction time is not a nuisance, but a blessing in disguise. We describe a probabilistic method for adapting classifiers at prediction time without having to retrain them. We also introduce a framework for creating realistically distributed image sequences, which offers a way to benchmark classifier adaptation methods, such as the one we propose. Experiments on the ILSVRC2010 and ILSVRC2012 datasets show that adapting object classification systems at prediction time can significantly reduce their error rate, even with no additional human feedback.},
author = {Royer, Amélie and Lampert, Christoph},
location = {Boston, MA, United States},
pages = {1401 -- 1409},
publisher = {IEEE},
title = {{Classifier adaptation at prediction time}},
doi = {10.1109/CVPR.2015.7298746},
year = {2015},
}
@article{1861,
abstract = {Continuous-time Markov chains are commonly used in practice for modeling biochemical reaction networks in which the inherent randomness of themolecular interactions cannot be ignored. This has motivated recent research effort into methods for parameter inference and experiment design for such models. The major difficulty is that such methods usually require one to iteratively solve the chemical master equation that governs the time evolution of the probability distribution of the system. This, however, is rarely possible, and even approximation techniques remain limited to relatively small and simple systems. An alternative explored in this article is to base methods on only some low-order moments of the entire probability distribution. We summarize the theory behind such moment-based methods for parameter inference and experiment design and provide new case studies where we investigate their performance.},
author = {Ruess, Jakob and Lygeros, John},
journal = {ACM Transactions on Modeling and Computer Simulation},
number = {2},
publisher = {ACM},
title = {{Moment-based methods for parameter inference and experiment design for stochastic biochemical reaction networks}},
doi = {10.1145/2688906},
volume = {25},
year = {2015},
}
@article{1864,
abstract = {The Altshuler–Shklovskii formulas (Altshuler and Shklovskii, BZh Eksp Teor Fiz 91:200, 1986) predict, for any disordered quantum system in the diffusive regime, a universal power law behaviour for the correlation functions of the mesoscopic eigenvalue density. In this paper and its companion (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013), we prove these formulas for random band matrices. In (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013) we introduced a diagrammatic approach and presented robust estimates on general diagrams under certain simplifying assumptions. In this paper, we remove these assumptions by giving a general estimate of the subleading diagrams. We also give a precise analysis of the leading diagrams which give rise to the Altschuler–Shklovskii power laws. Moreover, we introduce a family of general random band matrices which interpolates between real symmetric (β = 1) and complex Hermitian (β = 2) models, and track the transition for the mesoscopic density–density correlation. Finally, we address the higher-order correlation functions by proving that they behave asymptotically according to a Gaussian process whose covariance is given by the Altshuler–Shklovskii formulas.
},
author = {Erdös, László and Knowles, Antti},
journal = {Annales Henri Poincare},
number = {3},
pages = {709 -- 799},
publisher = {Springer},
title = {{The Altshuler–Shklovskii formulas for random band matrices II: The general case}},
doi = {10.1007/s00023-014-0333-5},
volume = {16},
year = {2015},
}
@article{1865,
abstract = {The plant hormone auxin and its directional transport are known to play a crucial role in defining the embryonic axis and subsequent development of the body plan. Although the role of PIN auxin efflux transporters has been clearly assigned during embryonic shoot and root specification, the role of the auxin influx carriers AUX1 and LIKE-AUX1 (LAX) proteins is not well established. Here, we used chemical and genetic tools on Brassica napus microspore-derived embryos and Arabidopsis thaliana zygotic embryos, and demonstrate that AUX1, LAX1 and LAX2 are required for both shoot and root pole formation, in concert with PIN efflux carriers. Furthermore, we uncovered a positive-feedback loop betweenMONOPTEROS(ARF5)-dependent auxin signalling and auxin transport. ThisMONOPTEROSdependent transcriptional regulation of auxin influx (AUX1, LAX1 and LAX2) and auxin efflux (PIN1 and PIN4) carriers by MONOPTEROS helps to maintain proper auxin transport to the root tip. These results indicate that auxin-dependent cell specification during embryo development requires balanced auxin transport involving both influx and efflux mechanisms, and that this transport is maintained by a positive transcriptional feedback on auxin signalling.},
author = {Robert, Hélène and Grunewald, Wim and Sauer, Michael and Cannoot, Bernard and Soriano, Mercedes and Swarup, Ranjan and Weijers, Dolf and Bennett, Malcolm and Boutilier, Kim and Friml, Jirí},
journal = {Development},
number = {4},
pages = {702 -- 711},
publisher = {Company of Biologists},
title = {{Plant embryogenesis requires AUX/LAX-mediated auxin influx}},
doi = {10.1242/dev.115832},
volume = {142},
year = {2015},
}
@article{1866,
author = {Henzinger, Thomas A and Raskin, Jean},
journal = {Communications of the ACM},
number = {2},
pages = {86--86},
publisher = {ACM},
title = {{The equivalence problem for finite automata: Technical perspective}},
doi = {10.1145/2701001},
volume = {58},
year = {2015},
}
@article{1867,
abstract = {Cultured mammalian cells essential are model systems in basic biology research, production platforms of proteins for medical use, and testbeds in synthetic biology. Flavin cofactors, in particular flavin mononucleotide (FMN) and flavin adenine dinucleotide (FAD), are critical for cellular redox reactions and sense light in naturally occurring photoreceptors and optogenetic tools. Here, we quantified flavin contents of commonly used mammalian cell lines. We first compared three procedures for extraction of free and noncovalently protein-bound flavins and verified extraction using fluorescence spectroscopy. For separation, two CE methods with different BGEs were established, and detection was performed by LED-induced fluorescence with limit of detections (LODs 0.5-3.8 nM). We found that riboflavin (RF), FMN, and FAD contents varied significantly between cell lines. RF (3.1-14 amol/cell) and FAD (2.2-17.0 amol/cell) were the predominant flavins, while FMN (0.46-3.4 amol/cell) was found at markedly lower levels. Observed flavin contents agree with those previously extracted from mammalian tissues, yet reduced forms of RF were detected that were not described previously. Quantification of flavins in mammalian cell lines will allow a better understanding of cellular redox reactions and optogenetic tools.},
author = {Hühner, Jens and Inglés Prieto, Álvaro and Neusüß, Christian and Lämmerhofer, Michael and Janovjak, Harald L},
journal = {Electrophoresis},
number = {4},
pages = {518 -- 525},
publisher = {Wiley},
title = {{Quantification of riboflavin, flavin mononucleotide, and flavin adenine dinucleotide in mammalian model cells by CE with LED-induced fluorescence detection}},
doi = {10.1002/elps.201400451},
volume = {36},
year = {2015},
}