@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}, } @article{1868, abstract = {We investigate high-dimensional nonlinear dynamical systems exhibiting multiple resonances under adiabatic parameter variations. Our motivations come from experimental considerations where time-dependent sweeping of parameters is a practical approach to probing and characterizing the bifurcations of the system. The question is whether bifurcations so detected are faithful representations of the bifurcations intrinsic to the original stationary system. Utilizing a harmonically forced, closed fluid flow system that possesses multiple resonances and solving the Navier-Stokes equation under proper boundary conditions, we uncover the phenomenon of the early effect. Specifically, as a control parameter, e.g., the driving frequency, is adiabatically increased from an initial value, resonances emerge at frequency values that are lower than those in the corresponding stationary system. The phenomenon is established by numerical characterization of physical quantities through the resonances, which include the kinetic energy and the vorticity field, and a heuristic analysis based on the concept of instantaneous frequency. A simple formula is obtained which relates the resonance points in the time-dependent and time-independent systems. Our findings suggest that, in general, any true bifurcation of a nonlinear dynamical system can be unequivocally uncovered through adiabatic parameter sweeping, in spite of a shift in the bifurcation point, which is of value to experimental studies of nonlinear dynamical systems.}, author = {Park, Youngyong and Do, Younghae and Altmeyer, Sebastian and Lai, Yingcheng and Lee, Gyuwon}, issn = {1539-3755}, journal = {Physical Review E}, number = {2}, publisher = {American Physical Society}, title = {{Early effect in time-dependent, high-dimensional nonlinear dynamical systems with multiple resonances}}, doi = {10.1103/PhysRevE.91.022906}, volume = {91}, year = {2015}, } @article{1871, abstract = {The plant hormone auxin is a key regulator of plant growth and development. Differences in auxin distribution within tissues are mediated by the polar auxin transport machinery, and cellular auxin responses occur depending on changes in cellular auxin levels. Multiple receptor systems at the cell surface and in the interior operate to sense and interpret fluctuations in auxin distribution that occur during plant development. Until now, three proteins or protein complexes that can bind auxin have been identified. SCFTIR1 [a SKP1-cullin-1-F-box complex that contains transport inhibitor response 1 (TIR1) as the F-box protein] and S-phase-kinaseassociated protein 2 (SKP2) localize to the nucleus, whereas auxinbinding protein 1 (ABP1), predominantly associates with the endoplasmic reticulum and cell surface. In this Cell Science at a Glance article, we summarize recent discoveries in the field of auxin transport and signaling that have led to the identification of new components of these pathways, as well as their mutual interaction.}, author = {Grones, Peter and Friml, Jirí}, journal = {Journal of Cell Science}, number = {1}, pages = {1 -- 7}, publisher = {Company of Biologists}, title = {{Auxin transporters and binding proteins at a glance}}, doi = {10.1242/jcs.159418}, volume = {128}, year = {2015}, } @article{1873, abstract = {We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ1ε(0,1]; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples.}, author = {Chatterjee, Krishnendu and Chmelik, Martin}, journal = {Artificial Intelligence}, pages = {46 -- 72}, publisher = {Elsevier}, title = {{POMDPs under probabilistic semantics}}, doi = {10.1016/j.artint.2014.12.009}, volume = {221}, year = {2015}, } @inproceedings{12881, author = {Martius, Georg S and Olbrich, Eckehard}, booktitle = {Proceedings of the 13th European Conference on Artificial Life}, isbn = {9780262330275}, location = {York, United Kingdom}, pages = {78}, publisher = {MIT Press}, title = {{Quantifying self-organizing behavior of autonomous robots}}, doi = {10.7551/978-0-262-33027-5-ch018}, year = {2015}, } @inproceedings{1992, abstract = {We present a method and a tool for generating succinct representations of sets of concurrent traces. We focus on trace sets that contain all correct or all incorrect permutations of events from a given trace. We represent trace sets as HB-Formulas that are Boolean combinations of happens-before constraints between events. To generate a representation of incorrect interleavings, our method iteratively explores interleavings that violate the specification and gathers generalizations of the discovered interleavings into an HB-Formula; its complement yields a representation of correct interleavings. We claim that our trace set representations can drive diverse verification, fault localization, repair, and synthesis techniques for concurrent programs. We demonstrate this by using our tool in three case studies involving synchronization synthesis, bug summarization, and abstraction refinement based verification. In each case study, our initial experimental results have been promising. In the first case study, we present an algorithm for inferring missing synchronization from an HB-Formula representing correct interleavings of a given trace. The algorithm applies rules to rewrite specific patterns in the HB-Formula into locks, barriers, and wait-notify constructs. In the second case study, we use an HB-Formula representing incorrect interleavings for bug summarization. While the HB-Formula itself is a concise counterexample summary, we present additional inference rules to help identify specific concurrency bugs such as data races, define-use order violations, and two-stage access bugs. In the final case study, we present a novel predicate learning procedure that uses HB-Formulas representing abstract counterexamples to accelerate counterexample-guided abstraction refinement (CEGAR). In each iteration of the CEGAR loop, the procedure refines the abstraction to eliminate multiple spurious abstract counterexamples drawn from the HB-Formula.}, author = {Gupta, Ashutosh and Henzinger, Thomas A and Radhakrishna, Arjun and Samanta, Roopsha and Tarrach, Thorsten}, isbn = {978-1-4503-3300-9}, location = {Mumbai, India}, pages = {433 -- 444}, publisher = {ACM}, title = {{Succinct representation of concurrent trace sets}}, doi = {10.1145/2676726.2677008}, year = {2015}, } @article{1993, abstract = {The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens. }, author = {Konrad, Matthias and Grasse, Anna V and Tragust, Simon and Cremer, Sylvia}, issn = {1471-2954}, journal = {Proceedings of the Royal Society of London Series B Biological Sciences}, number = {1799}, publisher = {The Royal Society}, title = {{Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host}}, doi = {10.1098/rspb.2014.1976}, volume = {282}, year = {2015}, } @article{1997, abstract = {We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials.}, author = {Noren, Patrik}, journal = {Journal of Symbolic Computation}, number = {May-June}, pages = {285 -- 296}, publisher = {Elsevier}, title = {{The three-state toric homogeneous Markov chain model has Markov degree two}}, doi = {10.1016/j.jsc.2014.09.014}, volume = {68/Part 2}, year = {2015}, } @article{2006, abstract = {The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data. }, author = {Hein, Nicolas and Hillar, Christopher and Martin Del Campo Sanchez, Abraham and Sottile, Frank and Teitler, Zach}, journal = {Experimental Mathematics}, number = {3}, pages = {261 -- 269}, publisher = {Taylor & Francis}, title = {{The monotone secant conjecture in the real Schubert calculus}}, doi = {10.1080/10586458.2014.980044}, volume = {24}, year = {2015}, } @article{2008, abstract = {The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package.}, author = {Klimova, Anna and Rudas, Tamás}, journal = {Scandinavian Journal of Statistics}, number = {3}, pages = {832 -- 847}, publisher = {Wiley}, title = {{Iterative scaling in curved exponential families}}, doi = {10.1111/sjos.12139}, volume = {42}, year = {2015}, } @article{2014, abstract = {The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.}, author = {Klimova, Anna and Uhler, Caroline and Rudas, Tamás}, journal = {Computational Statistics & Data Analysis}, number = {7}, pages = {57 -- 72}, publisher = {Elsevier}, title = {{Faithfulness and learning hypergraphs from discrete distributions}}, doi = {10.1016/j.csda.2015.01.017}, volume = {87}, year = {2015}, } @article{2025, abstract = {Small GTP-binding proteins of the Ras superfamily play diverse roles in intracellular trafficking. Among them, the Rab, Arf, and Rho families function in successive steps of vesicle transport, in forming vesicles from donor membranes, directing vesicle trafficking toward target membranes and docking vesicles onto target membranes. These proteins act as molecular switches that are controlled by a cycle of GTP binding and hydrolysis regulated by guanine nucleotide exchange factors (GEFs) and GTPase-activating proteins (GAPs). In this study we explored the role of GAPs in the regulation of the endocytic pathway using fluorescently labeled yeast mating pheromone α-factor. Among 25 non-essential GAP mutants, we found that deletion of the GLO3 gene, encoding Arf-GAP protein, caused defective internalization of fluorescently labeled α-factor. Quantitative analysis revealed that glo3Δ cells show defective α-factor binding to the cell surface. Interestingly, Ste2p, the α-factor receptor, was mis-localized from the plasma membrane to the vacuole in glo3Δ cells. Domain deletion mutants of Glo3p revealed that a GAP-independent function, as well as the GAP activity, of Glo3p is important for both α-factor binding and Ste2p localization at the cell surface. Additionally, we found that deletion of the GLO3 gene affects the size and number of Arf1p-residing Golgi compartments and causes a defect in transport from the TGN to the plasma membrane. Furthermore, we demonstrated that glo3Δ cells were defective in the late endosome-to-TGN transport pathway, but not in the early endosome-to-TGN transport pathway. These findings suggest novel roles for Arf-GAP Glo3p in endocytic recycling of cell surface proteins.}, author = {Kawada, Daiki and Kobayashi, Hiromu and Tomita, Tsuyoshi and Nakata, Eisuke and Nagano, Makoto and Siekhaus, Daria E and Toshima, Junko and Toshimaa, Jiro}, journal = {Biochimica et Biophysica Acta - Molecular Cell Research}, number = {1}, pages = {144 -- 156}, publisher = {Elsevier}, title = {{The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins}}, doi = {10.1016/j.bbamcr.2014.10.009}, volume = {1853}, year = {2015}, } @article{2030, abstract = {A hybrid-parallel direct-numerical-simulation method with application to turbulent Taylor-Couette flow is presented. The Navier-Stokes equations are discretized in cylindrical coordinates with the spectral Fourier-Galerkin method in the axial and azimuthal directions, and high-order finite differences in the radial direction. Time is advanced by a second-order, semi-implicit projection scheme, which requires the solution of five Helmholtz/Poisson equations, avoids staggered grids and renders very small slip velocities. Nonlinear terms are evaluated with the pseudospectral method. The code is parallelized using a hybrid MPI-OpenMP strategy, which, compared with a flat MPI parallelization, is simpler to implement, allows to reduce inter-node communications and MPI overhead that become relevant at high processor-core counts, and helps to contain the memory footprint. A strong scaling study shows that the hybrid code maintains scalability up to more than 20,000 processor cores and thus allows to perform simulations at higher resolutions than previously feasible. In particular, it opens up the possibility to simulate turbulent Taylor-Couette flows at Reynolds numbers up to O(105). This enables to probe hydrodynamic turbulence in Keplerian flows in experimentally relevant regimes.}, author = {Shi, Liang and Rampp, Markus and Hof, Björn and Avila, Marc}, journal = {Computers and Fluids}, number = {1}, pages = {1 -- 11}, publisher = {Elsevier}, title = {{A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow}}, doi = {10.1016/j.compfluid.2014.09.021}, volume = {106}, year = {2015}, }