OpenRaiser/Intern-Atlas huggingface dataset:
Millimeter Wave Beam-Selection Using Out-of-Band Spatial Information
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave (mmWave) communication is one feasible solution for high data-rate applications like vehicular-to-everything communication and next generation cellular communication. Configuring mmWave links, which can be done through channel estimation or beam-selection, however, is a source of significant overhead. In this paper, we propose to use spatial information extracted at sub-6 GHz to help establish the mmWave link. First, we review the prior work on frequency dependent channel behavior and outline a simulation strategy to generate multi-band frequency dependent channels. Second, assuming: (i) narrowband channels and a fully digital architecture at sub-6 GHz; and (ii) wideband frequency selective channels, OFDM signaling, and an analog architecture at mmWave, we outline strategies to incorporate sub-6 GHz spatial information in mmWave compressed beam selection. We formulate compressed beam-selection as a weighted sparse signal recovery problem, and obtain the weighting information from sub-6 GHz channels. In addition, we outline a structured precoder/combiner design to tailor the training to out-of-band information. We also extend the proposed out-of-band aided compressed beam-selection approach to leverage information from all active OFDM subcarriers. The simulation results for achievable rate show that out-of-band aided beam-selection can reduce the training overhead of in-band only beam-selection by 4x.
Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces
Venue: arXiv cs.CG 2017
Year: 2017

We present a new algorithm for the widely used density-based clustering method DBscan. Our algorithm computes the DBscan-clustering in $O(n\log n)$ time in $\mathbb{R}^2$, irrespective of the scale parameter $\varepsilon$ (and assuming the second parameter MinPts is set to a fixed constant, as is the case in practice). Experiments show that the new algorithm is not only fast in theory, but that a slightly simplified version is competitive in practice and much less sensitive to the choice of $\varepsilon$ than the original DBscan algorithm. We also present an $O(n\log n)$ randomized algorithm for HDBscan in the plane---HDBscan is a hierarchical version of DBscan introduced recently---and we show how to compute an approximate version of HDBscan in near-linear time in any fixed dimension.
An Optimization Framework with Flexible Inexact Inner Iterations for Nonconvex and Nonsmooth Programming
Venue: arXiv cs.CV 2017
Year: 2017

In recent years, numerous vision and learning tasks have been (re)formulated as nonconvex and nonsmooth programmings(NNPs). Although some algorithms have been proposed for particular problems, designing fast and flexible optimization schemes with theoretical guarantee is a challenging task for general NNPs. It has been investigated that performing inexact inner iterations often benefit to special applications case by case, but their convergence behaviors are still unclear. Motivated by these practical experiences, this paper designs a novel algorithmic framework, named inexact proximal alternating direction method (IPAD) for solving general NNPs. We demonstrate that any numerical algorithms can be incorporated into IPAD for solving subproblems and the convergence of the resulting hybrid schemes can be consistently guaranteed by a series of simple error conditions. Beyond the guarantee in theory, numerical experiments on both synthesized and real-world data further demonstrate the superiority and flexibility of our IPAD framework for practical use.
Auto-clustering Output Layer: Automatic Learning of Latent Annotations in Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we discuss a different type of semi-supervised setting: a coarse level of labeling is available for all observations but the model has to learn a fine level of latent annotation for each one of them. Problems in this setting are likely to be encountered in many domains such as text categorization, protein function prediction, image classification as well as in exploratory scientific studies such as medical and genomics research. We consider this setting as simultaneously performed supervised classification (per the available coarse labels) and unsupervised clustering (within each one of the coarse labels) and propose a novel output layer modification called auto-clustering output layer (ACOL) that allows concurrent classification and clustering based on Graph-based Activity Regularization (GAR) technique. As the proposed output layer modification duplicates the softmax nodes at the output layer for each class, GAR allows for competitive learning between these duplicates on a traditional error-correction learning framework to ultimately enable a neural network to learn the latent annotations in this partially supervised setup. We demonstrate how the coarse label supervision impacts performance and helps propagate useful clustering information between sub-classes. Comparative tests on three of the most popular image datasets MNIST, SVHN and CIFAR-100 rigorously demonstrate the effectiveness and competitiveness of the proposed approach.
II-FCN for skin lesion analysis towards melanoma detection
Venue: arXiv cs.CV 2017
Year: 2017

Dermoscopy image detection stays a tough task due to the weak distinguishable property of the object.Although the deep convolution neural network signifigantly boosted the performance on prevelance computer vision tasks in recent years,there remains a room to explore more robust and precise models to the problem of low contrast image segmentation.Towards the challenge of Lesion Segmentation in ISBI 2017,we built a symmetrical identity inception fully convolution network which is based on only 10 reversible inception blocks,every block composed of four convolution branches with combination of different layer depth and kernel size to extract sundry semantic features.Then we proposed an approximate loss function for jaccard index metrics to train our model.To overcome the drawbacks of traditional convolution,we adopted the dilation convolution and conditional random field method to rectify our segmentation.We also introduced multiple ways to prevent the problem of overfitting.The experimental results shows that our model achived jaccard index of 0.82 and kept learning from epoch to epoch.
Bayesian Verification under Model Uncertainty
Venue: arXiv cs.SE 2017
Year: 2017

Machine learning enables systems to build and update domain models based on runtime observations. In this paper, we study statistical model checking and runtime verification for systems with this ability. Two challenges arise: (1) Models built from limited runtime data yield uncertainty to be dealt with. (2) There is no definition of satisfaction w.r.t. uncertain hypotheses. We propose such a definition of subjective satisfaction based on recently introduced satisfaction functions. We also propose the BV algorithm as a Bayesian solution to runtime verification of subjective satisfaction under model uncertainty. BV provides user-definable stochastic bounds for type I and II errors. We discuss empirical results from an example application to illustrate our ideas.
MILD: Multi-Index hashing for Loop closure Detection
Venue: arXiv cs.CV 2017
Year: 2017

Loop Closure Detection (LCD) has been proved to be extremely useful in global consistent visual Simultaneously Localization and Mapping (SLAM) and appearance-based robot relocalization. Methods exploiting binary features in bag of words representation have recently gained a lot of popularity for their efficiency, but suffer from low recall due to the inherent drawback that high dimensional binary feature descriptors lack well-defined centroids. In this paper, we propose a realtime LCD approach called MILD (Multi-Index Hashing for Loop closure Detection), in which image similarity is measured by feature matching directly to achieve high recall without introducing extra computational complexity with the aid of Multi-Index Hashing (MIH). A theoretical analysis of the approximate image similarity measurement using MIH is presented, which reveals the trade-off between efficiency and accuracy from a probabilistic perspective. Extensive comparisons with state-of-the-art LCD methods demonstrate the superiority of MILD in both efficiency and accuracy.
Lowest Unique Bid Auctions with Resubmission Opportunities
Venue: arXiv cs.GT 2017
Year: 2017

The recent online platforms propose multiple items for bidding. The state of the art, however, is limited to the analysis of one item auction without resubmission. In this paper we study multi-item lowest unique bid auctions (LUBA) with resubmission in discrete bid spaces under budget constraints. We show that the game does not have pure Bayes-Nash equilibria (except in very special cases). However, at least one mixed Bayes-Nash equilibria exists for arbitrary number of bidders and items. The equilibrium is explicitly computed for two-bidder setup with resubmission possibilities. In the general setting we propose a distributed strategic learning algorithm to approximate equilibria. Computer simulations indicate that the error quickly decays in few number of steps. When the number of bidders per item follows a Poisson distribution, it is shown that the seller can get a non-negligible revenue on several items, and hence making a partial revelation of the true value of the items. Finally, the attitude of the bidders towards the risk is considered. In contrast to risk-neutral agents who bids very small values, the cumulative distribution and the bidding support of risk-sensitive agents are more distributed.
Unsupervised Triplet Hashing for Fast Image Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

Hashing has played a pivotal role in large-scale image retrieval. With the development of Convolutional Neural Network (CNN), hashing learning has shown great promise. But existing methods are mostly tuned for classification, which are not optimized for retrieval tasks, especially for instance-level retrieval. In this study, we propose a novel hashing method for large-scale image retrieval. Considering the difficulty in obtaining labeled datasets for image retrieval task in large scale, we propose a novel CNN-based unsupervised hashing method, namely Unsupervised Triplet Hashing (UTH). The unsupervised hashing network is designed under the following three principles: 1) more discriminative representations for image retrieval; 2) minimum quantization loss between the original real-valued feature descriptors and the learned hash codes; 3) maximum information entropy for the learned hash codes. Extensive experiments on CIFAR-10, MNIST and In-shop datasets have shown that UTH outperforms several state-of-the-art unsupervised hashing methods in terms of retrieval accuracy.
Proportional Representation in Vote Streams
Venue: arXiv cs.GT 2017
Year: 2017

We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respect to common multiwinner proportional representation voting rules; specifically, we consider the Approval-based and the Borda-based variants of both the Chamberlin-- ourant rule and the Monroe rule. We complement our algorithms with lower bounds. Somewhat surprisingly, our results imply that, using space which does not depend on the number of voters it is possible to efficiently identify an approximate representative committee of fixed size over vote streams with huge number of voters.
Predicting Slice-to-Volume Transformation in Presence of Arbitrary Subject Motion
Venue: arXiv cs.CV 2017
Year: 2017

This paper aims to solve a fundamental problem in intensity-based 2D/3D registration, which concerns the limited capture range and need for very good initialization of state-of-the-art image registration methods. We propose a regression approach that learns to predict rotation and translations of arbitrary 2D image slices from 3D volumes, with respect to a learned canonical atlas co-ordinate system. To this end, we utilize Convolutional Neural Networks (CNNs) to learn the highly complex regression function that maps 2D image slices into their correct position and orientation in 3D space. Our approach is attractive in challenging imaging scenarios, where significant subject motion complicates reconstruction performance of 3D volumes from 2D slice data. We extensively evaluate the effectiveness of our approach quantitatively on simulated MRI brain data with extreme random motion. We further demonstrate qualitative results on fetal MRI where our method is integrated into a full reconstruction and motion compensation pipeline. With our CNN regression approach we obtain an average prediction error of 7mm on simulated data, and convincing reconstruction quality of images of very young fetuses where previous methods fail. We further discuss applications to Computed Tomography and X-ray projections. Our approach is a general solution to the 2D/3D initialization problem. It is computationally efficient, with prediction times per slice of a few milliseconds, making it suitable for real-time scenarios.
Tree tribes and lower bounds for switching lemmas
Venue: arXiv cs.CC 2017
Year: 2017

We show tight upper and lower bounds for switching lemmas obtained by the action of random $p$-restrictions on boolean functions that can be expressed as decision trees in which every vertex is at a distance of at most $t$ from some leaf, also called $t$-clipped decision trees. More specifically, we show the following: $\bullet$ If a boolean function $f$ can be expressed as a $t$-clipped decision tree, then under the action of a random $p$-restriction $ρ$, the probability that the smallest depth decision tree for $f|_ρ$ has depth greater than $d$ is upper bounded by $(4p2^{t})^{d}$. $\bullet$ For every $t$, there exists a function $g_{t}$ that can be expressed as a $t$-clipped decision tree, such that under the action of a random $p$-restriction $ρ$, the probability that the smallest depth decision tree for $g_{t}|_ρ$ has depth greater than $d$ is lower bounded by $(c_{0}p2^{t})^{d}$, for $0\leq p\leq c_{p}2^{-t}$ and $0\leq d\leq c_{d}\frac{\log n}{2^{t}\log t}$, where $c_{0},c_{p},c_{d}$ are universal constants.
Aggregated knowledge from a small number of debates outperforms the wisdom of large crowds
Venue: arXiv cs.SI 2017
Year: 2017

The aggregation of many independent estimates can outperform the most accurate individual judgment. This centenarian finding, popularly known as the wisdom of crowds, has been applied to problems ranging from the diagnosis of cancer to financial forecasting. It is widely believed that social influence undermines collective wisdom by reducing the diversity of opinions within the crowd. Here, we show that if a large crowd is structured in small independent groups, deliberation and social influence within groups improve the crowd's collective accuracy. We asked a live crowd (N=5180) to respond to general-knowledge questions (e.g., what is the height of the Eiffel Tower?). Participants first answered individually, then deliberated and made consensus decisions in groups of five, and finally provided revised individual estimates. We found that averaging consensus decisions was substantially more accurate than aggregating the initial independent opinions. Remarkably, combining as few as four consensus choices outperformed the wisdom of thousands of individuals.
SceneSeer: 3D Scene Design with Natural Language
Venue: arXiv cs.GR 2017
Year: 2017

Designing 3D scenes is currently a creative task that requires significant expertise and effort in using complex 3D design interfaces. This effortful design process starts in stark contrast to the easiness with which people can use language to describe real and imaginary environments. We present SceneSeer: an interactive text to 3D scene generation system that allows a user to design 3D scenes using natural language. A user provides input text from which we extract explicit constraints on the objects that should appear in the scene. Given these explicit constraints, the system then uses a spatial knowledge base learned from an existing database of 3D scenes and 3D object models to infer an arrangement of the objects forming a natural scene matching the input description. Using textual commands the user can then iteratively refine the created scene by adding, removing, replacing, and manipulating objects. We evaluate the quality of 3D scenes generated by SceneSeer in a perceptual evaluation experiment where we compare against manually designed scenes and simpler baselines for 3D scene generation. We demonstrate how the generated scenes can be iteratively refined through simple natural language commands.
On the Power of Learning from $k$-Wise Queries
Venue: arXiv cs.LG 2017
Year: 2017

Several well-studied models of access to data samples, including statistical queries, local differential privacy and low-communication algorithms rely on queries that provide information about a function of a single sample. (For example, a statistical query (SQ) gives an estimate of $Ex_{x \sim D}[q(x)]$ for any choice of the query function $q$ mapping $X$ to the reals, where $D$ is an unknown data distribution over $X$.) Yet some data analysis algorithms rely on properties of functions that depend on multiple samples. Such algorithms would be naturally implemented using $k$-wise queries each of which is specified by a function $q$ mapping $X^k$ to the reals. Hence it is natural to ask whether algorithms using $k$-wise queries can solve learning problems more efficiently and by how much. Blum, Kalai and Wasserman (2003) showed that for any weak PAC learning problem over a fixed distribution, the complexity of learning with $k$-wise SQs is smaller than the (unary) SQ complexity by a factor of at most $2^k$. We show that for more general problems over distributions the picture is substantially richer. For every $k$, the complexity of distribution-independent PAC learning with $k$-wise queries can be exponentially larger than learning with $(k+1)$-wise queries. We then give two approaches for simulating a $k$-wise query using unary queries. The first approach exploits the structure of the problem that needs to be solved. It generalizes and strengthens (exponentially) the results of Blum et al.. It allows us to derive strong lower bounds for learning DNF formulas and stochastic constraint satisfaction problems that hold against algorithms using $k$-wise queries. The second approach exploits the $k$-party communication complexity of the $k$-wise query function.
Distributed Frequency Control with Operational Constraints, Part II: Network Power Balance
Venue: arXiv cs.SY 2017
Year: 2017

In Part I of this paper we propose a decentralized optimal frequency control of multi-area power system with operational constraints, where the tie-line powers remain unchanged in the steady state and the power mismatch is balanced within individual control areas. In Part II of the paper, we propose a distributed controller for optimal frequency control in the network power balance case, where the power mismatch is balanced over the whole system. With the proposed controller, the tie-line powers remain within the acceptable range at equilibrium, while the regulation capacity constraints are satisfied both at equilibrium and during transient. It is revealed that the closed-loop system with the proposed controller carries out primal-dual updates with saturation for solving an associated optimization problem. To cope with discontinuous dynamics of the closed-loop system, we deploy the invariance principle for nonpathological Lyapunov function to prove its asymptotic stability. Simulation results are provided to show the effectiveness of our controller.
How long delays impact TCP performance for a connectivity from Reunion Island ?
Venue: arXiv cs.NI 2017
Year: 2017

TCP is the protocol of transport the most used in the Internet and have a heavy-dependence on delay. Reunion Island have a specific Internet connection, based on main links to France, located 10.000 km away. As a result, the minimal delay between Reunion Island and France is around 180 ms. In this paper, we will study TCP traces collected in Reunion Island University. The goal is to determine the metrics to study the impacts of long delays on TCP performance.
Improving Object Detection with Region Similarity Learning
Venue: arXiv cs.CV 2017
Year: 2017

Object detection aims to identify instances of semantic objects of a certain class in images or videos. The success of state-of-the-art approaches is attributed to the significant progress of object proposal and convolutional neural networks (CNNs). Most promising detectors involve multi-task learning with an optimization objective of softmax loss and regression loss. The first is for multi-class categorization, while the latter is for improving localization accuracy. However, few of them attempt to further investigate the hardness of distinguishing different sorts of distracting background regions (i.e., negatives) from true object regions (i.e., positives). To improve the performance of classifying positive object regions vs. a variety of negative background regions, we propose to incorporate triplet embedding into learning objective. The triplet units are formed by assigning each negative region to a meaningful object class and establishing class- specific negatives, followed by triplets construction. Over the benchmark PASCAL VOC 2007, the proposed triplet em- bedding has improved the performance of well-known FastRCNN model with a mAP gain of 2.1%. In particular, the state-of-the-art approach OHEM can benefit from the triplet embedding and has achieved a mAP improvement of 1.2%.
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
Venue: arXiv cs.CC 2017
Year: 2017

We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to "width" complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called "reordering"), which allows to build Boolean function $g$ from Boolean Function $f$, such that if for $f$ we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function $g$, but for any order. Using it we construct the total function $REQ$ which deterministic OBDD complexity is $2^{Ω(n/\log n)}$ and present quantum OBDD of width $O(n^2)$. It is bigger gap for explicit function that was known before for OBDD of width more than linear. Using this result we prove the width hierarchy for complexity classes of Boolean functions for quantum OBDDs. Additionally, we prove the width hierarchy for complexity classes of Boolean functions for bounded error probabilistic OBDDs. And using "reordering" method we extend a hierarchy for $k$-OBDD of polynomial size, for $k=o(n/\log^3n)$. Moreover, we proved a similar hierarchy for bounded error probabilistic $k$-OBDD. And for deterministic and probabilistic $k$-OBDDs of superpolynomial and subexponential size.