TY - CONF
AB - Multi-exit architectures, in which a stack of processing layers is interleaved with early output layers, allow the processing of a test example to stop early and thus save computation time and/or energy. In this work, we propose a new training procedure for multi-exit architectures based on the principle of knowledge distillation. The method encourage searly exits to mimic later, more accurate exits, by matching their output probabilities.
Experiments on CIFAR100 and ImageNet show that distillation-based training significantly improves the accuracy of early exits while maintaining state-of-the-art accuracy for late ones. The method is particularly beneficial when training data is limited and it allows a straightforward extension to semi-supervised learning,i.e. making use of unlabeled data at training time. Moreover, it takes only afew lines to implement and incurs almost no computational overhead at training time, and none at all at test time.
AU - Bui Thi Mai, Phuong
AU - Lampert, Christoph
ID - 7479
SN - 15505499
T2 - IEEE International Conference on Computer Vision
TI - Distillation-based training for multi-exit architectures
VL - 2019-October
ER -
TY - JOUR
AB - An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H into r parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω)(m−−√) and this is best possible. That is, there exist cuts which exceed the expected size of a random cut by some multiple of the standard deviation. We study analogues of this and related results in hypergraphs. First, we observe that similarly to graphs, every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m−−√) larger than the expected size of a random r-cut. Moreover, in the case where k = 3 and r = 2 this bound is best possible and is attained by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥ 4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant difference in behaviour, since the amount by which the size of the largest cut exceeds the expected size of a random cut is now considerably larger than the standard deviation.
AU - Conlon, David
AU - Fox, Jacob
AU - Kwan, Matthew Alan
AU - Sudakov, Benny
ID - 9580
IS - 1
JF - Israel Journal of Mathematics
SN - 0021-2172
TI - Hypergraph cuts above the average
VL - 233
ER -
TY - JOUR
AB - Consider integers 𝑘,ℓ such that 0⩽ℓ⩽(𝑘2) . Given a large graph 𝐺 , what is the fraction of 𝑘 -vertex subsets of 𝐺 which span exactly ℓ edges? When 𝐺 is empty or complete, and ℓ is zero or (𝑘2) , this fraction can be exactly 1. On the other hand, if ℓ is far from these extreme values, one might expect that this fraction is substantially smaller than 1. This was recently proved by Alon, Hefetz, Krivelevich, and Tyomkyn who initiated the systematic study of this question and proposed several natural conjectures.
Let ℓ∗=min{ℓ,(𝑘2)−ℓ} . Our main result is that for any 𝑘 and ℓ , the fraction of 𝑘 -vertex subsets that span ℓ edges is at most log𝑂(1)(ℓ∗/𝑘)√ 𝑘/ℓ∗, which is best-possible up to the logarithmic factor. This improves on multiple results of Alon, Hefetz, Krivelevich, and Tyomkyn, and resolves one of their conjectures. In addition, we also make some first steps towards some analogous questions for hypergraphs.
Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities, hypercontractivity, and a coupling trick for random variables defined on a ‘slice’ of the Boolean hypercube.
AU - Kwan, Matthew Alan
AU - Sudakov, Benny
AU - Tran, Tuan
ID - 9586
IS - 3
JF - Journal of the London Mathematical Society
SN - 0024-6107
TI - Anticoncentration for subgraph statistics
VL - 99
ER -
TY - JOUR
AB - An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. More than 25 years ago, Erdős, Faudree and Sós conjectured that in any C-Ramsey graph there are Ω(n^5/2) induced subgraphs, no pair of which have the same numbers of vertices and edges. Improving on earlier results of Alon, Balogh, Kostochka and Samotij, in this paper we prove this conjecture.
AU - Kwan, Matthew Alan
AU - Sudakov, Benny
ID - 9585
IS - 8
JF - Transactions of the American Mathematical Society
SN - 0002-9947
TI - Proof of a conjecture on induced subgraphs of Ramsey graphs
VL - 372
ER -
TY - JOUR
AB - Expansion microscopy is a relatively new approach to super-resolution imaging that uses expandable hydrogels to isotropically increase the physical distance between fluorophores in biological samples such as cell cultures or tissue slices. The classic gel recipe results in an expansion factor of ~4×, with a resolution of 60–80 nm. We have recently developed X10 microscopy, which uses a gel that achieves an expansion factor of ~10×, with a resolution of ~25 nm. Here, we provide a step-by-step protocol for X10 expansion microscopy. A typical experiment consists of seven sequential stages: (i) immunostaining, (ii) anchoring, (iii) polymerization, (iv) homogenization, (v) expansion, (vi) imaging, and (vii) validation. The protocol presented here includes recommendations for optimization, pitfalls and their solutions, and detailed guidelines that should increase reproducibility. Although our protocol focuses on X10 expansion microscopy, we detail which of these suggestions are also applicable to classic fourfold expansion microscopy. We exemplify our protocol using primary hippocampal neurons from rats, but our approach can be used with other primary cells or cultured cell lines of interest. This protocol will enable any researcher with basic experience in immunostainings and access to an epifluorescence microscope to perform super-resolution microscopy with X10. The procedure takes 3 d and requires ~5 h of actively handling the sample for labeling and expansion, and another ~3 h for imaging and analysis.
AU - Truckenbrodt, Sven M
AU - Sommer, Christoph M
AU - Rizzoli, Silvio O
AU - Danzl, Johann G
ID - 6052
IS - 3
JF - Nature Protocols
TI - A practical guide to optimization in X10 expansion microscopy
VL - 14
ER -
TY - CONF
AB - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.
AU - Aichholzer, Oswin
AU - Akitaya, Hugo A
AU - Cheung, Kenneth C
AU - Demaine, Erik D
AU - Demaine, Martin L
AU - Fekete, Sandor P
AU - Kleist, Linda
AU - Kostitsyna, Irina
AU - Löffler, Maarten
AU - Masárová, Zuzana
AU - Mundilova, Klara
AU - Schmidt, Christiane
ID - 6989
T2 - Proceedings of the 31st Canadian Conference on Computational Geometry
TI - Folding polyominoes with holes into a cube
ER -
TY - JOUR
AB - Progress in the atomic-scale modeling of matter over the past decade has been tremendous. This progress has been brought about by improvements in methods for evaluating interatomic forces that work by either solving the electronic structure problem explicitly, or by computing accurate approximations of the solution and by the development of techniques that use the Born–Oppenheimer (BO) forces to move the atoms on the BO potential energy surface. As a consequence of these developments it is now possible to identify stable or metastable states, to sample configurations consistent with the appropriate thermodynamic ensemble, and to estimate the kinetics of reactions and phase transitions. All too often, however, progress is slowed down by the bottleneck associated with implementing new optimization algorithms and/or sampling techniques into the many existing electronic-structure and empirical-potential codes. To address this problem, we are thus releasing a new version of the i-PI software. This piece of software is an easily extensible framework for implementing advanced atomistic simulation techniques using interatomic potentials and forces calculated by an external driver code. While the original version of the code (Ceriotti et al., 2014) was developed with a focus on path integral molecular dynamics techniques, this second release of i-PI not only includes several new advanced path integral methods, but also offers other classes of algorithms. In other words, i-PI is moving towards becoming a universal force engine that is both modular and tightly coupled to the driver codes that evaluate the potential energy surface and its derivatives.
AU - Kapil, Venkat
AU - Rossi, Mariana
AU - Marsalek, Ondrej
AU - Petraglia, Riccardo
AU - Litman, Yair
AU - Spura, Thomas
AU - Cheng, Bingqing
AU - Cuzzocrea, Alice
AU - Meißner, Robert H.
AU - Wilkins, David M.
AU - Helfrecht, Benjamin A.
AU - Juda, Przemysław
AU - Bienvenue, Sébastien P.
AU - Fang, Wei
AU - Kessler, Jan
AU - Poltavsky, Igor
AU - Vandenbrande, Steven
AU - Wieme, Jelle
AU - Corminboeuf, Clemence
AU - Kühne, Thomas D.
AU - Manolopoulos, David E.
AU - Markland, Thomas E.
AU - Richardson, Jeremy O.
AU - Tkatchenko, Alexandre
AU - Tribello, Gareth A.
AU - Van Speybroeck, Veronique
AU - Ceriotti, Michele
ID - 9677
JF - Computer Physics Communications
SN - 0010-4655
TI - i-PI 2.0: A universal force engine for advanced molecular simulations
VL - 236
ER -
TY - JOUR
AB - Atomistic modeling of phase transitions, chemical reactions, or other rare events that involve overcoming high free energy barriers usually entails prohibitively long simulation times. Introducing a bias potential as a function of an appropriately chosen set of collective variables can significantly accelerate the exploration of phase space, albeit at the price of distorting the distribution of microstates. Efficient reweighting to recover the unbiased distribution can be nontrivial when employing adaptive sampling techniques such as metadynamics, variationally enhanced sampling, or parallel bias metadynamics, in which the system evolves in a quasi-equilibrium manner under a time-dependent bias. We introduce an iterative unbiasing scheme that makes efficient use of all the trajectory data and that does not require the distribution to be evaluated on a grid. The method can thus be used even when the bias has a high dimensionality. We benchmark this approach against some of the existing schemes on model systems with different complexity and dimensionality.
AU - Giberti, F.
AU - Cheng, Bingqing
AU - Tribello, G. A.
AU - Ceriotti, M.
ID - 9680
IS - 1
JF - Journal of Chemical Theory and Computation
SN - 1549-9618
TI - Iterative unbiasing of quasi-equilibrium sampling
VL - 16
ER -
TY - JOUR
AB - A central goal of computational physics and chemistry is to predict material properties by using first-principles methods based on the fundamental laws of quantum mechanics. However, the high computational costs of these methods typically prevent rigorous predictions of macroscopic quantities at finite temperatures, such as heat capacity, density, and chemical potential. Here, we enable such predictions by marrying advanced free-energy methods with data-driven machine-learning interatomic potentials. We show that, for the ubiquitous and technologically essential system of water, a first-principles thermodynamic description not only leads to excellent agreement with experiments, but also reveals the crucial role of nuclear quantum fluctuations in modulating the thermodynamic stabilities of different phases of water.
AU - Cheng, Bingqing
AU - Engel, Edgar A.
AU - Behler, Jörg
AU - Dellago, Christoph
AU - Ceriotti, Michele
ID - 9689
IS - 4
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - Ab initio thermodynamics of liquid and solid water
VL - 116
ER -
TY - JOUR
AB - Background
Chlamydia are ancient intracellular pathogens with reduced, though strikingly conserved genome. Despite their parasitic lifestyle and isolated intracellular environment, these bacteria managed to avoid accumulation of deleterious mutations leading to subsequent genome degradation characteristic for many parasitic bacteria.
Results
We report pan-genomic analysis of sixteen species from genus Chlamydia including identification and functional annotation of orthologous genes, and characterization of gene gains, losses, and rearrangements. We demonstrate the overall genome stability of these bacteria as indicated by a large fraction of common genes with conserved genomic locations. On the other hand, extreme evolvability is confined to several paralogous gene families such as polymorphic membrane proteins and phospholipase D, and likely is caused by the pressure from the host immune system.
Conclusions
This combination of a large, conserved core genome and a small, evolvable periphery likely reflect the balance between the selective pressure towards genome reduction and the need to adapt to escape from the host immunity.
AU - Sigalova, Olga M.
AU - Chaplin, Andrei V.
AU - Bochkareva, Olga
AU - Shelyakin, Pavel V.
AU - Filaretov, Vsevolod A.
AU - Akkuratov, Evgeny E.
AU - Burskaia, Valentina
AU - Gelfand, Mikhail S.
ID - 6898
IS - 1
JF - BMC Genomics
TI - Chlamydia pan-genomic analysis reveals balance between host adaptation and selective pressure to genome reduction
VL - 20
ER -