OpenRaiser/Intern-Atlas huggingface dataset:
Cost-Effective Millimeter Wave Communications with Lens Antenna Array
Venue: arXiv cs.IT 2016
Year: 2016

Millimeter wave (mmWave) communication is a promising technology for the fifth-generation (5G) wireless system. However, the large number of antennas used and the wide signal bandwidth in mmWave systems render the conventional multi-antenna techniques increasingly costly in terms of signal processing complexity, hardware implementation, and power consumption. In this article, we investigate cost-effective mmWave communications by first providing an overview of the main existing techniques that offer different trade-offs between performance and cost, and then focusing our discussion on a promising new technique based on the advanced lens antenna array. It is revealed that by exploiting the angle-dependent energy focusing property of lens arrays, together with the angular sparsity of the mmWave channels, mmWave lens-antenna system is able to achieve the capacity-optimal performance with very few radio-frequency (RF) chains and using the low-complexity single-carrier transmission, even for wide-band frequency-selective channels. Numerical results show that the lens-based system significantly outperforms the state-of-the-art designs for mmWave systems in both spectrum efficiency and energy efficiency.
A Hybrid Model for Estimating Software Project Effort from Use Case Points
Venue: arXiv cs.SE 2016
Year: 2016

Early software effort estimation is a hallmark of successful software project management. Building a reliable effort estimation model usually requires historical data. Unfortunately, since the information available at early stages of software development is scarce, it is recommended to use software size metrics as key cost factor of effort estimation. Use Case Points (UCP) is a prominent size measure designed mainly for object-oriented projects. Nevertheless, there are no established models that can translate UCP into its corresponding effort, therefore, most models use productivity as a second cost driver. The productivity in those models is usually guessed by experts and does not depend on historical data, which makes it subject to uncertainty. Thus, these models were not well examined using a large number of historical data. In this paper, we designed a hybrid model that consists of classification and prediction stages using a support vector machine and radial basis neural networks. The proposed model was constructed over a large number of observations collected from industrial and student projects. The proposed model was compared against previous UCP prediction models. The validation and empirical results demonstrated that the proposed model significantly surpasses these models on all datasets. The main conclusion is that the environmental factors of UCP can be used to classify and estimate productivity.
Crafting GBD-Net for Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

The visual cues from multiple support regions of different sizes and resolutions are complementary in classifying a candidate box in object detection. Effective integration of local and contextual visual cues from these regions has become a fundamental problem in object detection. In this paper, we propose a gated bi-directional CNN (GBD-Net) to pass messages among features from different support regions during both feature learning and feature extraction. Such message passing can be implemented through convolution between neighboring support regions in two directions and can be conducted in various layers. Therefore, local and contextual visual patterns can validate the existence of each other by learning their nonlinear relationships and their close interactions are modeled in a more complex way. It is also shown that message passing is not always helpful but dependent on individual samples. Gated functions are therefore needed to control message transmission, whose on-or-offs are controlled by extra visual evidence from the input sample. The effectiveness of GBD-Net is shown through experiments on three object detection datasets, ImageNet, Pascal VOC2007 and Microsoft COCO. This paper also shows the details of our approach in wining the ImageNet object detection challenge of 2016, with source code provided on \url{https://github.com/craftGBD/craftGBD}.
On the Mints Hierarchy in First-Order Intuitionistic Logic
Venue: arXiv cs.LO 2016
Year: 2016

We stratify intuitionistic first-order logic over $(\forall,\to)$ into fragments determined by the alternation of positive and negative occurrences of quantifiers (Mints hierarchy). We study the decidability and complexity of these fragments. We prove that even the $Δ_2$ level is undecidable and that $Σ_1$ is Expspace-complete. We also prove that the arity-bounded fragment of $Σ_1$ is complete for co-Nexptime.
Image Segmentation Based on the Self-Balancing Mechanism in Virtual 3D Elastic Mesh
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a novel model of 3D elastic mesh is presented for image segmentation. The model is inspired by stress and strain in physical elastic objects, while the repulsive force and elastic force in the model are defined slightly different from the physical force to suit the segmentation problem well. The self-balancing mechanism in the model guarantees the stability of the method in segmentation. The shape of the elastic mesh at balance state is used for region segmentation, in which the sign distribution of the points'z coordinate values is taken as the basis for segmentation. The effectiveness of the proposed method is proved by analysis and experimental results for both test images and real world images.
Matching of Images with Rotation Transformation Based on the Virtual Electromagnetic Interaction
Venue: arXiv cs.CV 2016
Year: 2016

A novel approach of image matching for rotating transformation is presented and studied. The approach is inspired by electromagnetic interaction force between physical currents. The virtual current in images is proposed based on the significant edge lines extracted as the fundamental structural feature of images. The virtual electromagnetic force and the corresponding moment is studied between two images after the extraction of the virtual currents in the images. Then image matching for rotating transformation is implemented by exploiting the interaction between the virtual currents in the two images to be matched. The experimental results prove the effectiveness of the novel idea, which indicates the promising application of the proposed method in image registration.
Vehicle-to-Vehicle Communications with Urban Intersection Path Loss Models
Venue: arXiv cs.IT 2016
Year: 2016

Vehicle-to-vehicle (V2V) communication can improve road safety and traffic efficiency, particularly around critical areas such as intersections. We analytically derive V2V success probability near an urban intersection, based on empirically supported line-of-sight (LOS), weak-line-of-sight (WLOS), and non-line-of-sight (NLOS) channel models. The analysis can serve as a preliminary design tool for performance assessment over different system parameters and target performance requirements.
LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs
Venue: arXiv cs.CG 2016
Year: 2016

In this paper we study a family of algorithms, introduced by Chan [SODA 1999] and called LR-algorithms, for drawing ordered rooted binary trees. In particular, we are interested in constructing LR-drawings (that are drawings obtained via LR-algorithms) with small width. Chan showed three different LR-algorithms that achieve, for an ordered rooted binary tree with $n$ nodes, width $O(n^{0.695})$, width $O(n^{0.5})$, and width $O(n^{0.48})$. We prove that, for every $n$-node ordered rooted binary tree, an LR-drawing with minimum width can be constructed in $O(n^{1.48})$ time. Further, we show an infinite family of $n$-node ordered rooted binary trees requiring $Ω(n^{0.418})$ width in any LR-drawing; no lower bound better than $Ω(\log n)$ was previously known. Finally, we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to $451$ nodes. Our interest in LR-drawings is mainly motivated by a result of Di Battista and Frati [Algorithmica 2009], who proved that $n$-vertex outerplanar graphs have outerplanar straight-line drawings in $O(n^{1.48})$ area by means of a drawing algorithm which resembles an LR-algorithm. We deepen the connection between LR-drawings and outerplanar straight-line drawings by proving that, if $n$-node ordered rooted binary trees have LR-drawings with $f(n)$ width, for any function $f(n)$, then $n$-vertex outerplanar graphs have outerplanar straight-line drawings in $O(f(n))$ area. Finally, we exploit a structural decomposition for ordered rooted binary trees introduced by Chan in order to prove that every $n$-vertex outerplanar graph has an outerplanar straight-line drawing in $O(n\cdot 2^{\sqrt{2 \log_2 n}} \sqrt{\log n})$ area.
Situational Awareness by Risk-Conscious Skills
Venue: arXiv cs.AI 2016
Year: 2016

Hierarchical Reinforcement Learning has been previously shown to speed up the convergence rate of RL planning algorithms as well as mitigate feature-based model misspecification (Mankowitz et. al. 2016a,b, Bacon 2015). To do so, it utilizes hierarchical abstractions, also known as skills -- a type of temporally extended action (Sutton et. al. 1999) to plan at a higher level, abstracting away from the lower-level details. We incorporate risk sensitivity, also referred to as Situational Awareness (SA), into hierarchical RL for the first time by defining and learning risk aware skills in a Probabilistic Goal Semi-Markov Decision Process (PG-SMDP). This is achieved using our novel Situational Awareness by Risk-Conscious Skills (SARiCoS) algorithm which comes with a theoretical convergence guarantee. We show in a RoboCup soccer domain that the learned risk aware skills exhibit complex human behaviors such as `time-wasting' in a soccer game. In addition, the learned risk aware skills are able to mitigate reward-based model misspecification.
Impatient DNNs - Deep Neural Networks with Dynamic Time Budgets
Venue: arXiv cs.CV 2016
Year: 2016

We propose Impatient Deep Neural Networks (DNNs) which deal with dynamic time budgets during application. They allow for individual budgets given a priori for each test example and for anytime prediction, i.e., a possible interruption at multiple stages during inference while still providing output estimates. Our approach can therefore tackle the computational costs and energy demands of DNNs in an adaptive manner, a property essential for real-time applications. Our Impatient DNNs are based on a new general framework of learning dynamic budget predictors using risk minimization, which can be applied to current DNN architectures by adding early prediction and additional loss layers. A key aspect of our method is that all of the intermediate predictors are learned jointly. In experiments, we evaluate our approach for different budget distributions, architectures, and datasets. Our results show a significant gain in expected accuracy compared to common baselines.
Accounting for Availability Biases in Information Visualization
Venue: arXiv cs.HC 2016
Year: 2016

The availability heuristic is a strategy that people use to make quick decisions but often lead to systematic errors. We propose three ways that visualization could facilitate unbiased decision-making. First, visualizations can alter the way our memory stores the events for later recall, so as to improve users' long-term intuitions. Second, the known biases could lead to new visualization guidelines. Third, we suggest the design of decision-making tools that are inspired by heuristics, e.g. suggesting intuitive approximations, rather than target to present exhaustive comparisons of all possible outcomes, or automated solutions for choosing decisions.
ABA+: Assumption-Based Argumentation with Preferences
Venue: arXiv cs.AI 2016
Year: 2016

We present ABA+, a new approach to handling preferences in a well known structured argumentation formalism, Assumption-Based Argumentation (ABA). In ABA+, preference information given over assumptions is incorporated directly into the attack relation, thus resulting in attack reversal. ABA+ conservatively extends ABA and exhibits various desirable features regarding relationship among argumentation semantics as well as preference handling. We also introduce Weak Contraposition, a principle concerning reasoning with rules and preferences that relaxes the standard principle of contraposition, while guaranteeing additional desirable features for ABA+.
Optimal Beamforming for MIMO Shared Relaying in Downlink Cellular Networks with ARQ
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the performance of the downlink of a cellular network with automatic repeat-request (ARQ) and a half duplex decode-and-forward shared relay. In this system, two multiple-input-multiple-output (MIMO) base stations serve two single antenna users. A MIMO shared relay retransmits the lost packets to the target users. First, we study the system with direct retransmission from the base station and derive a closed form expression for the outage probability of the system.We show that the direct retransmission can overcome the fading, however, it cannot overcome the interference. After that, we invoke the shared relay and design the relay beamforming matrices such that the signal-to-interference-and-noise ratio (SINR) is improved at the users subject to power constraints on the relay. In the case when the transmission of only one user fails, we derive a closed form solution for the relay beamformers. On the other hand when both transmissions fail, we pose the beamforming problem as a sequence of non-convex feasibility problems. We use semidefinite relaxation (SDR) to convert each feasibility problem into a convex optimization problem. We ensure a rank one solution, and hence, there is no loss of optimality in SDR. Simulation results are presented showing the superior performance of the proposed relay beamforming strategy compared to direct ARQ system in terms of the outage probability.
A Flat and Scalable Data Center Network Topology Based on De Bruijn Graphs
Venue: arXiv cs.NI 2016
Year: 2016

Due to the requirement of hosting tens of thousands of hosts in today's data centers, data center networks strive for scalability and high throughput on the one hand. On the other hand, the cost for networking hardware should be minimized. Consequently, the number and complexity (e.g. TCAM size) of switches has to be minimized. These requirements led to network topologies like Clos and Leaf-Spine networks only requiring a shallow hierarchy of switches---two levels for Leaf-Spine networks. The drawback of these topologies is that switches at higher levels like Spine switches need a high port density and, thus, are expensive and limit the scalability of the network. In this paper, we propose a data center network topology based on De Bruijn graphs completely avoiding a switch hierarchy and implementing a flat network topology of top-of-rack switches instead. This topology guarantees logarithmic (short) path length. We show that the required routing logic can be implemented by standard prefix matching operations in hardware (TCAM) allowing for using commodity switches without any modification. Moreover, forwarding requires only a very small number of forwarding table entries, saving costly and energy-intensive TCAM.
Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
Venue: arXiv cs.AI 2016
Year: 2016

Autonomous driving is a multi-agent setting where the host vehicle must apply sophisticated negotiation skills with other road users when overtaking, giving way, merging, taking left and right turns and while pushing ahead in unstructured urban roadways. Since there are many possible scenarios, manually tackling all possible cases will likely yield a too simplistic policy. Moreover, one must balance between unexpected behavior of other drivers/pedestrians and at the same time not to be too defensive so that normal traffic flow is maintained. In this paper we apply deep reinforcement learning to the problem of forming long term driving strategies. We note that there are two major challenges that make autonomous driving different from other robotic tasks. First, is the necessity for ensuring functional safety - something that machine learning has difficulty with given that performance is optimized at the level of an expectation over many instances. Second, the Markov Decision Process model often used in robotics is problematic in our case because of unpredictable behavior of other agents in this multi-agent scenario. We make three contributions in our work. First, we show how policy gradient iterations can be used without Markovian assumptions. Second, we decompose the problem into a composition of a Policy for Desires (which is to be learned) and trajectory planning with hard constraints (which is not learned). The goal of Desires is to enable comfort of driving, while hard constraints guarantees the safety of driving. Third, we introduce a hierarchical temporal abstraction we call an "Option Graph" with a gating mechanism that significantly reduces the effective horizon and thereby reducing the variance of the gradient estimation even further.
Model Based In Situ Calibration of Six Axis Force Torque Sensors
Venue: arXiv cs.RO 2016
Year: 2016

This paper proposes and validates an in situ calibration method to calibrate six axis force torque (F/T) sensors once they are mounted on the system. This procedure takes advantage of the knowledge of the model of the robot to generate the expected wrenches of the sensors during some arbitrary motions. It then uses this information to train and validate new calibration matrices, taking into account the calibration matrix obtained with a classical Workbench calibration. The proposed calibration algorithm is validated on the F/T sensors mounted on the iCub humanoid robot legs.
A Greedy Approach for Budgeted Maximum Inner Product Search
Venue: arXiv cs.DS 2016
Year: 2016

Maximum Inner Product Search (MIPS) is an important task in many machine learning applications such as the prediction phase of a low-rank matrix factorization model for a recommender system. There have been some works on how to perform MIPS in sub-linear time recently. However, most of them do not have the flexibility to control the trade-off between search efficient and search quality. In this paper, we study the MIPS problem with a computational budget. By carefully studying the problem structure of MIPS, we develop a novel Greedy-MIPS algorithm, which can handle budgeted MIPS by design. While simple and intuitive, Greedy-MIPS yields surprisingly superior performance compared to state-of-the-art approaches. As a specific example, on a candidate set containing half a million vectors of dimension 200, Greedy-MIPS runs 200x faster than the naive approach while yielding search results with the top-5 precision greater than 75\%.
Secrecy in MIMO Networks with No Eavesdropper CSIT
Venue: arXiv cs.IT 2016
Year: 2016

We consider two fundamental multi-user channel models: the multiple-input multiple-output (MIMO) wiretap channel with one helper (WTH) and the MIMO multiple access wiretap channel (MAC-WT). In each case, the eavesdropper has $K$ antennas while the remaining terminals have $N$ antennas each. We consider a fast fading channel where the channel state information (CSI) of the legitimate receiver is available at the transmitters but no channel state information at the transmitters (CSIT) is available for the eavesdropper's channel. We determine the optimal sum secure degrees of freedom (s.d.o.f.) for each channel model for the regime $K\leq N$, and show that in this regime, the MAC-WT channel reduces to the WTH in the absence of eavesdropper CSIT. For the regime $N\leq K\leq 2N$, we obtain the optimal linear s.d.o.f., and show that the MAC-WT channel and the WTH have the same optimal s.d.o.f. when restricted to linear encoding strategies. In the absence of any such restrictions, we provide an upper bound for the sum s.d.o.f. of the MAC-WT chanel in the regime $N\leq K\leq 2N$. Our results show that unlike in the single-input single-output (SISO) case, there is loss of s.d.o.f. for even the WTH due to lack of eavesdropper CSIT when $K\geq N$.
Transfer from Simulation to Real World through Learning Deep Inverse Dynamics Model
Venue: arXiv cs.RO 2016
Year: 2016

Developing control policies in simulation is often more practical and safer than directly running experiments in the real world. This applies to policies obtained from planning and optimization, and even more so to policies obtained from reinforcement learning, which is often very data demanding. However, a policy that succeeds in simulation often doesn't work when deployed on a real robot. Nevertheless, often the overall gist of what the policy does in simulation remains valid in the real world. In this paper we investigate such settings, where the sequence of states traversed in simulation remains reasonable for the real world, even if the details of the controls are not, as could be the case when the key differences lie in detailed friction, contact, mass and geometry properties. During execution, at each time step our approach computes what the simulation-based control policy would do, but then, rather than executing these controls on the real robot, our approach computes what the simulation expects the resulting next state(s) will be, and then relies on a learned deep inverse dynamics model to decide which real-world action is most suitable to achieve those next states. Deep models are only as good as their training data, and we also propose an approach for data collection to (incrementally) learn the deep inverse dynamics model. Our experiments shows our approach compares favorably with various baselines that have been developed for dealing with simulation to real world model discrepancy, including output error control and Gaussian dynamics adaptation.
Monitoring the Top-m Aggregation in a Sliding Window of Spatial Queries
Venue: arXiv cs.DB 2016
Year: 2016

In this paper, we propose and study the problem of top-m rank aggregation of spatial objects in streaming queries, where, given a set of objects O, a stream of spatial queries (kNN or range), the goal is to report m objects with the highest aggregate rank. The rank of an object w.r.t. an individual query is computed based on its distance from the query location, and the aggregate rank is computed from all of the individual rank orderings. Solutions to this fundamental problem can be used to monitor the popularity of spatial objects, which in turn can provide new analytical tools for spatial data. Our work draws inspiration from three different domains: rank aggregation, continuous queries and spatial databases. To the best of our knowledge, there is no prior work that considers all three problem domains in a single context. Our problem is different from the classical rank aggregation problem in the way that the rank of spatial objects are dependent on streaming queries whose locations are not known a priori, and is different from the problem of continuous spatial queries because new query locations can arrive in any region, but do not move. In order to solve this problem, we show how to upper and lower bound the rank of an object for any unseen query. Then we propose an approximation solution to continuously monitor the top-m objects efficiently, for which we design an Inverted Rank File (IRF) index to guarantee the error bound of the solution. In particular, we propose the notion of safe ranking to determine whether the current result is still valid or not when new queries arrive, and propose the notion of validation objects to limit the number of objects to update in the top-m results. We also propose an exact solution for applications where an approximate solution is not sufficient. Last, we conduct extensive experiments to verify the efficiency and effectiveness of our solutions.