Paper Group ANR 484
Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis. Generalization for Adaptively-chosen Estimators via Stable Median. Reasoning in Non-Probabilistic Uncertainty: Logic Programming and Neural-Symbolic Computing as Examples. ALCN: Meta-Learning for Contrast Normalization Applie …
Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis
| Title | Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis |
| Authors | Houman Owhadi, Clint Scovel |
| Abstract | We show how the discovery of robust scalable numerical solvers for arbitrary bounded linear operators can be automated as a Game Theory problem by reformulating the process of computing with partial information and limited resources as that of playing underlying hierarchies of adversarial information games. When the solution space is a Banach space $B$ endowed with a quadratic norm $\cdot$, the optimal measure (mixed strategy) for such games (e.g. the adversarial recovery of $u\in B$, given partial measurements $[\phi_i, u]$ with $\phi_i\in B^*$, using relative error in $\cdot$-norm as a loss) is a centered Gaussian field $\xi$ solely determined by the norm $\cdot$, whose conditioning (on measurements) produces optimal bets. When measurements are hierarchical, the process of conditioning this Gaussian field produces a hierarchy of elementary bets (gamblets). These gamblets generalize the notion of Wavelets and Wannier functions in the sense that they are adapted to the norm $\cdot$ and induce a multi-resolution decomposition of $B$ that is adapted to the eigensubspaces of the operator defining the norm $\cdot$. When the operator is localized, we show that the resulting gamblets are localized both in space and frequency and introduce the Fast Gamblet Transform (FGT) with rigorous accuracy and (near-linear) complexity estimates. As the FFT can be used to solve and diagonalize arbitrary PDEs with constant coefficients, the FGT can be used to decompose a wide range of continuous linear operators (including arbitrary continuous linear bijections from $H^s_0$ to $H^{-s}$ or to $L^2$) into a sequence of independent linear systems with uniformly bounded condition numbers and leads to $\mathcal{O}(N \operatorname{polylog} N)$ solvers and eigenspace adapted Multiresolution Analysis (resulting in near linear complexity approximation of all eigensubspaces). |
| Tasks | |
| Published | 2017-03-31 |
| URL | http://arxiv.org/abs/1703.10761v2 |
| http://arxiv.org/pdf/1703.10761v2.pdf | |
| PWC | https://paperswithcode.com/paper/universal-scalable-robust-solvers-from |
| Repo | |
| Framework | |
Generalization for Adaptively-chosen Estimators via Stable Median
| Title | Generalization for Adaptively-chosen Estimators via Stable Median |
| Authors | Vitaly Feldman, Thomas Steinke |
| Abstract | Datasets are often reused to perform multiple statistical analyses in an adaptive way, in which each analysis may depend on the outcomes of previous analyses on the same dataset. Standard statistical guarantees do not account for these dependencies and little is known about how to provably avoid overfitting and false discovery in the adaptive setting. We consider a natural formalization of this problem in which the goal is to design an algorithm that, given a limited number of i.i.d.~samples from an unknown distribution, can answer adaptively-chosen queries about that distribution. We present an algorithm that estimates the expectations of $k$ arbitrary adaptively-chosen real-valued estimators using a number of samples that scales as $\sqrt{k}$. The answers given by our algorithm are essentially as accurate as if fresh samples were used to evaluate each estimator. In contrast, prior work yields error guarantees that scale with the worst-case sensitivity of each estimator. We also give a version of our algorithm that can be used to verify answers to such queries where the sample complexity depends logarithmically on the number of queries $k$ (as in the reusable holdout technique). Our algorithm is based on a simple approximate median algorithm that satisfies the strong stability guarantees of differential privacy. Our techniques provide a new approach for analyzing the generalization guarantees of differentially private algorithms. |
| Tasks | |
| Published | 2017-06-15 |
| URL | http://arxiv.org/abs/1706.05069v1 |
| http://arxiv.org/pdf/1706.05069v1.pdf | |
| PWC | https://paperswithcode.com/paper/generalization-for-adaptively-chosen |
| Repo | |
| Framework | |
Reasoning in Non-Probabilistic Uncertainty: Logic Programming and Neural-Symbolic Computing as Examples
| Title | Reasoning in Non-Probabilistic Uncertainty: Logic Programming and Neural-Symbolic Computing as Examples |
| Authors | Tarek R. Besold, Artur d’Avila Garcez, Keith Stenning, Leendert van der Torre, Michiel van Lambalgen |
| Abstract | This article aims to achieve two goals: to show that probability is not the only way of dealing with uncertainty (and even more, that there are kinds of uncertainty which are for principled reasons not addressable with probabilistic means); and to provide evidence that logic-based methods can well support reasoning with uncertainty. For the latter claim, two paradigmatic examples are presented: Logic Programming with Kleene semantics for modelling reasoning from information in a discourse, to an interpretation of the state of affairs of the intended model, and a neural-symbolic implementation of Input/Output logic for dealing with uncertainty in dynamic normative contexts. |
| Tasks | |
| Published | 2017-01-18 |
| URL | http://arxiv.org/abs/1701.05226v2 |
| http://arxiv.org/pdf/1701.05226v2.pdf | |
| PWC | https://paperswithcode.com/paper/reasoning-in-non-probabilistic-uncertainty |
| Repo | |
| Framework | |
ALCN: Meta-Learning for Contrast Normalization Applied to Robust 3D Pose Estimation
| Title | ALCN: Meta-Learning for Contrast Normalization Applied to Robust 3D Pose Estimation |
| Authors | Mahdi Rad, Peter M. Roth, Vincent Lepetit |
| Abstract | To be robust to illumination changes when detecting objects in images, the current trend is to train a Deep Network with training images captured under many different lighting conditions. Unfortunately, creating such a training set is very cumbersome, or sometimes even impossible, for some applications such as 3D pose estimation of specific objects, which is the application we focus on in this paper. We therefore propose a novel illumination normalization method that lets us learn to detect objects and estimate their 3D pose under challenging illumination conditions from very few training samples. Our key insight is that normalization parameters should adapt to the input image. In particular, we realized this via a Convolutional Neural Network trained to predict the parameters of a generalization of the Difference-of-Gaussians method. We show that our method significantly outperforms standard normalization methods and demonstrate it on two challenging 3D detection and pose estimation problems. |
| Tasks | 3D Pose Estimation, Meta-Learning, Pose Estimation |
| Published | 2017-08-31 |
| URL | http://arxiv.org/abs/1708.09633v1 |
| http://arxiv.org/pdf/1708.09633v1.pdf | |
| PWC | https://paperswithcode.com/paper/alcn-meta-learning-for-contrast-normalization |
| Repo | |
| Framework | |
SAGA and Restricted Strong Convexity
| Title | SAGA and Restricted Strong Convexity |
| Authors | Chao Qu, Yan Li, Huan Xu |
| Abstract | SAGA is a fast incremental gradient method on the finite sum problem and its effectiveness has been tested on a vast of applications. In this paper, we analyze SAGA on a class of non-strongly convex and non-convex statistical problem such as Lasso, group Lasso, Logistic regression with $\ell_1$ regularization, linear regression with SCAD regularization and Correct Lasso. We prove that SAGA enjoys the linear convergence rate up to the statistical estimation accuracy, under the assumption of restricted strong convexity (RSC). It significantly extends the applicability of SAGA in convex and non-convex optimization. |
| Tasks | |
| Published | 2017-02-19 |
| URL | http://arxiv.org/abs/1702.05683v2 |
| http://arxiv.org/pdf/1702.05683v2.pdf | |
| PWC | https://paperswithcode.com/paper/saga-and-restricted-strong-convexity |
| Repo | |
| Framework | |
Provably noise-robust, regularised $k$-means clustering
| Title | Provably noise-robust, regularised $k$-means clustering |
| Authors | Shrinu Kushagra, Yaoliang Yu, Shai Ben-David |
| Abstract | We consider the problem of clustering in the presence of noise. That is, when on top of cluster structure, the data also contains a subset of \emph{unstructured} points. Our goal is to detect the clusters despite the presence of many unstructured points. Any algorithm that achieves this goal is noise-robust. We consider a regularisation method which converts any center-based clustering objective into a noise-robust one. We focus on the $k$-means objective and we prove that the regularised version of $k$-means is NP-Hard even for $k=1$. We consider two algorithms based on the convex (sdp and lp) relaxation of the regularised objective and prove robustness guarantees for both. The sdp and lp relaxation of the standard (non-regularised) $k$-means objective has been previously studied by [ABC+15]. Under the stochastic ball model of the data they show that the sdp-based algorithm recovers the underlying structure as long as the balls are separated by $\delta > 2\sqrt{2} + \epsilon$. We improve upon this result in two ways. First, we show recovery even for $\delta > 2 + \epsilon$. Second, our regularised algorithm recovers the balls even in the presence of noise so long as the number of noisy points is not too large. We complement our theoretical analysis with simulations and analyse the effect of various parameters like regularization constant, noise-level etc. on the performance of our algorithm. In the presence of noise, our algorithm performs better than $k$-means++ on MNIST. |
| Tasks | |
| Published | 2017-11-30 |
| URL | http://arxiv.org/abs/1711.11247v3 |
| http://arxiv.org/pdf/1711.11247v3.pdf | |
| PWC | https://paperswithcode.com/paper/provably-noise-robust-regularised-k-means |
| Repo | |
| Framework | |
Human-Level Intelligence or Animal-Like Abilities?
| Title | Human-Level Intelligence or Animal-Like Abilities? |
| Authors | Adnan Darwiche |
| Abstract | The vision systems of the eagle and the snake outperform everything that we can make in the laboratory, but snakes and eagles cannot build an eyeglass or a telescope or a microscope. (Judea Pearl) |
| Tasks | |
| Published | 2017-07-13 |
| URL | http://arxiv.org/abs/1707.04327v1 |
| http://arxiv.org/pdf/1707.04327v1.pdf | |
| PWC | https://paperswithcode.com/paper/human-level-intelligence-or-animal-like |
| Repo | |
| Framework | |
Understanding the complexity of #SAT using knowledge compilation
| Title | Understanding the complexity of #SAT using knowledge compilation |
| Authors | Florent Capelli |
| Abstract | Two main techniques have been used so far to solve the #P-hard problem #SAT. The first one, used in practice, is based on an extension of DPLL for model counting called exhaustive DPLL. The second approach, more theoretical, exploits the structure of the input to compute the number of satisfying assignments by usually using a dynamic programming scheme on a decomposition of the formula. In this paper, we make a first step toward the separation of these two techniques by exhibiting a family of formulas that can be solved in polynomial time with the first technique but needs an exponential time with the second one. We show this by observing that both techniques implicitely construct a very specific boolean circuit equivalent to the input formula. We then show that every beta-acyclic formula can be represented by a polynomial size circuit corresponding to the first method and exhibit a family of beta-acyclic formulas which cannot be represented by polynomial size circuits corresponding to the second method. This result shed a new light on the complexity of #SAT and related problems on beta-acyclic formulas. As a byproduct, we give new handy tools to design algorithms on beta-acyclic hypergraphs. |
| Tasks | |
| Published | 2017-01-05 |
| URL | http://arxiv.org/abs/1701.01461v1 |
| http://arxiv.org/pdf/1701.01461v1.pdf | |
| PWC | https://paperswithcode.com/paper/understanding-the-complexity-of-sat-using |
| Repo | |
| Framework | |
Inverse Reinforcement Learning from Summary Data
| Title | Inverse Reinforcement Learning from Summary Data |
| Authors | Antti Kangasrääsiö, Samuel Kaski |
| Abstract | Inverse reinforcement learning (IRL) aims to explain observed strategic behavior by fitting reinforcement learning models to behavioral data. However, traditional IRL methods are only applicable when the observations are in the form of state-action paths. This assumption may not hold in many real-world modeling settings, where only partial or summarized observations are available. In general, we may assume that there is a summarizing function $\sigma$, which acts as a filter between us and the true state-action paths that constitute the demonstration. Some initial approaches to extending IRL to such situations have been presented, but with very specific assumptions about the structure of $\sigma$, such as that only certain state observations are missing. This paper instead focuses on the most general case of the problem, where no assumptions are made about the summarizing function, except that it can be evaluated. We demonstrate that inference is still possible. The paper presents exact and approximate inference algorithms that allow full posterior inference, which is particularly important for assessing parameter uncertainty in this challenging inference situation. Empirical scalability is demonstrated to reasonably sized problems, and practical applicability is demonstrated by estimating the posterior for a cognitive science RL model based on an observed user’s task completion time only. |
| Tasks | |
| Published | 2017-03-28 |
| URL | http://arxiv.org/abs/1703.09700v3 |
| http://arxiv.org/pdf/1703.09700v3.pdf | |
| PWC | https://paperswithcode.com/paper/inverse-reinforcement-learning-from-summary |
| Repo | |
| Framework | |
A Computer Vision Pipeline for Automated Determination of Cardiac Structure and Function and Detection of Disease by Two-Dimensional Echocardiography
| Title | A Computer Vision Pipeline for Automated Determination of Cardiac Structure and Function and Detection of Disease by Two-Dimensional Echocardiography |
| Authors | Jeffrey Zhang, Sravani Gajjala, Pulkit Agrawal, Geoffrey H. Tison, Laura A. Hallock, Lauren Beussink-Nelson, Eugene Fan, Mandar A. Aras, ChaRandle Jordan, Kirsten E. Fleischmann, Michelle Melisko, Atif Qasim, Alexei Efros, Sanjiv J. Shah, Ruzena Bajcsy, Rahul C. Deo |
| Abstract | Automated cardiac image interpretation has the potential to transform clinical practice in multiple ways including enabling low-cost serial assessment of cardiac function in the primary care and rural setting. We hypothesized that advances in computer vision could enable building a fully automated, scalable analysis pipeline for echocardiogram (echo) interpretation. Our approach entailed: 1) preprocessing; 2) convolutional neural networks (CNN) for view identification, image segmentation, and phasing of the cardiac cycle; 3) quantification of chamber volumes and left ventricular mass; 4) particle tracking to compute longitudinal strain; and 5) targeted disease detection. CNNs accurately identified views (e.g. 99% for apical 4-chamber) and segmented individual cardiac chambers. Cardiac structure measurements agreed with study report values (e.g. mean absolute deviations (MAD) of 7.7 mL/kg/m2 for left ventricular diastolic volume index, 2918 studies). We computed automated ejection fraction and longitudinal strain measurements (within 2 cohorts), which agreed with commercial software-derived values [for ejection fraction, MAD=5.3%, N=3101 studies; for strain, MAD=1.5% (n=197) and 1.6% (n=110)], and demonstrated applicability to serial monitoring of breast cancer patients for trastuzumab cardiotoxicity. Overall, we found that, compared to manual measurements, automated measurements had superior performance across seven internal consistency metrics with an average increase in the Spearman correlation coefficient of 0.05 (p=0.02). Finally, we developed disease detection algorithms for hypertrophic cardiomyopathy and cardiac amyloidosis, with C-statistics of 0.93 and 0.84, respectively. Our pipeline lays the groundwork for using automated interpretation to support point-of-care handheld cardiac ultrasound and large-scale analysis of the millions of echos archived within healthcare systems. |
| Tasks | Semantic Segmentation |
| Published | 2017-06-22 |
| URL | http://arxiv.org/abs/1706.07342v7 |
| http://arxiv.org/pdf/1706.07342v7.pdf | |
| PWC | https://paperswithcode.com/paper/a-computer-vision-pipeline-for-automated |
| Repo | |
| Framework | |
Macquarie University at BioASQ 5b – Query-based Summarisation Techniques for Selecting the Ideal Answers
| Title | Macquarie University at BioASQ 5b – Query-based Summarisation Techniques for Selecting the Ideal Answers |
| Authors | Diego Molla-Aliod |
| Abstract | Macquarie University’s contribution to the BioASQ challenge (Task 5b Phase B) focused on the use of query-based extractive summarisation techniques for the generation of the ideal answers. Four runs were submitted, with approaches ranging from a trivial system that selected the first $n$ snippets, to the use of deep learning approaches under a regression framework. Our experiments and the ROUGE results of the five test batches of BioASQ indicate surprisingly good results for the trivial approach. Overall, most of our runs on the first three test batches achieved the best ROUGE-SU4 results in the challenge. |
| Tasks | |
| Published | 2017-06-07 |
| URL | http://arxiv.org/abs/1706.02095v2 |
| http://arxiv.org/pdf/1706.02095v2.pdf | |
| PWC | https://paperswithcode.com/paper/macquarie-university-at-bioasq-5b-query-based |
| Repo | |
| Framework | |
What’s in my closet?: Image classification using fuzzy logic
| Title | What’s in my closet?: Image classification using fuzzy logic |
| Authors | Amina E. Hussein |
| Abstract | A fuzzy system was created in MATLAB to identify an item of clothing as a dress, shirt, or pair of pants from a series of input images. The system was initialized using a high-contrast vector-image of each item of clothing as the state closest to a direct solution. Nine other user-input images (three of each item) were also used to determine the characteristic function of each item and recognize each pattern. Mamdani inference systems were used for edge location and identification of characteristic regions of interest for each item of clothing. Based on these non-dimensional trends, a second Mamdani fuzzy inference system was used to characterize each image as containing a shirt, a dress, or a pair of pants. An outline of the fuzzy inference system and image processing techniques used for creating an image pattern recognition system are discussed. |
| Tasks | Image Classification |
| Published | 2017-12-05 |
| URL | http://arxiv.org/abs/1712.01970v1 |
| http://arxiv.org/pdf/1712.01970v1.pdf | |
| PWC | https://paperswithcode.com/paper/whats-in-my-closet-image-classification-using |
| Repo | |
| Framework | |
Unsupervised Construction of Human Body Models Using Principles of Organic Computing
| Title | Unsupervised Construction of Human Body Models Using Principles of Organic Computing |
| Authors | Thomas Walther, Rolf P. Würtz |
| Abstract | Unsupervised learning of a generalizable model of the visual appearance of humans from video data is of major importance for computing systems interacting naturally with their users and others. We propose a step towards automatic behavior understanding by integrating principles of Organic Computing into the posture estimation cycle, thereby relegating the need for human intervention while simultaneously raising the level of system autonomy. The system extracts coherent motion from moving upper bodies and autonomously decides about limbs and their possible spatial relationships. The models from many videos are integrated into meta-models, which show good generalization to different individuals, backgrounds, and attire. These models allow robust interpretation of single video frames without temporal continuity and posture mimicking by an android robot. |
| Tasks | |
| Published | 2017-04-12 |
| URL | http://arxiv.org/abs/1704.03724v1 |
| http://arxiv.org/pdf/1704.03724v1.pdf | |
| PWC | https://paperswithcode.com/paper/unsupervised-construction-of-human-body |
| Repo | |
| Framework | |
Extractor-Based Time-Space Lower Bounds for Learning
| Title | Extractor-Based Time-Space Lower Bounds for Learning |
| Authors | Sumegha Garg, Ran Raz, Avishay Tal |
| Abstract | A matrix $M: A \times X \rightarrow {-1,1}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen uniformly at random and $b_i = M(a_i,x)$. Assume that $k,\ell, r$ are such that any submatrix of $M$ of at least $2^{-k} \cdot A$ rows and at least $2^{-\ell} \cdot X$ columns, has a bias of at most $2^{-r}$. We show that any learning algorithm for the learning problem corresponding to $M$ requires either a memory of size at least $\Omega\left(k \cdot \ell \right)$, or at least $2^{\Omega(r)}$ samples. The result holds even if the learner has an exponentially small success probability (of $2^{-\Omega(r)}$). In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least $\Omega\left((\log X) \cdot (\log A)\right)$ or an exponential number of samples, achieving a tight $\Omega\left((\log X) \cdot (\log A)\right)$ lower bound on the size of the memory, rather than a bound of $\Omega\left(\min\left{(\log X)^2,(\log A)^2\right}\right)$ obtained in previous works [R17,MM17b]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on [R17] that gave a general technique for proving memory-samples lower bounds. |
| Tasks | |
| Published | 2017-08-08 |
| URL | http://arxiv.org/abs/1708.02639v1 |
| http://arxiv.org/pdf/1708.02639v1.pdf | |
| PWC | https://paperswithcode.com/paper/extractor-based-time-space-lower-bounds-for |
| Repo | |
| Framework | |
Efficient Benchmarking of Algorithm Configuration Procedures via Model-Based Surrogates
| Title | Efficient Benchmarking of Algorithm Configuration Procedures via Model-Based Surrogates |
| Authors | Katharina Eggensperger, Marius Lindauer, Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown |
| Abstract | The optimization of algorithm (hyper-)parameters is crucial for achieving peak performance across a wide range of domains, ranging from deep neural networks to solvers for hard combinatorial problems. The resulting algorithm configuration (AC) problem has attracted much attention from the machine learning community. However, the proper evaluation of new AC procedures is hindered by two key hurdles. First, AC benchmarks are hard to set up. Second and even more significantly, they are computationally expensive: a single run of an AC procedure involves many costly runs of the target algorithm whose performance is to be optimized in a given AC benchmark scenario. One common workaround is to optimize cheap-to-evaluate artificial benchmark functions (e.g., Branin) instead of actual algorithms; however, these have different properties than realistic AC problems. Here, we propose an alternative benchmarking approach that is similarly cheap to evaluate but much closer to the original AC problem: replacing expensive benchmarks by surrogate benchmarks constructed from AC benchmarks. These surrogate benchmarks approximate the response surface corresponding to true target algorithm performance using a regression model, and the original and surrogate benchmark share the same (hyper-)parameter space. In our experiments, we construct and evaluate surrogate benchmarks for hyperparameter optimization as well as for AC problems that involve performance optimization of solvers for hard combinatorial problems, drawing training data from the runs of existing AC procedures. We show that our surrogate benchmarks capture overall important characteristics of the AC scenarios, such as high- and low-performing regions, from which they were derived, while being much easier to use and orders of magnitude cheaper to evaluate. |
| Tasks | Hyperparameter Optimization |
| Published | 2017-03-30 |
| URL | http://arxiv.org/abs/1703.10342v1 |
| http://arxiv.org/pdf/1703.10342v1.pdf | |
| PWC | https://paperswithcode.com/paper/efficient-benchmarking-of-algorithm |
| Repo | |
| Framework | |
