October 17, 2019

3217 words 16 mins read

Paper Group ANR 843

Efficient Statistics, in High Dimensions, from Truncated Samples. A Circuit-Level Amoeba-Inspired SAT Solver. FishEyeRecNet: A Multi-Context Collaborative Deep Network for Fisheye Image Rectification. Deep Joint Source-Channel Coding for Wireless Image Transmission. Notes on computational-to-statistical gaps: predictions using statistical physics. …

Efficient Statistics, in High Dimensions, from Truncated Samples


Title	Efficient Statistics, in High Dimensions, from Truncated Samples
Authors	Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, Manolis Zampetakis
Abstract	We provide an efficient algorithm for the classical problem, going back to Galton, Pearson, and Fisher, of estimating, with arbitrary accuracy the parameters of a multivariate normal distribution from truncated samples. Truncated samples from a $d$-variate normal ${\cal N}(\mathbf{\mu},\mathbf{\Sigma})$ means a samples is only revealed if it falls in some subset $S \subseteq \mathbb{R}^d$; otherwise the samples are hidden and their count in proportion to the revealed samples is also hidden. We show that the mean $\mathbf{\mu}$ and covariance matrix $\mathbf{\Sigma}$ can be estimated with arbitrary accuracy in polynomial-time, as long as we have oracle access to $S$, and $S$ has non-trivial measure under the unknown $d$-variate normal distribution. Additionally we show that without oracle access to $S$, any non-trivial estimation is impossible.
Tasks
Published	2018-09-11
URL	http://arxiv.org/abs/1809.03986v1
PDF	http://arxiv.org/pdf/1809.03986v1.pdf
PWC	https://paperswithcode.com/paper/efficient-statistics-in-high-dimensions-from
Repo
Framework

A Circuit-Level Amoeba-Inspired SAT Solver


Title	A Circuit-Level Amoeba-Inspired SAT Solver
Authors	N. Takeuchi, M. Aono, Y. Hara-Azumi, C. L. Ayala
Abstract	AmbSAT (or AmoebaSAT) is a biologically-inspired stochastic local search (SLS) solver to explore solutions to the Boolean satisfiability problem (SAT). AmbSAT updates multiple variables in parallel at every iteration step, and thus AmbSAT can find solutions with a fewer number of iteration steps than some other conventional SLS solvers for a specific set of SAT instances. However, the parallelism of AmbSAT is not compatible with general-purpose microprocessors in that many clock cycles are required to execute each iteration; thus, AmbSAT requires special hardware that can exploit the parallelism of AmbSAT to quickly find solutions. In this paper, we propose a circuit model (hardware-friendly algorithm) that explores solutions to SAT in a similar way to AmbSAT, which we call circuit-level AmbSAT (CL-AmbSAT). We conducted numerical simulation to evaluate the search performance of CL-AmbSAT for a set of randomly generated SAT instances that was designed to estimate the scalability of our approach. Simulation results showed that CL-AmbSAT finds solutions with a fewer iteration number than a powerful SLS solver, ProbSAT, and outperforms even AmbSAT. Since CL-AmbSAT uses simple combinational logic to update variables, CL-AmbSAT can be easily implemented in various hardware.
Tasks
Published	2018-12-15
URL	https://arxiv.org/abs/1812.11792v3
PDF	https://arxiv.org/pdf/1812.11792v3.pdf
PWC	https://paperswithcode.com/paper/a-circuit-level-amoeba-inspired-sat-solver
Repo
Framework

FishEyeRecNet: A Multi-Context Collaborative Deep Network for Fisheye Image Rectification


Title	FishEyeRecNet: A Multi-Context Collaborative Deep Network for Fisheye Image Rectification
Authors	Xiaoqing Yin, Xinchao Wang, Jun Yu, Maojun Zhang, Pascal Fua, Dacheng Tao
Abstract	Images captured by fisheye lenses violate the pinhole camera assumption and suffer from distortions. Rectification of fisheye images is therefore a crucial preprocessing step for many computer vision applications. In this paper, we propose an end-to-end multi-context collaborative deep network for removing distortions from single fisheye images. In contrast to conventional approaches, which focus on extracting hand-crafted features from input images, our method learns high-level semantics and low-level appearance features simultaneously to estimate the distortion parameters. To facilitate training, we construct a synthesized dataset that covers various scenes and distortion parameter settings. Experiments on both synthesized and real-world datasets show that the proposed model significantly outperforms current state of the art methods. Our code and synthesized dataset will be made publicly available.
Tasks
Published	2018-04-13
URL	http://arxiv.org/abs/1804.04784v1
PDF	http://arxiv.org/pdf/1804.04784v1.pdf
PWC	https://paperswithcode.com/paper/fisheyerecnet-a-multi-context-collaborative
Repo
Framework

Deep Joint Source-Channel Coding for Wireless Image Transmission


Title	Deep Joint Source-Channel Coding for Wireless Image Transmission
Authors	Eirina Bourtsoulatze, David Burth Kurka, Deniz Gunduz
Abstract	We propose a joint source and channel coding (JSCC) technique for wireless image transmission that does not rely on explicit codes for either compression or error correction; instead, it directly maps the image pixel values to the complex-valued channel input symbols. We parameterize the encoder and decoder functions by two convolutional neural networks (CNNs), which are trained jointly, and can be considered as an autoencoder with a non-trainable layer in the middle that represents the noisy communication channel. Our results show that the proposed deep JSCC scheme outperforms digital transmission concatenating JPEG or JPEG2000 compression with a capacity achieving channel code at low signal-to-noise ratio (SNR) and channel bandwidth values in the presence of additive white Gaussian noise (AWGN). More strikingly, deep JSCC does not suffer from the ``cliff effect’', and it provides a graceful performance degradation as the channel SNR varies with respect to the SNR value assumed during training. In the case of a slow Rayleigh fading channel, deep JSCC learns noise resilient coded representations and significantly outperforms separation-based digital communication at all SNR and channel bandwidth values. \|
Tasks
Published	2018-09-04
URL	https://arxiv.org/abs/1809.01733v4
PDF	https://arxiv.org/pdf/1809.01733v4.pdf
PWC	https://paperswithcode.com/paper/deep-joint-source-channel-coding-for-wireless
Repo
Framework

Notes on computational-to-statistical gaps: predictions using statistical physics


Title	Notes on computational-to-statistical gaps: predictions using statistical physics
Authors	Afonso S. Bandeira, Amelia Perry, Alexander S. Wein
Abstract	In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances. The methods we describe here are based on mature, albeit non-rigorous, tools from statistical physics. These notes are based on a lecture series given by the authors at the Courant Institute of Mathematical Sciences in New York City, on May 16th, 2017.
Tasks
Published	2018-03-29
URL	http://arxiv.org/abs/1803.11132v2
PDF	http://arxiv.org/pdf/1803.11132v2.pdf
PWC	https://paperswithcode.com/paper/notes-on-computational-to-statistical-gaps
Repo
Framework

DCI: Discriminative and Contrast Invertible Descriptor


Title	DCI: Discriminative and Contrast Invertible Descriptor
Authors	Zhenwei Miao, Kim-Hui Yap, Xudong Jiang, Subbhuraam Sinduja, Zhenhua Wang
Abstract	Local feature descriptors have been widely used in fine-grained visual object search thanks to their robustness in scale and rotation variation and cluttered background. However, the performance of such descriptors drops under severe illumination changes. In this paper, we proposed a Discriminative and Contrast Invertible (DCI) local feature descriptor. In order to increase the discriminative ability of the descriptor under illumination changes, a Laplace gradient based histogram is proposed. A robust contrast flipping estimate is proposed based on the divergence of a local region. Experiments on fine-grained object recognition and retrieval applications demonstrate the superior performance of DCI descriptor to others.
Tasks	Object Recognition
Published	2018-12-31
URL	http://arxiv.org/abs/1901.00027v1
PDF	http://arxiv.org/pdf/1901.00027v1.pdf
PWC	https://paperswithcode.com/paper/dci-discriminative-and-contrast-invertible
Repo
Framework

A Continuation Method for Discrete Optimization and its Application to Nearest Neighbor Classification


Title	A Continuation Method for Discrete Optimization and its Application to Nearest Neighbor Classification
Authors	Ali Shameli, Yasin Abbasi-Yadkori
Abstract	The continuation method is a popular approach in non-convex optimization and computer vision. The main idea is to start from a simple function that can be minimized efficiently, and gradually transform it to the more complicated original objective function. The solution of the simpler problem is used as the starting point to solve the original problem. We show a continuation method for discrete optimization problems. Ideally, we would like the evolved function to be hill-climbing friendly and to have the same global minima as the original function. We show that the proposed continuation method is the best affine approximation of a transformation that is guaranteed to transform the function to a hill-climbing friendly function and to have the same global minima. We show the effectiveness of the proposed technique in the problem of nearest neighbor classification. Although nearest neighbor methods are often competitive in terms of sample efficiency, the computational complexity in the test phase has been a major obstacle in their applicability in big data problems. Using the proposed continuation method, we show an improved graph-based nearest neighbor algorithm. The method is readily understood and easy to implement. We show how the computational complexity of the method in the test phase scales gracefully with the size of the training set, a property that is particularly important in big data applications.
Tasks
Published	2018-02-10
URL	http://arxiv.org/abs/1802.03482v1
PDF	http://arxiv.org/pdf/1802.03482v1.pdf
PWC	https://paperswithcode.com/paper/a-continuation-method-for-discrete
Repo
Framework

CRAM: Clued Recurrent Attention Model


Title	CRAM: Clued Recurrent Attention Model
Authors	Minki Chung, Sungzoon Cho
Abstract	To overcome the poor scalability of convolutional neural network, recurrent attention model(RAM) selectively choose what and where to look on the image. By directing recurrent attention model how to look the image, RAM can be even more successful in that the given clue narrow down the scope of the possible focus zone. In this perspective, this work proposes clued recurrent attention model (CRAM) which add clue or constraint on the RAM better problem solving. CRAM follows encoder-decoder framework, encoder utilizes recurrent attention model with spatial transformer network and decoder which varies depending on the task. To ensure the performance, CRAM tackles two computer vision task. One is the image classification task, with clue given as the binary image saliency which indicates the approximate location of object. The other is the inpainting task, with clue given as binary mask which indicates the occluded part. In both tasks, CRAM shows better performance than existing methods showing the successful extension of RAM.
Tasks	Image Classification
Published	2018-04-28
URL	http://arxiv.org/abs/1804.10844v1
PDF	http://arxiv.org/pdf/1804.10844v1.pdf
PWC	https://paperswithcode.com/paper/cram-clued-recurrent-attention-model
Repo
Framework

Facial Landmarks Detection by Self-Iterative Regression based Landmarks-Attention Network


Title	Facial Landmarks Detection by Self-Iterative Regression based Landmarks-Attention Network
Authors	Tao Hu, Honggang Qi, Jizheng Xu, Qingming Huang
Abstract	Cascaded Regression (CR) based methods have been proposed to solve facial landmarks detection problem, which learn a series of descent directions by multiple cascaded regressors separately trained in coarse and fine stages. They outperform the traditional gradient descent based methods in both accuracy and running speed. However, cascaded regression is not robust enough because each regressor’s training data comes from the output of previous regressor. Moreover, training multiple regressors requires lots of computing resources, especially for deep learning based methods. In this paper, we develop a Self-Iterative Regression (SIR) framework to improve the model efficiency. Only one self-iterative regressor is trained to learn the descent directions for samples from coarse stages to fine stages, and parameters are iteratively updated by the same regressor. Specifically, we proposed Landmarks-Attention Network (LAN) as our regressor, which concurrently learns features around each landmark and obtains the holistic location increment. By doing so, not only the rest of regressors are removed to simplify the training process, but the number of model parameters is significantly decreased. The experiments demonstrate that with only 3.72M model parameters, our proposed method achieves the state-of-the-art performance.
Tasks	Face Alignment
Published	2018-03-18
URL	http://arxiv.org/abs/1803.06598v1
PDF	http://arxiv.org/pdf/1803.06598v1.pdf
PWC	https://paperswithcode.com/paper/facial-landmarks-detection-by-self-iterative
Repo
Framework

Self-Erasing Network for Integral Object Attention


Title	Self-Erasing Network for Integral Object Attention
Authors	Qibin Hou, Peng-Tao Jiang, Yunchao Wei, Ming-Ming Cheng
Abstract	Recently, adversarial erasing for weakly-supervised object attention has been deeply studied due to its capability in localizing integral object regions. However, such a strategy raises one key problem that attention regions will gradually expand to non-object regions as training iterations continue, which significantly decreases the quality of the produced attention maps. To tackle such an issue as well as promote the quality of object attention, we introduce a simple yet effective Self-Erasing Network (SeeNet) to prohibit attentions from spreading to unexpected background regions. In particular, SeeNet leverages two self-erasing strategies to encourage networks to use reliable object and background cues for learning to attention. In this way, integral object regions can be effectively highlighted without including much more background regions. To test the quality of the generated attention maps, we employ the mined object regions as heuristic cues for learning semantic segmentation models. Experiments on Pascal VOC well demonstrate the superiority of our SeeNet over other state-of-the-art methods.
Tasks	Semantic Segmentation
Published	2018-10-23
URL	http://arxiv.org/abs/1810.09821v1
PDF	http://arxiv.org/pdf/1810.09821v1.pdf
PWC	https://paperswithcode.com/paper/self-erasing-network-for-integral-object
Repo
Framework

Accounting for the Neglected Dimensions of AI Progress


Title	Accounting for the Neglected Dimensions of AI Progress
Authors	Fernando Martínez-Plumed, Shahar Avin, Miles Brundage, Allan Dafoe, Sean Ó hÉigeartaigh, José Hernández-Orallo
Abstract	We analyze and reframe AI progress. In addition to the prevailing metrics of performance, we highlight the usually neglected costs paid in the development and deployment of a system, including: data, expert knowledge, human oversight, software resources, computing cycles, hardware and network facilities, development time, etc. These costs are paid throughout the life cycle of an AI system, fall differentially on different individuals, and vary in magnitude depending on the replicability and generality of the AI solution. The multidimensional performance and cost space can be collapsed to a single utility metric for a user with transitive and complete preferences. Even absent a single utility function, AI advances can be generically assessed by whether they expand the Pareto (optimal) surface. We explore a subset of these neglected dimensions using the two case studies of Alpha* and ALE. This broadened conception of progress in AI should lead to novel ways of measuring success in AI, and can help set milestones for future progress.
Tasks
Published	2018-06-02
URL	http://arxiv.org/abs/1806.00610v1
PDF	http://arxiv.org/pdf/1806.00610v1.pdf
PWC	https://paperswithcode.com/paper/accounting-for-the-neglected-dimensions-of-ai
Repo
Framework

Poincaré GloVe: Hyperbolic Word Embeddings


Title	Poincaré GloVe: Hyperbolic Word Embeddings
Authors	Alexandru Tifrea, Gary Bécigneul, Octavian-Eugen Ganea
Abstract	Words are not created equal. In fact, they form an aristocratic graph with a latent hierarchical structure that the next generation of unsupervised learned word embeddings should reveal. In this paper, justified by the notion of delta-hyperbolicity or tree-likeliness of a space, we propose to embed words in a Cartesian product of hyperbolic spaces which we theoretically connect to the Gaussian word embeddings and their Fisher geometry. This connection allows us to introduce a novel principled hypernymy score for word embeddings. Moreover, we adapt the well-known Glove algorithm to learn unsupervised word embeddings in this type of Riemannian manifolds. We further explain how to solve the analogy task using the Riemannian parallel transport that generalizes vector arithmetics to this new type of geometry. Empirically, based on extensive experiments, we prove that our embeddings, trained unsupervised, are the first to simultaneously outperform strong and popular baselines on the tasks of similarity, analogy and hypernymy detection. In particular, for word hypernymy, we obtain new state-of-the-art on fully unsupervised WBLESS classification accuracy.
Tasks	Word Embeddings
Published	2018-10-15
URL	http://arxiv.org/abs/1810.06546v2
PDF	http://arxiv.org/pdf/1810.06546v2.pdf
PWC	https://paperswithcode.com/paper/poincare-glove-hyperbolic-word-embeddings
Repo
Framework

Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning


Title	Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
Authors	Dong Yin, Yudong Chen, Kannan Ramchandran, Peter Bartlett
Abstract	We study robust distributed learning that involves minimizing a non-convex loss function with saddle points. We consider the Byzantine setting where some worker machines have abnormal or even arbitrary and adversarial behavior. In this setting, the Byzantine machines may create fake local minima near a saddle point that is far away from any true local minimum, even when robust gradient estimators are used. We develop ByzantinePGD, a robust first-order algorithm that can provably escape saddle points and fake local minima, and converge to an approximate true local minimizer with low iteration complexity. As a by-product, we give a simpler algorithm and analysis for escaping saddle points in the usual non-Byzantine setting. We further discuss three robust gradient estimators that can be used in ByzantinePGD, including median, trimmed mean, and iterative filtering. We characterize their performance in concrete statistical settings, and argue for their near-optimality in low and high dimensional regimes.
Tasks
Published	2018-06-14
URL	http://arxiv.org/abs/1806.05358v3
PDF	http://arxiv.org/pdf/1806.05358v3.pdf
PWC	https://paperswithcode.com/paper/defending-against-saddle-point-attack-in
Repo
Framework

On Learning Causal Structures from Non-Experimental Data without Any Faithfulness Assumption


Title	On Learning Causal Structures from Non-Experimental Data without Any Faithfulness Assumption
Authors	Hanti Lin, Jiji Zhang
Abstract	Consider the problem of learning, from non-experimental data, the causal (Markov equivalence) structure of the true, unknown causal Bayesian network (CBN) on a given, fixed set of (categorical) variables. This learning problem is known to be so hard that there is no learning algorithm that converges to the truth for all possible CBNs (on the given set of variables). So the convergence property has to be sacrificed for some CBNs—but for which? In response, the standard practice has been to design and employ learning algorithms that secure the convergence property for at least all the CBNs that satisfy the famous faithfulness condition, which implies sacrificing the convergence property for some CBNs that violate the faithfulness condition (Spirtes et al. 2000). This standard design practice can be justified by assuming—that is, accepting on faith—that the true, unknown CBN satisfies the faithfulness condition. But the real question is this: Is it possible to explain, without assuming the faithfulness condition or any of its weaker variants, why it is mandatory rather than optional to follow the standard design practice? This paper aims to answer the above question in the affirmative. We first define an array of modes of convergence to the truth as desiderata that might or might not be achieved by a causal learning algorithm. Those modes of convergence concern (i) how pervasive the domain of convergence is on the space of all possible CBNs and (ii) how uniformly the convergence happens. Then we prove a result to the following effect: for any learning algorithm that tackles the causal learning problem in question, if it achieves the best achievable mode of convergence (considered in this paper), then it must follow the standard design practice of converging to the truth for at least all CBNs that satisfy the faithfulness condition—it is a requirement, not an option.
Tasks
Published	2018-02-20
URL	https://arxiv.org/abs/1802.07051v2
PDF	https://arxiv.org/pdf/1802.07051v2.pdf
PWC	https://paperswithcode.com/paper/how-to-tackle-an-extremely-hard-learning
Repo
Framework

Multi-objective optimization to explicitly account for model complexity when learning Bayesian Networks


Title	Multi-objective optimization to explicitly account for model complexity when learning Bayesian Networks
Authors	Paolo Cazzaniga, Marco S. Nobile, Daniele Ramazzotti
Abstract	Bayesian Networks have been widely used in the last decades in many fields, to describe statistical dependencies among random variables. In general, learning the structure of such models is a problem with considerable theoretical interest that still poses many challenges. On the one hand, this is a well-known NP-complete problem, which is practically hardened by the huge search space of possible solutions. On the other hand, the phenomenon of I-equivalence, i.e., different graphical structures underpinning the same set of statistical dependencies, may lead to multimodal fitness landscapes further hindering maximum likelihood approaches to solve the task. Despite all these difficulties, greedy search methods based on a likelihood score coupled with a regularization term to account for model complexity, have been shown to be surprisingly effective in practice. In this paper, we consider the formulation of the task of learning the structure of Bayesian Networks as an optimization problem based on a likelihood score. Nevertheless, our approach do not adjust this score by means of any of the complexity terms proposed in the literature; instead, it accounts directly for the complexity of the discovered solutions by exploiting a multi-objective optimization procedure. To this extent, we adopt NSGA-II and define the first objective function to be the likelihood of a solution and the second to be the number of selected arcs. We thoroughly analyze the behavior of our method on a wide set of simulated data, and we discuss the performance considering the goodness of the inferred solutions both in terms of their objective functions and with respect to the retrieved structure. Our results show that NSGA-II can converge to solutions characterized by better likelihood and less arcs than classic approaches, although paradoxically frequently characterized by a lower similarity to the target network.
Tasks
Published	2018-08-03
URL	http://arxiv.org/abs/1808.01345v1
PDF	http://arxiv.org/pdf/1808.01345v1.pdf
PWC	https://paperswithcode.com/paper/multi-objective-optimization-to-explicitly
Repo
Framework