OpenRaiser/Intern-Atlas huggingface dataset:
A General Constrained Shortest Path Approach for Virtual Path Embedding
Venue: arXiv cs.NI 2016
Year: 2016

Network virtualization has become a fundamental technology to deliver services for emerging data-intensive applications in fields such as bioinformatics and retail analytics hosted at multi-data center scales. To create and maintain a successful virtual network service, the problem of generating a constrained path manifests both in the management plane with a physical path creation (chains of virtual network functions or virtual link embedding) and in the data plane with on-demand path adaptation (traffic steering with Service Level Objective (SLO) guarantees). In this paper, we define the virtual path embedding problem to subsume the virtual link embedding and the constrained traffic steering problems, and propose a new scheme to solve it optimally. Specifically, we introduce a novel algorithm viz., "Neighborhood Method" (NM) which provides an on-demand path with SLO guarantees while reducing expensive over provisioning. We show that by solving the Virtual Path Embedding problem in a set of diverse topology scenarios we gain up to 20% in network utilization, and up to 150% in energy efficiency, compared to the existing path embedding solutions.
Matrix Factorization Method for Decentralized Recommender Systems
Venue: arXiv cs.IR 2016
Year: 2016

Decentralized recommender system does not rely on the central service provider, and the users can keep the ownership of their ratings. This article brings the theoretically well-studied matrix factorization method into the decentralized recommender system, where the formerly prevalent algorithms are heuristic and hence lack of theoretical guarantee. Our preliminary simulation results show that this method is promising.
Optimal pattern matching algorithms
Venue: arXiv cs.CC 2016
Year: 2016

We study a class of finite state machines, called \defi{$w$-matching machines}, which yield to simulate the behavior of pattern matching algorithms while searching for a pattern $w$. They can be used to compute the asymptotic speed, i.e. the limit of the expected ratio of the number of text accesses to the length of the text, of algorithms while parsing an iid text to find the pattern $w$. Defining the order of a matching machine or of an algorithm as the maximum difference between the current and accessed positions during a search (standard algorithms are generally of order $|w|$), we show that being given a pattern $w$, an order $k$ and an iid model, there exists an optimal $w$-matching machine, i.e. with the greatest asymptotic speed under the model among all the machines of order $k$, of which the set of states belongs to a finite and enumerable set. It shows that it is possible to determine: 1) the greatest asymptotic speed among a large class of algorithms, with regard to a pattern and an iid model, and 2) a $w$-matching machine, thus an algorithm, achieving this speed.
Array Program Transformation with Loo.py by Example: High-Order Finite Elements
Venue: arXiv cs.PL 2016
Year: 2016

To concisely and effectively demonstrate the capabilities of our program transformation system Loo.py, we examine a transformation path from two real-world Fortran subroutines as found in a weather model to a single high-performance computational kernel suitable for execution on modern GPU hardware. Along the transformation path, we encounter kernel fusion, vectorization, prefetch- ing, parallelization, and algorithmic changes achieved by mechanized conversion between imperative and functional/substitution- based code, among a number more. We conclude with performance results that demonstrate the effects and support the effectiveness of the applied transformations.
KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
Venue: arXiv cs.DS 2016
Year: 2016

We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks. The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time $|E|^{\frac{1}{2}+o(1)}$ with high probability, obtaining a significant speedup with respect to the $Θ(|E|)$ worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the $k$ most central nodes. Furthermore, our analysis is general, and it might be extended to other settings.
Decomposing Cubic Graphs into Connected Subgraphs of Size Three
Venue: arXiv cs.DS 2016
Year: 2016

Let $S=\{K_{1,3},K_3,P_4\}$ be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph $G$ into graphs taken from any non-empty $S'\subseteq S$. The problem is known to be NP-complete for any possible choice of $S'$ in general graphs. In this paper, we assume that the input graph is cubic, and study the computational complexity of the problem of partitioning its edge set for any choice of $S'$. We identify all polynomial and NP-complete problems in that setting, and give graph-theoretic characterisations of $S'$-decomposable cubic graphs in some cases.
Dynamic Clustering and Sleep Mode Strategies for Small Cell Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, a novel cluster-based approach for optimizing the energy efficiency of wireless small cell networks is proposed. A dynamic mechanism based on the spectral clustering technique is proposed to dynamically form clusters of small cell base stations. Such clustering enables intra-cluster coordination among the base stations for optimizing the downlink performance through load balancing, while satisfying users' quality-of-service requirements. In the proposed approach, the clusters use an opportunistic base station sleep-wake switching mechanism to strike a balance between delay and energy consumption. The inter-cluster interference affects the performance of the clusters and their choices of active or sleep state. Due to the lack of inter-cluster communications, the clusters have to compete with each other to make decisions on improving the energy efficiency. This competition is formulated as a noncooperative game among the clusters that seek to minimize a cost function which captures the tradeoff between energy expenditure and load. To solve this game, a distributed learning algorithm is proposed using which the clusters autonomously choose their optimal transmission strategies. Simulation results show that the proposed approach yields significant performance gains in terms of reduced energy expenditures up to 40% and reduced load up to 23% compared to conventional approaches.
Undecidability of Two-dimensional Robot Games
Venue: arXiv cs.GT 2016
Year: 2016

Robot game is a two-player vector addition game played on the integer lattice $\mathbb{Z}^n$. Both players have sets of vectors and in each turn the vector chosen by a player is added to the current configuration vector of the game. One of the players, called Eve, tries to play the game from the initial configuration to the origin while the other player, Adam, tries to avoid the origin. The problem is to decide whether or not Eve has a winning strategy. In this paper we prove undecidability of the robot game in dimension two answering the question formulated by Doyen and Rabinovich in 2011 and closing the gap between undecidable and decidable cases.
Teaching natural language to computers
Venue: arXiv cs.CL 2016
Year: 2016

"Natural Language," whether spoken and attended to by humans, or processed and generated by computers, requires networked structures that reflect creative processes in semantic, syntactic, phonetic, linguistic, social, emotional, and cultural modules. Being able to produce novel and useful behavior following repeated practice gets to the root of both artificial intelligence and human language. This paper investigates the modalities involved in language-like applications that computers -- and programmers -- engage with, and aims to fine tune the questions we ask to better account for context, self-awareness, and embodiment.
Improved Dense Trajectory with Cross Streams
Venue: arXiv cs.CV 2016
Year: 2016

Improved dense trajectories (iDT) have shown great performance in action recognition, and their combination with the two-stream approach has achieved state-of-the-art performance. It is, however, difficult for iDT to completely remove background trajectories from video with camera shaking. Trajectories in less discriminative regions should be given modest weights in order to create more discriminative local descriptors for action recognition. In addition, the two-stream approach, which learns appearance and motion information separately, cannot focus on motion in important regions when extracting features from spatial convolutional layers of the appearance network, and vice versa. In order to address the above mentioned problems, we propose a new local descriptor that pools a new convolutional layer obtained from crossing two networks along iDT. This new descriptor is calculated by applying discriminative weights learned from one network to a convolutional layer of the other network. Our method has achieved state-of-the-art performance on ordinal action recognition datasets, 92.3% on UCF101, and 66.2% on HMDB51.
Convolutional Neural Networks for Attribute-based Active Authentication on Mobile Devices
Venue: arXiv cs.CV 2016
Year: 2016

We present a Deep Convolutional Neural Network (DCNN) architecture for the task of continuous authentication on mobile devices. To deal with the limited resources of these devices, we reduce the complexity of the networks by learning intermediate features such as gender and hair color instead of identities. We present a multi-task, part-based DCNN architecture for attribute detection that performs better than the state-of-the-art methods in terms of accuracy. As a byproduct of the proposed architecture, we are able to explore the embedding space of the attributes extracted from different facial parts, such as mouth and eyes, to discover new attributes. Furthermore, through extensive experimentation, we show that the attribute features extracted by our method outperform the previously presented attribute-based method and a baseline LBP method for the task of active authentication. Lastly, we demonstrate the effectiveness of the proposed architecture in terms of speed and power consumption by deploying it on an actual mobile device.
Faster R-CNN Features for Instance Search
Venue: arXiv cs.CV 2016
Year: 2016

Image representations derived from pre-trained Convolutional Neural Networks (CNNs) have become the new state of the art in computer vision tasks such as instance retrieval. This work explores the suitability for instance retrieval of image- and region-wise representations pooled from an object detection CNN such as Faster R-CNN. We take advantage of the object proposals learned by a Region Proposal Network (RPN) and their associated CNN features to build an instance search pipeline composed of a first filtering stage followed by a spatial reranking. We further investigate the suitability of Faster R-CNN features when the network is fine-tuned for the same objects one wants to retrieve. We assess the performance of our proposed system with the Oxford Buildings 5k, Paris Buildings 6k and a subset of TRECVid Instance Search 2013, achieving competitive results.
Provision of Public Goods on Networks: On Existence, Uniqueness, and Centralities
Venue: arXiv cs.GT 2016
Year: 2016

We consider the provision of public goods on networks of strategic agents. We study different effort outcomes of these network games, namely, the Nash equilibria, Pareto efficient effort profiles, and semi-cooperative equilibria (effort profiles resulting from interactions among coalitions of agents). We identify necessary and sufficient conditions on the structure of the network for the uniqueness of the Nash equilibrium. We show that our finding unifies (and strengthens) existing results in the literature. We also identify conditions for the existence of Nash equilibria for the subclasses of games at the two extremes of our model, namely games of strategic complements and games of strategic substitutes. We provide a graph-theoretical interpretation of agents' efforts at the Nash equilibrium, as well as the Pareto efficient outcomes and semi-cooperative equilibria, by linking an agent's decision to her centrality in the interaction network. Using this connection, we separate the effects of incoming and outgoing edges on agents' efforts and uncover an alternating effect over walks of different length in the network.
Skybridge-3D-CMOS: A Vertically-Composed Fine-Grained 3D CMOS Integrated Circuit Technology
Venue: arXiv cs.ET 2016
Year: 2016

Parallel and monolithic 3D integration directions offer pathways to realize 3D integrated circuits (ICs) but still lead to layer-by-layer implementations, each functional layer being composed in 2D first. This mindset causes challenging connectivity, routing and layer alignment between layers when connected in 3D, with a routing access that can be even worse than 2D CMOS, which fundamentally limits their potential. To fully exploit the opportunities in the third dimension, we propose Skybridge-3D-CMOS (S3DC), a fine-grained 3D integration approach that is directly composed in 3D, utilizing the vertical dimension vs. using a layer-by-layer assembly mindset. S3DC uses a novel wafer fabric creation with direct 3D design and connectivity in the vertical dimension. It builds on a uniform vertical nanowire template that is processed as a single wafer; it incorporates specifically architected structures for realizing devices, circuits, and heat management directly in 3D. Novel 3D interconnect concepts, including within the silicon layers, enable significantly improved routing flexibility in all three dimensions and a high-density 3D design paradigm overall. Intrinsic components for fabric-level 3D heat management are introduced. Extensive bottom-up simulations and experiments have been presented to validate the key fabric-enabling concepts. Evaluation results indicate up to 40x density and 10x performance-per-watt benefits against conventional 16-nm CMOS for the circuits studied; benefits are also at least an order of magnitude beyond what was shown to be possible with other 3D directions.
Predicting the direction of stock market prices using random forest
Venue: arXiv cs.LG 2016
Year: 2016

Predicting trends in stock market prices has been an area of interest for researchers for many years due to its complex and dynamic nature. Intrinsic volatility in stock market across the globe makes the task of prediction challenging. Forecasting and diffusion modeling, although effective can't be the panacea to the diverse range of problems encountered in prediction, short-term or otherwise. Market risk, strongly correlated with forecasting errors, needs to be minimized to ensure minimal risk in investment. The authors propose to minimize forecasting error by treating the forecasting problem as a classification problem, a popular suite of algorithms in Machine learning. In this paper, we propose a novel way to minimize the risk of investment in stock market by predicting the returns of a stock using a class of powerful machine learning algorithms known as ensemble learning. Some of the technical indicators such as Relative Strength Index (RSI), stochastic oscillator etc are used as inputs to train our model. The learning model used is an ensemble of multiple decision trees. The algorithm is shown to outperform existing algo- rithms found in the literature. Out of Bag (OOB) error estimates have been found to be encouraging. Key Words: Random Forest Classifier, stock price forecasting, Exponential smoothing, feature extraction, OOB error and convergence.
Deep Colorization
Venue: arXiv cs.CV 2016
Year: 2016

This paper investigates into the colorization problem which converts a grayscale image to a colorful version. This is a very difficult problem and normally requires manual adjustment to achieve artifact-free quality. For instance, it normally requires human-labelled color scribbles on the grayscale target image or a careful selection of colorful reference images (e.g., capturing the same scene in the grayscale target image). Unlike the previous methods, this paper aims at a high-quality fully-automatic colorization method. With the assumption of a perfect patch matching technique, the use of an extremely large-scale reference database (that contains sufficient color images) is the most reliable solution to the colorization problem. However, patch matching noise will increase with respect to the size of the reference database in practice. Inspired by the recent success in deep learning techniques which provide amazing modeling of large-scale data, this paper re-formulates the colorization problem so that deep learning techniques can be directly employed. To ensure artifact-free quality, a joint bilateral filtering based post-processing step is proposed. We further develop an adaptive image clustering technique to incorporate the global image information. Numerous experiments demonstrate that our method outperforms the state-of-art algorithms both in terms of quality and speed.
Multi-Connectivity in 5G mmWave Cellular Networks
Venue: arXiv cs.NI 2016
Year: 2016

The millimeter wave (mmWave) frequencies offer the potential of orders of magnitude increases in capacity for next-generation cellular wireless systems. However, links in mmWave networks are highly susceptible to blocking and may suffer from rapid variations in quality. Connectivity to multiple cells - both in the mmWave and in the traditional lower frequencies - is thus considered essential for robust connectivity. However, one of the challenges in supporting multi-connectivity in the mmWave space is the requirement for the network to track the direction of each link in addition to its power and timing. With highly directional beams and fast varying channels, this directional tracking may be the main bottleneck in realizing robust mmWave networks. To address this challenge, this paper proposes a novel measurement system based on (i) the UE transmitting sounding signals in directions that sweep the angular space, (ii) the mmWave cells measuring the instantaneous received signal strength along with its variance to better capture the dynamics and, consequently, the reliability of a channel/direction and, finally, (iii) a centralized controller making handover and scheduling decisions based on the mmWave cell reports and transmitting the decisions either via a mmWave cell or conventional microwave cell (when control signaling paths are not available). We argue that the proposed scheme enables efficient and highly adaptive cell selection in the presence of the channel variability expected at mmWave frequencies.
A Supervised Learning Algorithm for Binary Domain Classification of Web Queries using SERPs
Venue: arXiv cs.IR 2016
Year: 2016

General purpose Search Engines (SEs) crawl all domains (e.g., Sports, News, Entertainment) of the Web, but sometimes the informational need of a query is restricted to a particular domain (e.g., Medical). We leverage the work of SEs as part of our effort to route domain specific queries to local Digital Libraries (DLs). SEs are often used even if they are not the "best" source for certain types of queries. Rather than tell users to "use this DL for this kind of query", we intend to automatically detect when a query could be better served by a local DL (such as a private, access-controlled DL that is not crawlable via SEs). This is not an easy task because Web queries are short, ambiguous, and there is lack of quality labeled training data (or it is expensive to create). To detect queries that should be routed to local, specialized DLs, we first send the queries to Google and then examine the features in the resulting Search Engine Result Pages (SERPs), and then classify the query as belonging to either the scholar or non-scholar domain. Using 400,000 AOL queries for the non-scholar domain and 400,000 queries from the NASA Technical Report Server (NTRS) for the scholar domain, our classifier achieved a precision of 0.809 and F-measure of 0.805.
Distributed Detection Fusion via Monte Carlo Importance Sampling
Venue: arXiv cs.IT 2016
Year: 2016

Distributed detection fusion with high-dimension conditionally dependent observations is known to be a challenging problem. When a fusion rule is fixed, this paper attempts to make progress on this problem for the large sensor networks by proposing a new Monte Carlo framework. Through the Monte Carlo importance sampling, we derive a necessary condition for optimal sensor decision rules in the sense of minimizing the approximated Bayesian cost function. Then, a Gauss-Seidel/person-by-person optimization algorithm can be obtained to search the optimal sensor decision rules. It is proved that the discretized algorithm is finitely convergent. The complexity of the new algorithm is $O(LN)$ compared with $O(LN^L)$ of the previous algorithm where $L$ is the number of sensors and $N$ is a constant. Thus, the proposed methods allows us to design the large sensor networks with general high-dimension dependent observations. Furthermore, an interesting result is that, for the fixed AND or OR fusion rules, we can analytically derive the optimal solution in the sense of minimizing the approximated Bayesian cost function. In general, the solution of the Gauss-Seidel algorithm is only local optimal. However, in the new framework, we can prove that the solution of Gauss-Seidel algorithm is same as the analytically optimal solution in the case of the AND or OR fusion rule. The typical examples with dependent observations and large number of sensors are examined under this new framework. The results of numerical examples demonstrate the effectiveness of the new algorithm.
A Self-Taught Artificial Agent for Multi-Physics Computational Model Personalization
Venue: arXiv cs.CE 2016
Year: 2016

Personalization is the process of fitting a model to patient data, a critical step towards application of multi-physics computational models in clinical practice. Designing robust personalization algorithms is often a tedious, time-consuming, model- and data-specific process. We propose to use artificial intelligence concepts to learn this task, inspired by how human experts manually perform it. The problem is reformulated in terms of reinforcement learning. In an off-line phase, Vito, our self-taught artificial agent, learns a representative decision process model through exploration of the computational model: it learns how the model behaves under change of parameters. The agent then automatically learns an optimal strategy for on-line personalization. The algorithm is model-independent; applying it to a new model requires only adjusting few hyper-parameters of the agent and defining the observations to match. The full knowledge of the model itself is not required. Vito was tested in a synthetic scenario, showing that it could learn how to optimize cost functions generically. Then Vito was applied to the inverse problem of cardiac electrophysiology and the personalization of a whole-body circulation model. The obtained results suggested that Vito could achieve equivalent, if not better goodness of fit than standard methods, while being more robust (up to 11% higher success rates) and with faster (up to seven times) convergence rate. Our artificial intelligence approach could thus make personalization algorithms generalizable and self-adaptable to any patient and any model.