OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Multi-Matroid Intersection via Iterative Refinement
Venue: arXiv cs.DS 2018
Year: 2018

We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constrains under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first $2$-approximation for finding a maximum-weight common independent set in $3$ matroids. Moreover, our $2$-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no better upper bound than $3$ was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.
BRDF Estimation of Complex Materials with Nested Learning
Venue: arXiv cs.CV 2018
Year: 2018

The estimation of the optical properties of a material from RGB-images is an important but extremely ill-posed problem in Computer Graphics. While recent works have successfully approached this problem even from just a single photograph, significant simplifications of the material model are assumed, limiting the usability of such methods. The detection of complex material properties such as anisotropy or Fresnel effect remains an unsolved challenge. We propose a novel method that predicts the model parameters of an artist-friendly, physically-based BRDF, from only two low-resolution shots of the material. Thanks to a novel combination of deep neural networks in a nested architecture, we are able to handle the ambiguities given by the non-orthogonality and non-convexity of the parameter space. To train the network, we generate a novel dataset of physically-based synthetic images. We prove that our model can recover new properties like anisotropy, index of refraction and a second reflectance color, for materials that have tinted specular reflections or whose albedo changes at glancing angles.
Uncalibrated Non-Rigid Factorisation by Independent Subspace Analysis
Venue: arXiv cs.CV 2018
Year: 2018

We propose a general, prior-free approach for the uncalibrated non-rigid structure-from-motion problem for modelling and analysis of non-rigid objects such as human faces. The word general refers to an approach that recovers the non-rigid affine structure and motion from 2D point correspondences by assuming that (1) the non-rigid shapes are generated by a linear combination of rigid 3D basis shapes, (2) that the non-rigid shapes are affine in nature, i.e., they can be modelled as deviations from the mean, rigid shape, (3) and that the basis shapes are statistically independent. In contrast to the majority of existing works, no prior information is assumed for the structure and motion apart from the assumption the that underlying basis shapes are statistically independent. The independent 3D shape bases are recovered by independent subspace analysis (ISA). Likewise, in contrast to the most previous approaches, no calibration information is assumed for affine cameras; the reconstruction is solved up to a global affine ambiguity that makes our approach simple but efficient. In the experiments, we evaluated the method with several standard data sets including a real face expression data set of 7200 faces with 2D point correspondences and unknown 3D structure and motion for which we obtained promising results.
REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel
Venue: arXiv cs.DS 2018
Year: 2018

Recently, considerable efforts have been devoted to approximately computing the global and local (i.e., incident to each node) triangle counts of a large graph stream represented as a sequence of edges. Existing approximate triangle counting algorithms rely on sampling techniques to reduce the computational cost. However, their estimation errors are significantly determined by the covariance between sampled triangles. Moreover, little attention has been paid to developing parallel one-pass streaming algorithms that can be used to fast and approximately count triangles on a multi-core machine or a cluster of machines. To solve these problems, we develop a novel parallel method REPT to significantly reduce the covariance (even completely eliminate the covariance for some cases) between sampled triangles. We theoretically prove that REPT is more accurate than parallelizing existing triangle count estimation algorithms in a direct manner. In addition, we also conduct extensive experiments on a variety of real-world graphs, and the results demonstrate that our method REPT is several times more accurate than state-of-the-art methods.
Construction of optimal locally recoverable codes and connection with hypergraph
Venue: arXiv cs.IT 2018
Year: 2018

Recently, it was discovered by several authors that a $q$-ary optimal locally recoverable code, i.e., a locally recoverable code archiving the Singleton-type bound, can have length much bigger than $q+1$. This is quite different from the classical $q$-ary MDS codes where it is conjectured that the code length is upper bounded by $q+1$ (or $q+2$ for some special case). This discovery inspired some recent studies on length of an optimal locally recoverable code. It was shown in \cite{LXY} that a $q$-ary optimal locally recoverable code is unbounded for $d=3,4$. Soon after, it was proved that a $q$-ary optimal locally recoverable code with distance $d$ and locality $r$ can have length $Ω_{d,r}(q^{1 + 1/\lfloor(d-3)/2\rfloor})$. Recently, an explicit construction of $q$-ary optimal locally recoverable codes for distance $d=5,6$ was given in \cite{J18} and \cite{BCGLP}. In this paper, we further investigate construction optimal locally recoverable codes along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and \cite{J18}, we equip parity-check matrices with the Vandermond structure. It is turns out that a parity-check matrix with the Vandermond structure produces an optimal locally recoverable code must obey certain disjoint property for subsets of $\mathbb{F}_q$. To our surprise, this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in \cite{GXY} for $d\geq 7$. In addition, for $d=6$, we are able to remove the constraint required in \cite{J18} that $q$ is even.
Generalized Range Moves
Venue: arXiv cs.CV 2018
Year: 2018

We consider move-making algorithms for energy minimization of multi-label Markov Random Fields (MRFs). Since this is not a tractable problem in general, a commonly used heuristic is to minimize over subsets of labels and variables in an iterative procedure. Such methods include α-expansion, αβ-swap, and range-moves. In each iteration, a small subset of variables are active in the optimization, which diminishes their effectiveness, and increases the required number of iterations. In this paper, we present a method in which optimization can be carried out over all labels, and most, or all variables at once. Experiments show substantial improvement with respect to previous move-making algorithms.
The Statistical Dictionary-based String Matching Problem
Venue: arXiv cs.IR 2018
Year: 2018

In the Dictionary-based String Matching (DSM) problem, a retrieval system has access to a source sequence and stores the position of a certain number of strings in a posting table. When a user inquires the position of a string, the retrieval system, instead of searching in the source sequence directly, relies on the the posting table to answer the query more efficiently. In this paper, the Statistical DSM problem is a proposed as a statistical and information-theoretic formulation of the classic DSM problem in which both the source and the query have a statistical description while the strings stored in the posting sequence are described as a code. Through this formulation, we are able to define the efficiency of the retrieval system as the average cost in answering a users' query in the limit of sufficiently long source sequence. This formulation is used to study the retrieval performance for the case in which (i) all the strings of a given length, referred to as k-grams , and (ii) prefix-free codes.
MVPNet: Multi-View Point Regression Networks for 3D Object Reconstruction from A Single Image
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we address the problem of reconstructing an object's surface from a single image using generative networks. First, we represent a 3D surface with an aggregation of dense point clouds from multiple views. Each point cloud is embedded in a regular 2D grid aligned on an image plane of a viewpoint, making the point cloud convolution-favored and ordered so as to fit into deep network architectures. The point clouds can be easily triangulated by exploiting connectivities of the 2D grids to form mesh-based surfaces. Second, we propose an encoder-decoder network that generates such kind of multiple view-dependent point clouds from a single image by regressing their 3D coordinates and visibilities. We also introduce a novel geometric loss that is able to interpret discrepancy over 3D surfaces as opposed to 2D projective planes, resorting to the surface discretization on the constructed meshes. We demonstrate that the multi-view point regression network outperforms state-of-the-art methods with a significant improvement on challenging datasets.
Natural language understanding for task oriented dialog in the biomedical domain in a low resources context
Venue: arXiv cs.CL 2018
Year: 2018

In the biomedical domain, the lack of sharable datasets often limit the possibility of developing natural language processing systems, especially dialogue applications and natural language understanding models. To overcome this issue, we explore data generation using templates and terminologies and data augmentation approaches. Namely, we report our experiments using paraphrasing and word representations learned on a large EHR corpus with Fasttext and ELMo, to learn a NLU model without any available dataset. We evaluate on a NLU task of natural language queries in EHRs divided in slot-filling and intent classification sub-tasks. On the slot-filling task, we obtain a F-score of 0.76 with the ELMo representation; and on the classification task, a mean F-score of 0.71. Our results show that this method could be used to develop a baseline system.
Quantifying Filter Bubbles: Analyzing Surprise in Elections
Venue: arXiv cs.SI 2018
Year: 2018

This work analyses surprising elections, and attempts to quantify the notion of surprise in elections. A voter is surprised if their estimate of the winner (assumed to be based on a combination of the preferences of their social connections and popular media predictions) is different from the true winner. A voter's social connections are assumed to consist of contacts on social media and geographically proximate people. We propose a simple mathematical model for combining the global information (traditional media) as well as the local information (local neighbourhood) of a voter in the case of a two-candidate election. We show that an unbiased, influential media can nullify the effect of filter bubbles and result in a less surprised populace. Surprisingly, an influential media source biased towards the winners of the election also results in a less surprised populace. Our model shows that elections will be unsurprising for all of the voters with a high probability under certain assumptions on the social connection model in the presence of an influential, unbiased traditional media source. Our experiments with the UK-EU referendum (popularly known as Brexit) dataset support our theoretical predictions. Since surprising elections can lead to significant economic movements, it is a worthwhile endeavour to figure out the causes of surprising elections.
A class of linear codes with few weights
Venue: arXiv cs.IT 2018
Year: 2018

Linear codes have been an interesting topic in both theory and practice for many years. In this paper, a class of $q$-ary linear codes with few weights are presented and their weight distributions are determined using Gauss periods. Some of the linear codes obtained are optimal or almost optimal with respect to the Griesmer bound. As s applications, these linear codes can be used to construct secret sharing schemes with nice access structures.
An Interpretable Model for Scene Graph Generation
Venue: arXiv cs.CV 2018
Year: 2018

We propose an efficient and interpretable scene graph generator. We consider three types of features: visual, spatial and semantic, and we use a late fusion strategy such that each feature's contribution can be explicitly investigated. We study the key factors about these features that have the most impact on the performance, and also visualize the learned visual features for relationships and investigate the efficacy of our model. We won the champion of the OpenImages Visual Relationship Detection Challenge on Kaggle, where we outperform the 2nd place by 5\% (20\% relatively). We believe an accurate scene graph generator is a fundamental stepping stone for higher-level vision-language tasks such as image captioning and visual QA, since it provides a semantic, structured comprehension of an image that is beyond pixels and objects.
About the k-Error Linear Complexity over $\mathbb{F}_p$ of sequences of length 2$p$ with optimal three-level autocorrelation
Venue: arXiv cs.CR 2018
Year: 2018

We investigate the $k$-error linear complexity over $\mathbb{F}_p$ of binary sequences of length $2p$ with optimal three-level autocorrelation. These balanced sequences are constructed by cyclotomic classes of order four using a method presented by Ding et al.
Curricular Analytics: A Framework for Quantifying the Impact of Curricular Reforms and Pedagogical Innovations
Venue: arXiv cs.CY 2018
Year: 2018

In this paper we articulate a framework for quantifying the complexity of curricula based on their fundamental structural and instructional properties. We then introduce the notion of curricular analytics as a means of relating curricular complexity to student success outcomes, and we demonstrate the usefulness of curricular analytics by applying them to a number of important problems.
Multilevel-Coded Pulse-Position Modulation for Covert Communications over Binary-Input Discrete Memoryless Channels
Venue: arXiv cs.IT 2018
Year: 2018

We develop a low-complexity coding scheme to achieve covert communications over binary-input discrete memoryless channels (BI-DMCs). We circumvent the impossibility of covert communication with linear codes by introducing non-linearity through the use of pulse position modulation (PPM) and multilevel coding (MLC). We show that the MLC-PPM scheme exhibits many appealing properties; in particular, the channel at a given index level remains stationary as the number of level increases, which allows one to use families of channel capacity- and channel resolvability-achieving codes to concretely instantiate the covert communication scheme.
Robustness via curvature regularization, and vice versa
Venue: arXiv cs.LG 2018
Year: 2018

State-of-the-art classifiers have been shown to be largely vulnerable to adversarial perturbations. One of the most effective strategies to improve robustness is adversarial training. In this paper, we investigate the effect of adversarial training on the geometry of the classification landscape and decision boundaries. We show in particular that adversarial training leads to a significant decrease in the curvature of the loss surface with respect to inputs, leading to a drastically more "linear" behaviour of the network. Using a locally quadratic approximation, we provide theoretical evidence on the existence of a strong relation between large robustness and small curvature. To further show the importance of reduced curvature for improving the robustness, we propose a new regularizer that directly minimizes curvature of the loss surface, and leads to adversarial robustness that is on par with adversarial training. Besides being a more efficient and principled alternative to adversarial training, the proposed regularizer confirms our claims on the importance of exhibiting quasi-linear behavior in the vicinity of data points in order to achieve robustness.
Costless: Optimizing Cost of Serverless Computing through Function Fusion and Placement
Venue: arXiv cs.DC 2018
Year: 2018

Serverless computing has recently experienced significant adoption by several applications, especially Internet of Things (IoT) applications. In serverless computing, rather than deploying and managing dedicated virtual machines, users are able to deploy individual functions, and pay only for the time that their code is actually executing. However, since serverless platforms are relatively new, they have a completely different pricing model that depends on the memory, duration, and the number of executions of a sequence/workflow of functions. In this paper we present an algorithm that optimizes the price of serverless applications in AWS Lambda. We first describe the factors affecting price of serverless applications which include: (1) fusing a sequence of functions, (2) splitting functions across edge and cloud resources, and (3) allocating the memory for each function. We then present an efficient algorithm to explore different function fusion-placement solutions and find the solution that optimizes the application's price while keeping the latency under a certain threshold. Our results on image processing workflows show that the algorithm can find solutions optimizing the price by more than 35%-57% with only 5%-15% increase in latency. We also show that our algorithm can find non-trivial memory configurations that reduce both latency and price.
Estimation of Inter-Sentiment Correlations Employing Deep Neural Network Models
Venue: arXiv cs.CL 2018
Year: 2018

This paper focuses on sentiment mining and sentiment correlation analysis of web events. Although neural network models have contributed a lot to mining text information, little attention is paid to analysis of the inter-sentiment correlations. This paper fills the gap between sentiment calculation and inter-sentiment correlations. In this paper, the social emotion is divided into six categories: love, joy, anger, sadness, fear, and surprise. Two deep neural network models are presented for sentiment calculation. Three datasets - the titles, the bodies, the comments of news articles - are collected, covering both objective and subjective texts in varying lengths (long and short). From each dataset, three kinds of features are extracted: explicit expression, implicit expression, and alphabet characters. The performance of the two models are analyzed, with respect to each of the three kinds of the features. There is controversial phenomenon on the interpretation of anger (fn) and love (gd). In subjective text, other emotions are easily to be considered as anger. By contrast, in objective news bodies and titles, it is easy to regard text as caused love (gd). It means, journalist may want to arouse emotion love by writing news, but cause anger after the news is published. This result reflects the sentiment complexity and unpredictability.
Object Detection based Deep Unsupervised Hashing
Venue: arXiv cs.CV 2018
Year: 2018

Recently, similarity-preserving hashing methods have been extensively studied for large-scale image retrieval. Compared with unsupervised hashing, supervised hashing methods for labeled data have usually better performance by utilizing semantic label information. Intuitively, for unlabeled data, it will improve the performance of unsupervised hashing methods if we can first mine some supervised semantic 'label information' from unlabeled data and then incorporate the 'label information' into the training process. Thus, in this paper, we propose a novel Object Detection based Deep Unsupervised Hashing method (ODDUH). Specifically, a pre-trained object detection model is utilized to mining supervised 'label information', which is used to guide the learning process to generate high-quality hash codes.Extensive experiments on two public datasets demonstrate that the proposed method outperforms the state-of-the-art unsupervised hashing methods in the image retrieval task.
OCLEP+: One-class Anomaly and Intrusion Detection Using Minimal Length of Emerging Patterns
Venue: arXiv cs.LG 2018
Year: 2018

This paper presents a method called One-class Classification using Length statistics of Emerging Patterns Plus (OCLEP+).
Forward Stability of ResNet and Its Variants
Venue: arXiv cs.CV 2018
Year: 2018

The residual neural network (ResNet) is a popular deep network architecture which has the ability to obtain high-accuracy results on several image processing problems. In order to analyze the behavior and structure of ResNet, recent work has been on establishing connections between ResNets and continuous-time optimal control problems. In this work, we show that the post-activation ResNet is related to an optimal control problem with differential inclusions, and provide continuous-time stability results for the differential inclusion associated with ResNet. Motivated by the stability conditions, we show that alterations of either the architecture or the optimization problem can generate variants of ResNet which improve the theoretical stability bounds. In addition, we establish stability bounds for the full (discrete) network associated with two variants of ResNet, in particular, bounds on the growth of the features and a measure of the sensitivity of the features with respect to perturbations. These results also help to show the relationship between the depth, regularization, and stability of the feature space. Computational experiments on the proposed variants show that the accuracy of ResNet is preserved and that the accuracy seems to be monotone with respect to the depth and various corruptions.
Average-Case Information Complexity of Learning
Venue: arXiv cs.LG 2018
Year: 2018

How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension $d$? Previous works have shown that even for $d=1$ the amount of information may be unbounded (tend to $\infty$ with the universe size). Can it be that all concepts in the class require leaking a large amount of information? We show that typically concepts do not require leakage. There exists a proper learning algorithm that reveals $O(d)$ bits of information for most concepts in the class. This result is a special case of a more general phenomenon we explore. If there is a low information learner when the algorithm {\em knows} the underlying distribution on inputs, then there is a learner that reveals little information on an average concept {\em without knowing} the distribution on inputs.