OpenRaiser/Intern-Atlas huggingface dataset:
Detecting Qualia in Natural and Artificial Agents
Venue: arXiv cs.AI 2017
Year: 2017

The Hard Problem of consciousness has been dismissed as an illusion. By showing that computers are capable of experiencing, we show that they are at least rudimentarily conscious with potential to eventually reach superconsciousness. The main contribution of the paper is a test for confirming certain subjective experiences in a tested agent. We follow with analysis of benefits and problems with conscious machines and implications of such capability on future of computing, machine rights and artificial intelligence safety.
How to navigate through obstacles?
Venue: arXiv cs.CG 2017
Year: 2017

Given a set of obstacles and two points, is there a path between the two points that does not cross more than $k$ different obstacles? This is a fundamental problem that has undergone a tremendous amount of work. It is known to be NP-hard, even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). The problem can be generalized into the following graph problem: Given a planar graph $G$ whose vertices are colored by color sets, two designated vertices $s, t \in V(G)$, and $k \in \mathbb{N}$, is there an $s$-$t$ path in $G$ that uses at most $k$ colors? If each obstacle is connected, the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph. We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove that without the color-connectivity property, the problem is W[SAT]-hard parameterized by $k$. A corollary of this result is that, unless W[2] $=$ FPT, the problem cannot be approximated in FPT time to within a factor that is a function of $k$. By describing a generic plane embedding of the graph instances, we show that our hardness results translate to the geometric instances of the problem. We then focus on graphs satisfying the color-connectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results to "represent" the valid $s$-$t$ paths containing subsets of colors from any vertex $v$. We employ these results to design an FPT algorithm for the problem parameterized by both $k$ and the treewidth of the graph, and extend this result to obtain an FPT algorithm for the parameterization by both $k$ and the length of the path. The latter result directly implies previous FPT results for various obstacle shapes, such as unit disks and fat regions.
Cavs: A Vertex-centric Programming Interface for Dynamic Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Recent deep learning (DL) models have moved beyond static network architectures to dynamic ones, handling data where the network structure changes every example, such as sequences of variable lengths, trees, and graphs. Existing dataflow-based programming models for DL---both static and dynamic declaration---either cannot readily express these dynamic models, or are inefficient due to repeated dataflow graph construction and processing, and difficulties in batched execution. We present Cavs, a vertex-centric programming interface and optimized system implementation for dynamic DL models. Cavs represents dynamic network structure as a static vertex function $\mathcal{F}$ and a dynamic instance-specific graph $\mathcal{G}$, and performs backpropagation by scheduling the execution of $\mathcal{F}$ following the dependencies in $\mathcal{G}$. Cavs bypasses expensive graph construction and preprocessing overhead, allows for the use of static graph optimization techniques on pre-defined operations in $\mathcal{F}$, and naturally exposes batched execution opportunities over different graphs. Experiments comparing Cavs to two state-of-the-art frameworks for dynamic NNs (TensorFlow Fold and DyNet) demonstrate the efficacy of this approach: Cavs achieves a near one order of magnitude speedup on training of various dynamic NN architectures, and ablations demonstrate the contribution of our proposed batching and memory management strategies.
The Eigenoption-Critic Framework
Venue: arXiv cs.AI 2017
Year: 2017

Eigenoptions (EOs) have been recently introduced as a promising idea for generating a diverse set of options through the graph Laplacian, having been shown to allow efficient exploration. Despite its initial promising results, a couple of issues in current algorithms limit its application, namely: (1) EO methods require two separate steps (eigenoption discovery and reward maximization) to learn a control policy, which can incur a significant amount of storage and computation; (2) EOs are only defined for problems with discrete state-spaces and; (3) it is not easy to take the environment's reward function into consideration when discovering EOs. To addresses these issues, we introduce an algorithm termed eigenoption-critic (EOC) based on the Option-critic (OC) framework [Bacon17], a general hierarchical reinforcement learning (RL) algorithm that allows learning the intra-option policies simultaneously with the policy over options. We also propose a generalization of EOC to problems with continuous state-spaces through the Nyström approximation. EOC can also be seen as extending OC to nonstationary settings, where the discovered options are not tailored for a single task.
The Gaussian Interference Channel in the Presence of Malicious Jammers
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the two-user Gaussian interference channel in the presence of adversarial jammers. We first provide a general model including an arbitrary number of jammers, and show that its capacity region is equivalent to that of a simplified model in which the received jamming signal at each decoder is independent. Next, existing outer and inner bounds for two-user Gaussian interference channel are generalized for this simplified jamming model. We show that for certain problem parameters, precisely the same bounds hold, but with the noise variance increased by the received power of the jammer at each receiver. Thus, the jammers can do no better than to transmit Gaussian noise. For these problem parameters, this allows us to recover the half-bit theorem. In weak and strong interference regime, our inner bound matches the corresponding Han-Kobayashi bound with increased noise variance by the received power of the jammer, and even in strong interference we achieve the exact capacity. Furthermore, we determine the symmetric degrees of freedom where the signal-to-noise, interference-to-noise and jammer-to-noise ratios are all tend to infinity. Moreover, we show that, if the jammer has greater received power than the legitimate user, symmetrizability makes the capacity zero. The proof of the outer bound is straightforward, while the inner bound generalizes the Han-Kobayashi rate splitting scheme. As a novel aspect, the inner bound takes advantage of the common message acting as common randomness for the private message; hence, the jammer cannot symmetrize only the private codeword without being detected. This complication requires an extra condition on the signal power, so that in general our inner bound is not identical to the Han-Kobayashi bound. We also prove a new variation of the packing lemma that applies for multiple Gaussian codebooks in an adversarial setting.
A Practical Approach for Detecting Logical Error in Object Oriented Environment
Venue: arXiv cs.SE 2017
Year: 2017

A programming language is a formally constructed language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs to control the behavior of a machine or to express algorithms. Most programs that are written by programmers are often compiled correctly with no syntax or semantic errors. However, some other errors appear after the execution of the program (logical error). Logical Errors (LE) are errors that remain after all syntax errors have been removed. Usually, the compiler does not detect LE, so the produced results are different from what the programmer is expecting. For this reason, discovering and fixing the logical error is very hard and proposes a good topic for research and practice. Some LE are resulted from the misuse of classes' objects, and in Software Development Life Cycle (SDLC), it is considered that the software with LE is low-quality software with high maintenance cost. In this paper, an object-oriented environment that allows the programmer to detect and discover LE to avoid it. This environment will be called Object Behavior Environment (OBEnvironment) will enforce the correct use of objects according to their predefined behaviors by using tools like Xceed Component (that appeal .Net windows form developers for building better applications), Alsing Component (that provides an area to programmer that allows writing correct syntax code by C# language) and, Mind Fusion Component (that provides an area to programmer that allows drawing State Diagrams to show object state).
Empirical Evaluation of Kernel PCA Approximation Methods in Classification Tasks
Venue: arXiv cs.LG 2017
Year: 2017

Kernel Principal Component Analysis (KPCA) is a popular dimensionality reduction technique with a wide range of applications. However, it suffers from the problem of poor scalability. Various approximation methods have been proposed in the past to overcome this problem. The Nyström method, Randomized Nonlinear Component Analysis (RNCA) and Streaming Kernel Principal Component Analysis (SKPCA) were proposed to deal with the scalability issue of KPCA. Despite having theoretical guarantees, their performance in real world learning tasks have not been explored previously. In this work the evaluation of SKPCA, RNCA and Nyström method for the task of classification is done for several real world datasets. The results obtained indicate that SKPCA based features gave much better classification accuracy when compared to the other methods for a very large dataset.
Coordinator Location Effects in AODV Routing Protocol in ZigBee Mesh Network
Venue: arXiv cs.NI 2017
Year: 2017

ZigBee mesh network is very important research field in computer networks. However, the location of ZigBee coordinator plays a significant role in design and routing performance. In this paper, an extensive study on the factors that influence the performance of AODV routing protocol had been performed through the study of battery voltage decaying of nodes, neighboring tables, time delay and network topology structure. Simulation results reveal that the location of the coordinator within approximate equal distances to all nodes is more appropriate for lifelong batteries and AODV routing performance.
De-anonymizing Social Networks with Overlapping Community Structure
Venue: arXiv cs.SI 2017
Year: 2017

The advent of social networks poses severe threats on user privacy as adversaries can de-anonymize users' identities by mapping them to correlated cross-domain networks. Without ground-truth mapping, prior literature proposes various cost functions in hope of measuring the quality of mappings. However, there is generally a lacking of rationale behind the cost functions, whose minimizer also remains algorithmically unknown. We jointly tackle above concerns under a more practical social network model parameterized by overlapping communities, which, neglected by prior art, can serve as side information for de-anonymization. Regarding the unavailability of ground-truth mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our first contribution is a well-justified cost function minimizing the expected number of mismatched users over all possible true mappings. While proving the NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge matching problem (WEMP), which, as disclosed theoretically, resolves the tension between optimality and complexity: (i) WEMP asymptotically returns a negligible mapping error in large network size under mild conditions facilitated by higher overlapping strength; (ii) WEMP can be algorithmically characterized via the convex-concave based de-anonymization algorithm (CBDA), perfectly finding the optimum of WEMP. Extensive experiments further confirm the effectiveness of CBDA under overlapping communities, in terms of averagely 90% re-identified users in the rare true cross-domain co-author networks when communities overlap densely, and roughly 70% enhanced re-identification ratio compared to non-overlapping cases.
A Streaming Algorithm for Graph Clustering
Venue: arXiv cs.LG 2017
Year: 2017

We introduce a novel algorithm to perform graph clustering in the edge streaming setting. In this model, the graph is presented as a sequence of edges that can be processed strictly once. Our streaming algorithm has an extremely low memory footprint as it stores only three integers per node and does not keep any edge in memory. We provide a theoretical justification of the design of the algorithm based on the modularity function, which is a usual metric to evaluate the quality of a graph partition. We perform experiments on massive real-life graphs ranging from one million to more than one billion edges and we show that this new algorithm runs more than ten times faster than existing algorithms and leads to similar or better detection scores on the largest graphs.
Predicting Yelp Star Reviews Based on Network Structure with Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we tackle the real-world problem of predicting Yelp star-review rating based on business features (such as images, descriptions), user features (average previous ratings), and, of particular interest, network properties (which businesses has a user rated before). We compare multiple models on different sets of features -- from simple linear regression on network features only to deep learning models on network and item features. In recent years, breakthroughs in deep learning have led to increased accuracy in common supervised learning tasks, such as image classification, captioning, and language understanding. However, the idea of combining deep learning with network feature and structure appears to be novel. While the problem of predicting future interactions in a network has been studied at length, these approaches have often ignored either node-specific data or global structure. We demonstrate that taking a mixed approach combining both node-level features and network information can effectively be used to predict Yelp-review star ratings. We evaluate on the Yelp dataset by splitting our data along the time dimension (as would naturally occur in the real-world) and comparing our model against others which do no take advantage of the network structure and/or deep learning.
Agent Based Distributed Control of Islanded Microgrid - Real-Time Cyber-Physical Implementation
Venue: arXiv cs.SY 2017
Year: 2017

In the hierarchical control of an islanded microgrid, secondary control could be centralized or distributed. The former control strategy has several disadvantages, such as single point of failure at the level of the central controller as well as high investment of communication infrastructure. In this paper a three-layer architecture of distributed control is given, including the device layer, the control layer as well as the agent layer. The agent layer is a multi-agent system in which each agent is in charge of a distributed generation unit. Due to communication network constraints, agents are connected only to nearby neighbors. However, by using consensus algorithms the agents can discover the required global information and compute new references for the control layer. The proposed control system is tested on a microgrid scenario which includes paralleled inverter sources. For this, the system is implemented on a real-time cyber-physical test platform that combines real-time simulation models running in OPAL-RT with a network of ARM-based computers, representing the agents.
A characterization of colorless anonymous $t$-resilient task computability
Venue: arXiv cs.DC 2017
Year: 2017

A task is a distributed problem for $n$ processes, in which each process starts with a private input value, communicates with other processes, and eventually decides an output value. A task is colorless if each process can adopt the input or output value of another process. Colorless tasks are well studied in the non-anonymous shared-memory model where each process has a distinct identifier that can be used to access a single-writer/multi-reader shared register. In the anonymous case, where processes have no identifiers and communicate through multi-writer/multi-reader registers, there is a recent topological characterization of the colorless tasks that are solvable when any number of asynchronous processes may crash. In this paper we study the case where at most $t$ processes may crash, where $1 \le t < n$. We prove that a colorless task is $t$-resilient solvable non-anonymously if and only if it is $t$-resilient solvable anonymously. This implies a complete characterization of colorless anonymous t-resilient asynchronous task computability.
Android Malware Characterization using Metadata and Machine Learning Techniques
Venue: arXiv cs.CR 2017
Year: 2017

Android Malware has emerged as a consequence of the increasing popularity of smartphones and tablets. While most previous work focuses on inherent characteristics of Android apps to detect malware, this study analyses indirect features and meta-data to identify patterns in malware applications. Our experiments show that: (1) the permissions used by an application offer only moderate performance results; (2) other features publicly available at Android Markets are more relevant in detecting malware, such as the application developer and certificate issuer, and (3) compact and efficient classifiers can be constructed for the early detection of malware applications prior to code inspection or sandboxing.
Learning a Complete Image Indexing Pipeline
Venue: arXiv cs.CV 2017
Year: 2017

To work at scale, a complete image indexing system comprises two components: An inverted file index to restrict the actual search to only a subset that should contain most of the items relevant to the query; An approximate distance computation mechanism to rapidly scan these lists. While supervised deep learning has recently enabled improvements to the latter, the former continues to be based on unsupervised clustering in the literature. In this work, we propose a first system that learns both components within a unifying neural framework of structured binary encoding.
Intra-node Memory Safe GPU Co-Scheduling
Venue: arXiv cs.DC 2017
Year: 2017

GPUs in High-Performance Computing systems remain under-utilised due to the unavailability of schedulers that can safely schedule multiple applications to share the same GPU. The research reported in this paper is motivated to improve the utilisation of GPUs by proposing a framework, we refer to as schedGPU, to facilitate intra-node GPU co-scheduling such that a GPU can be safely shared among multiple applications by taking memory constraints into account. Two approaches, namely a client-server and a shared memory approach are explored. However, the shared memory approach is more suitable due to lower overheads when compared to the former approach. Four policies are proposed in schedGPU to handle applications that are waiting to access the GPU, two of which account for priorities. The feasibility of schedGPU is validated on three real-world applications. The key observation is that a performance gain is achieved. For single applications, a gain of over 10 times, as measured by GPU utilisation and GPU memory utilisation, is obtained. For workloads comprising multiple applications, a speed-up of up to 5x in the total execution time is noted. Moreover, the average GPU utilisation and average GPU memory utilisation is increased by 5 and 12 times, respectively.
Computational Properties of Slime Trail
Venue: arXiv cs.CC 2017
Year: 2017

We investigate the combinatorial game Slime Trail.This game is played on a graph with a starting piece in a node. Each player's objective is to reach one of their own goal nodes. Every turn the current player moves the piece and deletes the node they came from. We show that the game is PSPACE-complete when played on a planar graph.
Multi-focus Attention Network for Efficient Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

Deep reinforcement learning (DRL) has shown incredible performance in learning various tasks to the human level. However, unlike human perception, current DRL models connect the entire low-level sensory input to the state-action values rather than exploiting the relationship between and among entities that constitute the sensory input. Because of this difference, DRL needs vast amount of experience samples to learn. In this paper, we propose a Multi-focus Attention Network (MANet) which mimics human ability to spatially abstract the low-level sensory input into multiple entities and attend to them simultaneously. The proposed method first divides the low-level input into several segments which we refer to as partial states. After this segmentation, parallel attention layers attend to the partial states relevant to solving the task. Our model estimates state-action values using these attended partial states. In our experiments, MANet attains highest scores with significantly less experience samples. Additionally, the model shows higher performance compared to the Deep Q-network and the single attention model as benchmarks. Furthermore, we extend our model to attentive communication model for performing multi-agent cooperative tasks. In multi-agent cooperative task experiments, our model shows 20% faster learning than existing state-of-the-art model.
Review of Design of Speech Recognition and Text Analytics based Digital Banking Customer Interface and Future Directions of Technology Adoption
Venue: arXiv cs.CY 2017
Year: 2017

Banking is one of the most significant adopters of cutting-edge information technologies. Since its modern era beginning in the form of paper based accounting maintained in the branch, adoption of computerized system made it possible to centralize the processing in data centre and improve customer experience by making a more available and efficient system. The latest twist in this evolution is adoption of natural language processing and speech recognition in the user interface between the human and the system and use of machine learning and advanced analytics, in general, for backend processing as well. The paper reviews the progress of technology adoption in the field and comments on the maturity level of solutions involving less studied or low-resource languages like Hindi and also other Indian, regional languages. Furthermore, it also provides an analysis from a prototype built by us. The future directions of this area are also highlighted.
Software Engineering Solutions To Support Vertical Transportation
Venue: arXiv cs.HC 2017
Year: 2017

In this paper we introduce the core results of the project on visualisation and analysis of data collected from the vertical transport facilities. The aim of the project was to provide better user experience as well as to help building maintenance staff to increase productivity of their work. We elaborated a web-based system for vertical transportation, to cover the needs of (1) staff working on building maintenance, (2) people who are regularly using the facilities in the corresponding buildings.