OpenRaiser/Intern-Atlas huggingface dataset:
Contextual Search via Intrinsic Volumes
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector $v \in [0,1]^d$. Every round the learner is provided an adversarially-chosen context $u_t \in \mathbb{R}^d$, submits a guess $p_t$ for the value of $\langle u_t, v\rangle$, learns whether $p_t < \langle u_t, v\rangle$, and incurs loss $\ell(\langle u_t, v\rangle, p_t)$ (for some loss function $\ell$). The learner's goal is to minimize their total loss over the course of $T$ rounds. We present an algorithm for the contextual search problem for the symmetric loss function $\ell(θ, p) = |θ- p|$ that achieves $O_{d}(1)$ total loss. We present a new algorithm for the dynamic pricing problem (which can be realized as a special case of the contextual search problem) that achieves $O_{d}(\log \log T)$ total loss, improving on the previous best known upper bounds of $O_{d}(\log T)$ and matching the known lower bounds (up to a polynomial dependence on $d$). Both algorithms make significant use of ideas from the field of integral geometry, most notably the notion of intrinsic volumes of a convex set. To the best of our knowledge this is the first application of intrinsic volumes to algorithm design.
Exploiting Partial Structural Symmetry For Patient-Specific Image Augmentation in Trauma Interventions
Venue: arXiv cs.CV 2018
Year: 2018

In unilateral pelvic fracture reductions, surgeons attempt to reconstruct the bone fragments such that bilateral symmetry in the bony anatomy is restored. We propose to exploit this "structurally symmetric" nature of the pelvic bone, and provide intra-operative image augmentation to assist the surgeon in repairing dislocated fragments. The main challenge is to automatically estimate the desired plane of symmetry within the patient's pre-operative CT. We propose to estimate this plane using a non-linear optimization strategy, by minimizing Tukey's biweight robust estimator, relying on the partial symmetry of the anatomy. Moreover, a regularization term is designed to enforce the similarity of bone density histograms on both sides of this plane, relying on the biological fact that, even if injured, the dislocated bone segments remain within the body. The experimental results demonstrate the performance of the proposed method in estimating this "plane of partial symmetry" using CT images of both healthy and injured anatomy. Examples of unilateral pelvic fractures are used to show how intra-operative X-ray images could be augmented with the forward-projections of the mirrored anatomy, acting as objective road-map for fracture reduction procedures.
Prompt Scheduling for Selfish Agents
Venue: arXiv cs.DS 2018
Year: 2018

We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options.
Efficient Graph-based Word Sense Induction by Distributional Inclusion Vector Embeddings
Venue: arXiv cs.CL 2018
Year: 2018

Word sense induction (WSI), which addresses polysemy by unsupervised discovery of multiple word senses, resolves ambiguities for downstream NLP tasks and also makes word representations more interpretable. This paper proposes an accurate and efficient graph-based method for WSI that builds a global non-negative vector embedding basis (which are interpretable like topics) and clusters the basis indexes in the ego network of each polysemous word. By adopting distributional inclusion vector embeddings as our basis formation model, we avoid the expensive step of nearest neighbor search that plagues other graph-based methods without sacrificing the quality of sense clusters. Experiments on three datasets show that our proposed method produces similar or better sense clusters and embeddings compared with previous state-of-the-art methods while being significantly more efficient.
Juniper: A Tree+Table Approach to Multivariate Graph Visualization
Venue: arXiv cs.HC 2018
Year: 2018

Analyzing large, multivariate graphs is an important problem in many domains, yet such graphs are challenging to visualize. In this paper, we introduce a novel, scalable, tree+table multivariate graph visualization technique, which makes many tasks related to multivariate graph analysis easier to achieve. The core principle we follow is to selectively query for nodes or subgraphs of interest and visualize these subgraphs as a spanning tree of the graph. The tree is laid out linearly, which enables us to juxtapose the nodes with a table visualization where diverse attributes can be shown. We also use this table as an adjacency matrix, so that the resulting technique is a hybrid node-link/adjacency matrix technique. We implement this concept in Juniper and complement it with a set of interaction techniques that enable analysts to dynamically grow, restructure, and aggregate the tree, as well as change the layout or show paths between nodes. We demonstrate the utility of our tool in usage scenarios for different multivariate networks: a bipartite network of scholars, papers, and citation metrics and a multitype network of story characters, places, books, etc.
Adversarial Training Versus Weight Decay
Venue: arXiv cs.LG 2018
Year: 2018

Performance-critical machine learning models should be robust to input perturbations not seen during training. Adversarial training is a method for improving a model's robustness to some perturbations by including them in the training process, but this tends to exacerbate other vulnerabilities of the model. The adversarial training framework has the effect of translating the data with respect to the cost function, while weight decay has a scaling effect. Although weight decay could be considered a crude regularization technique, it appears superior to adversarial training as it remains stable over a broader range of regimes and reduces all generalization errors. Equipped with these abstractions, we provide key baseline results and methodology for characterizing robustness. The two approaches can be combined to yield one small model that demonstrates good robustness to several white-box attacks associated with different metrics.
Mean Field Network based Graph Refinement with application to Airway Tree Extraction
Venue: arXiv cs.CV 2018
Year: 2018

We present tree extraction in 3D images as a graph refinement task, of obtaining a subgraph from an over-complete input graph. To this end, we formulate an approximate Bayesian inference framework on undirected graphs using mean field approximation (MFA). Mean field networks are used for inference based on the interpretation that iterations of MFA can be seen as feed-forward operations in a neural network. This allows us to learn the model parameters from training data using back-propagation algorithm. We demonstrate usefulness of the model to extract airway trees from 3D chest CT data. We first obtain probability images using a voxel classifier that distinguishes airways from background and use Bayesian smoothing to model individual airway branches. This yields us joint Gaussian density estimates of position, orientation and scale as node features of the input graph. Performance of the method is compared with two methods: the first uses probability images from a trained voxel classifier with region growing, which is similar to one of the best performing methods at EXACT'09 airway challenge, and the second method is based on Bayesian smoothing on these probability images. Using centerline distance as error measure the presented method shows significant improvement compared to these two methods.
Realtime Active Sound Source Localization for Unmanned Ground Robots Using a Self-Rotational Bi-Microphone Array
Venue: arXiv cs.SD 2018
Year: 2018

This work presents a novel technique that performs both orientation and distance localization of a sound source in a three-dimensional (3D) space using only the interaural time difference (ITD) cue, generated by a newly-developed self-rotational bi-microphone robotic platform. The system dynamics is established in the spherical coordinate frame using a state-space model. The observability analysis of the state-space model shows that the system is unobservable when the sound source is placed with elevation angles of $90$ and $0$ degree. The proposed method utilizes the difference between the azimuth estimates resulting from respectively the 3D and the two-dimensional models to check the zero-degree-elevation condition and further estimates the elevation angle using a polynomial curve fitting approach. Also, the proposed method is capable of detecting a $90$-degree elevation by extracting the zero-ITD signal 'buried' in noise. Additionally, a distance localization is performed by first rotating the microphone array to face toward the sound source and then shifting the microphone perpendicular to the source-robot vector by a predefined distance of a fixed number of steps. The integrated rotational and translational motions of the microphone array provide a complete orientation and distance localization using only the ITD cue. A novel robotic platform using a self-rotational bi-microphone array was also developed for unmanned ground robots performing sound source localization. The proposed technique was first tested in simulation and was then verified on the newly-developed robotic platform. Experimental data collected by the microphones installed on a KEMAR dummy head were also used to test the proposed technique. All results show the effectiveness of the proposed technique.
What's (Not) Validating Network Paths: A Survey
Venue: arXiv cs.NI 2018
Year: 2018

Validating network paths taken by packets is critical for a secure Internet architecture. Any feasible solution must both enforce packet forwarding along endhost-specified paths and verify whether packets have taken those paths. However, neither enforcement nor verification is supported by the current Internet. Due likely to a long-standing confusion between routing and forwarding, only limited solutions for path validation exist in the literature. This survey article aims to reinvigorate research in to the significant and essential topic of path validation. It crystallizes not only how path validation works but also where seemingly qualified solutions fall short. The analyses explore future research directions in path validation toward improving security, privacy, and efficiency.
The Sum-Rate-Distortion Region of Correlated Gauss-Markov Sources
Venue: arXiv cs.IT 2018
Year: 2018

Efficient low-delay video encoders are of fundamental importance to provide timely feedback in remotely controlled platforms such as drones. In order to fully understand the theoretical limits of low-delay video encoders, we consider an ideal differential predictive coded modulation (DPCM) encoder and provide the explicit derivation of the sum-rate-distortion region for a generic number of successive correlated Gauss-Markov sources along the line of the work by Ma and Ishwar. Furthermore, we provide an upper bound on the minimum distortion achievable in case an arbitrary number of sources are not available at the decoder.
Who framed Roger Reindeer? De-censorship of Facebook posts by snippet classification
Venue: arXiv cs.CL 2018
Year: 2018

This paper considers online news censorship and it concentrates on censorship of identities. Obfuscating identities may occur for disparate reasons, from military to judiciary ones. In the majority of cases, this happens to protect individuals from being identified and persecuted by hostile people. However, being the collaborative web characterised by a redundancy of information, it is not unusual that the same fact is reported by multiple sources, which may not apply the same restriction policies in terms of censorship. Also, the proven aptitude of social network users to disclose personal information leads to the phenomenon that comments to news can reveal the data withheld in the news itself. This gives us a mean to figure out who the subject of the censored news is. We propose an adaptation of a text analysis approach to unveil censored identities. The approach is tested on a synthesised scenario, which however resembles a real use case. Leveraging a text analysis based on a context classifier trained over snippets from posts and comments of Facebook pages, we achieve promising results. Despite the quite constrained settings in which we operate -- such as considering only snippets of very short length -- our system successfully detects the censored name, choosing among 10 different candidate names, in more than 50\% of the investigated cases. This outperforms the results of two reference baselines. The findings reported in this paper, other than being supported by a thorough experimental methodology and interesting on their own, also pave the way for further investigation on the insidious issues of censorship on the web.
A Non-blocking Buddy System for Scalable Memory Allocation on Multi-core Machines
Venue: arXiv cs.DC 2018
Year: 2018

Common implementations of core memory allocation components, like the Linux buddy system, handle concurrent allocation/release requests by synchronizing threads via spin-locks. This approach is clearly not prone to scale with large thread counts, a problem that has been addressed in the literature by introducing layered allocation services or replicating the core allocators-the bottom most ones within the layered architecture. Both these solutions tend to reduce the pressure of actual concurrent accesses to each individual core allocator. In this article we explore an alternative approach to scalability of memory allocation/release, which can be still combined with those literature proposals. Conflict detection relies on conventional atomic machine instructions in the Read-Modify-Write (RMW) class. Furthermore, beyond improving scalability and performance, it can also avoid wasting clock cycles for spin-lock operations by threads that could in principle carry out their memory allocation/release in full concurrency. Thus, it is resilient to performance degradation---in face of concurrent accesses---independently of the current level of fragmentation of the handled memory blocks.
Seeing Through Misinformation: A Framework for Identifying Fake Online News
Venue: arXiv cs.CY 2018
Year: 2018

The fake news epidemic makes it imperative to develop a diagnostic framework that is both parsimonious and valid to guide present and future efforts in fake news detection. This paper represents one of the very first attempts to fill a void in the research on this topic. The LeSiE (Lexical Structure, Simplicity, Emotion) framework we created and validated allows lay people to identify potential fake news without the use of calculators or complex statistics by looking out for three simple cues.
Multi-band RF Energy and Spectrum Harvesting in Cognitive Radio Networks
Venue: arXiv cs.NI 2018
Year: 2018

This paper investigates a multi-band harvesting (EH) schemes under cognitive radio interweave framework. All secondary users are considered as EH nodes that are allowed to harvest energy from multiple bands of Radio Frequency (RF) sources. A win-win framework is proposed, where SUs can sense the spectrum to determine whether the spectrum is busy, and hence they may harvest from RF energy, or if it is idle, and hence they can use it for transmission. Only a subset of the SUs can sense in order to reduce sensing energy, and then machine learning is used to characterize areas of harvesting and spectrum usage. We formulate an optimization problem that jointly optimize number of sensing samples and sensing threshold in order to minimize the sensing time and hence maximize the amount of energy harvested. A near optimal solution is proposed using Geometric Programming (GP) to optimally solve the problem in a time-slotted period. Finally, an energy efficient approach based on multi-class Support Vector Machine (SVM) is proposed by involving only training SUs instead of all SUs.
Looking to Listen at the Cocktail Party: A Speaker-Independent Audio-Visual Model for Speech Separation
Venue: arXiv cs.SD 2018
Year: 2018

We present a joint audio-visual model for isolating a single speech signal from a mixture of sounds such as other speakers and background noise. Solving this task using only audio as input is extremely challenging and does not provide an association of the separated speech signals with speakers in the video. In this paper, we present a deep network-based model that incorporates both visual and auditory signals to solve this task. The visual features are used to "focus" the audio on desired speakers in a scene and to improve the speech separation quality. To train our joint audio-visual model, we introduce AVSpeech, a new dataset comprised of thousands of hours of video segments from the Web. We demonstrate the applicability of our method to classic speech separation tasks, as well as real-world scenarios involving heated interviews, noisy bars, and screaming children, only requiring the user to specify the face of the person in the video whose speech they want to isolate. Our method shows clear advantage over state-of-the-art audio-only speech separation in cases of mixed speech. In addition, our model, which is speaker-independent (trained once, applicable to any speaker), produces better results than recent audio-visual speech separation methods that are speaker-dependent (require training a separate model for each speaker of interest).
Probabilistic Prediction of Vehicle Semantic Intention and Motion
Venue: arXiv cs.LG 2018
Year: 2018

Accurately predicting the possible behaviors of traffic participants is an essential capability for future autonomous vehicles. The majority of current researches fix the number of driving intentions by considering only a specific scenario. However, distinct driving environments usually contain various possible driving maneuvers. Therefore, a intention prediction method that can adapt to different traffic scenarios is needed. To further improve the overall vehicle prediction performance, motion information is usually incorporated with classified intentions. As suggested in some literature, the methods that directly predict possible goal locations can achieve better performance for long-term motion prediction than other approaches due to their automatic incorporation of environment constraints. Moreover, by obtaining the temporal information of the predicted destinations, the optimal trajectories for predicted vehicles as well as the desirable path for ego autonomous vehicle could be easily generated. In this paper, we propose a Semantic-based Intention and Motion Prediction (SIMP) method, which can be adapted to any driving scenarios by using semantic-defined vehicle behaviors. It utilizes a probabilistic framework based on deep neural network to estimate the intentions, final locations, and the corresponding time information for surrounding vehicles. An exemplar real-world scenario was used to implement and examine the proposed method.
Deep Learning for Digital Text Analytics: Sentiment Analysis
Venue: arXiv cs.CL 2018
Year: 2018

In today's scenario, imagining a world without negativity is something very unrealistic, as bad NEWS spreads more virally than good ones. Though it seems impractical in real life, this could be implemented by building a system using Machine Learning and Natural Language Processing techniques in identifying the news datum with negative shade and filter them by taking only the news with positive shade (good news) to the end user. In this work, around two lakhs datum have been trained and tested using a combination of rule-based and data driven approaches. VADER along with a filtration method has been used as an annotating tool followed by statistical Machine Learning approach that have used Document Term Matrix (representation) and Support Vector Machine (classification). Deep Learning algorithms then came into picture to make this system reliable (Doc2Vec) which finally ended up with Convolutional Neural Network(CNN) that yielded better results than the other experimented modules. It showed up a training accuracy of 96%, while a test accuracy of (internal and external news datum) above 85% was obtained.
Gotta Learn Fast: A New Benchmark for Generalization in RL
Venue: arXiv cs.LG 2018
Year: 2018

In this report, we present a new reinforcement learning (RL) benchmark based on the Sonic the Hedgehog (TM) video game franchise. This benchmark is intended to measure the performance of transfer learning and few-shot learning algorithms in the RL domain. We also present and evaluate some baseline algorithms on the new benchmark.
On the Geometric Conservation Law for the Non Linear Frequency Domain and Time-Spectral Methods
Venue: arXiv cs.CE 2018
Year: 2018

The aim of this paper is to present and validate two new procedures to enforce the Geometric Conservation Law (GCL) on a moving grid for an Arbitrary Lagrangian Eulerian (ALE) formulation of the Euler equations discretized in time for either the Non Linear Frequency Domain (NLFD) or Time-Spectral (TS) methods. The equations are spatially discretized by a structured finite-volume scheme on a hexahedral mesh. The derived methodologies follow a general approach where the positions and the velocities of the grid points are known at each time step. The integrated face mesh velocities are derived either from the Approximation of the Exact Volumetric Increments (AEVI) relative to the undeformed mesh or exactly computed based on a Trilinear Mapping (TRI-MAP) between the physical space and the computational domain. The accuracy of the AEVI method highly depends on the computation of the volumetric increments and limits the temporal-order of accuracy of the deduced integrated face mesh velocities to between one and two. Thus defeating the purpose of the NLFD method which possesses spectral rate of convergence. However, the TRI-MAP method has proven to be more computationally efficient, ensuring the satisfaction of the GCL once the convergence of the time derivative of the cell volume is reached in Fourier space. The methods are validated numerically by verifying the conservation of uniform flow and by comparing the integrated face mesh velocities to the exact values derived from the mapping.
Control of Connected and Automated Vehicles: State of the Art and Future Challenges
Venue: arXiv cs.SY 2018
Year: 2018

Autonomous driving technology pledges safety, convenience, and energy efficiency. Challenges include the unknown intentions of other road users: communication between vehicles and with the road infrastructure is a possible approach to enhance awareness and enable cooperation. Connected and automated vehicles (CAVs) have the potential to disrupt mobility, extending what is possible with driving automation and connectivity alone. Applications include real-time control and planning with increased awareness, routing with micro-scale traffic information, coordinated platooning using traffic signals information, eco-mobility on demand with guaranteed parking. This paper introduces a control and planning architecture for CAVs, and surveys the state of the art on each functional block therein; the main focus is on techniques to improve energy efficiency. We provide an overview of existing algorithms and their mutual interactions, we present promising optimization-based approaches to CAVs control and identify future challenges.