OpenRaiser/Intern-Atlas huggingface dataset:
Covering Uncertain Points in a Tree
Venue: arXiv cs.CG 2017
Year: 2017

In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set P of n (weighted) demand points, and the location of each demand point P_i\in P is uncertain but is known to appear in one of m_i points on T each associated with a probability. Given a covering range λ, the problem is to find a minimum number of points (called centers) on T to build facilities for serving (or covering) these demand points in the sense that for each uncertain point P_i\in P, the expected distance from P_i to at least one center is no more than $λ$. The problem has not been studied before. We present an O(|T|+M\log^2 M) time algorithm for the problem, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points of P, i.e., M=\sum_{P_i\in P}m_i. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P.
Learning of Human-like Algebraic Reasoning Using Deep Feedforward Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

There is a wide gap between symbolic reasoning and deep learning. In this research, we explore the possibility of using deep learning to improve symbolic reasoning. Briefly, in a reasoning system, a deep feedforward neural network is used to guide rewriting processes after learning from algebraic reasoning examples produced by humans. To enable the neural network to recognise patterns of algebraic expressions with non-deterministic sizes, reduced partial trees are used to represent the expressions. Also, to represent both top-down and bottom-up information of the expressions, a centralisation technique is used to improve the reduced partial trees. Besides, symbolic association vectors and rule application records are used to improve the rewriting processes. Experimental results reveal that the algebraic reasoning examples can be accurately learnt only if the feedforward neural network has enough hidden layers. Also, the centralisation technique, the symbolic association vectors and the rule application records can reduce error rates of reasoning. In particular, the above approaches have led to 4.6% error rate of reasoning on a dataset of linear equations, differentials and integrals.
Path Planning with Kinematic Constraints for Robot Groups
Venue: arXiv cs.AI 2017
Year: 2017

Path planning for multiple robots is well studied in the AI and robotics communities. For a given discretized environment, robots need to find collision-free paths to a set of specified goal locations. Robots can be fully anonymous, non-anonymous, or organized in groups. Although powerful solvers for this abstract problem exist, they make simplifying assumptions by ignoring kinematic constraints, making it difficult to use the resulting plans on actual robots. In this paper, we present a solution which takes kinematic constraints, such as maximum velocities, into account, while guaranteeing a user-specified minimum safety distance between robots. We demonstrate our approach in simulation and on real robots in 2D and 3D environments.
Semi-supervised Bayesian Deep Multi-modal Emotion Recognition
Venue: arXiv cs.AI 2017
Year: 2017

In emotion recognition, it is difficult to recognize human's emotional states using just a single modality. Besides, the annotation of physiological emotional data is particularly expensive. These two aspects make the building of effective emotion recognition model challenging. In this paper, we first build a multi-view deep generative model to simulate the generative process of multi-modality emotional data. By imposing a mixture of Gaussians assumption on the posterior approximation of the latent variables, our model can learn the shared deep representation from multiple modalities. To solve the labeled-data-scarcity problem, we further extend our multi-view model to semi-supervised learning scenario by casting the semi-supervised classification problem as a specialized missing data imputation task. Our semi-supervised multi-view deep generative framework can leverage both labeled and unlabeled data from multiple modalities, where the weight factor for each modality can be learned automatically. Compared with previous emotion recognition methods, our method is more robust and flexible. The experiments conducted on two real multi-modal emotion datasets have demonstrated the superiority of our framework over a number of competitors.
Optical Non-Orthogonal Multiple Access for Visible Light Communication
Venue: arXiv cs.IT 2017
Year: 2017

The proliferation of mobile Internet and connected devices, offering a variety of services at different levels of performance, represents a major challenge for the fifth generation wireless networks and beyond. This requires a paradigm shift towards the development of key enabling techniques for the next generation wireless networks. In this respect, visible light communication (VLC) has recently emerged as a new communication paradigm that is capable of providing ubiquitous connectivity by complementing radio frequency communications. One of the main challenges of VLC systems, however, is the low modulation bandwidth of the light-emitting-diodes, which is in the megahertz range. This article presents a promising technology, referred to as "optical- non-orthogonal multiple access (O-NOMA)", which is envisioned to address the key challenges in the next generation of wireless networks. We provide a detailed overview and analysis of the state-of-the-art integration of O-NOMA in VLC networks. Furthermore, we provide insights on the potential opportunities and challenges as well as some open research problems that are envisioned to pave the way for the future design and implementation of O-NOMA in VLC systems.
Tapping the sensorimotor trajectory
Venue: arXiv cs.NE 2017
Year: 2017

In this paper, we propose the concept of sensorimotor tappings, a new graphical technique that explicitly represents relations between the time steps of an agent's sensorimotor loop and a single training step of an adaptive internal model. In the simplest case this is a relation linking two time steps. In realistic cases these relations can extend over several time steps and over different sensory channels. The aim is to capture the footprint of information intake relative to the agent's current time step. We argue that this view allows us to make prior considerations explicit and then use them in implementations without modification once they are established. Here we explain the basic idea, provide example tappings for standard configurations used in developmental models, and show how tappings can be applied to problems in related fields.
Wireless Surveillance of Two-Hop Communications
Venue: arXiv cs.IT 2017
Year: 2017

Wireless surveillance is becoming increasingly important to protect the public security by legitimately eavesdropping suspicious wireless communications. This paper studies the wireless surveillance of a two-hop suspicious communication link by a half-duplex legitimate monitor. By exploring the suspicious link's two-hop nature, the monitor can adaptively choose among the following three eavesdropping modes to improve the eavesdropping performance: (I) \emph{passive eavesdropping} to intercept both hops to decode the message collectively, (II) \emph{proactive eavesdropping} via {\emph{noise jamming}} over the first hop, and (III) \emph{proactive eavesdropping} via {\emph{hybrid jamming}} over the second hop. In both proactive eavesdropping modes, the (noise/hybrid) jamming over one hop is for the purpose of reducing the end-to-end communication rate of the suspicious link and accordingly making the interception more easily over the other hop. Under this setup, we maximize the eavesdropping rate at the monitor by jointly optimizing the eavesdropping mode selection as well as the transmit power for noise and hybrid jamming. Numerical results show that the eavesdropping mode selection significantly improves the eavesdropping rate as compared to each individual eavesdropping mode.
An efficient data structure for counting all linear extensions of a poset, calculating its jump number, and the likes
Venue: arXiv cs.DS 2017
Year: 2017

Achieving the goals in the title (and others) relies on a cardinality-wise scanning of the ideals of the poset. Specifically, the relevant numbers attached to the k+1 element ideals are inferred from the corresponding numbers of the k-element (order) ideals. Crucial in all of this is a compressed representation (using wildcards) of the ideal lattice. The whole scheme invites distributed computation.
Secure Transmission with Large Numbers of Antennas and Finite Alphabet Inputs
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate secure transmission over the large-scale multiple-antenna wiretap channel with finite alphabet inputs. First, we investigate the case where instantaneous channel state information (CSI) of the eavesdropper is known at the transmitter. We show analytically that a generalized singular value decomposition (GSVD) based design, which is optimal for Gaussian inputs, may exhibit a severe performance loss for finite alphabet inputs in the high signal-to-noise ratio (SNR) regime. In light of this, we propose a novel Per-Group-GSVD (PG-GSVD) design which can effectively compensate the performance loss caused by the GSVD design. More importantly, the computational complexity of the PG-GSVD design is by orders of magnitude lower than that of the existing design for finite alphabet inputs in [1] while the resulting performance loss is minimal. Then, we extend the PG-GSVD design to the case where only statistical CSI of the eavesdropper is available at the transmitter. Numerical results indicate that the proposed PG-GSVD design can be efficiently implemented in large-scale multiple-antenna systems and achieves significant performance gains compared to the GSVD design.
A Calculus of Truly Concurrent Mobile Processes
Venue: arXiv cs.LO 2017
Year: 2017

We make a mixture of Milner's $π$-calculus and our previous work on truly concurrent process algebra, which is called $π_{tc}$. We introduce syntax and semantics of $π_{tc}$, its properties based on strongly truly concurrent bisimilarities. Also, we include an axiomatization of $π_{tc}$. $π_{tc}$ can be used as a formal tool in verifying mobile systems in a truly concurrent flavor.
Introspective Generative Modeling: Decide Discriminatively
Venue: arXiv cs.CV 2017
Year: 2017

We study unsupervised learning by developing introspective generative modeling (IGM) that attains a generator using progressively learned deep convolutional neural networks. The generator is itself a discriminator, capable of introspection: being able to self-evaluate the difference between its generated samples and the given training data. When followed by repeated discriminative learning, desirable properties of modern discriminative classifiers are directly inherited by the generator. IGM learns a cascade of CNN classifiers using a synthesis-by-classification algorithm. In the experiments, we observe encouraging results on a number of applications including texture modeling, artistic style transferring, face modeling, and semi-supervised learning.
Information transmission on hybrid networks
Venue: arXiv cs.NI 2017
Year: 2017

Many real-world communication networks often have hybrid nature with both fixed nodes and moving modes, such as the mobile phone networks mainly composed of fixed base stations and mobile phones. In this paper, we discuss the information transmission process on the hybrid networks with both fixed and mobile nodes. The fixed nodes (base stations) are connected as a spatial lattice on the plane forming the information-carrying backbone, while the mobile nodes (users), which are the sources and destinations of information packets, connect to their current nearest fixed nodes respectively to deliver and receive information packets. We observe the phase transition of traffic load in the hybrid network when the packet generation rate goes from below and then above a critical value, which measures the network capacity of packets delivery. We obtain the optimal speed of moving nodes leading to the maximum network capacity. We further improve the network capacity by rewiring the fixed nodes and by considering the current load of fixed nodes during packets transmission. Our purpose is to optimize the network capacity of hybrid networks from the perspective of network science, and provide some insights for the construction of future communication infrastructures.
Participating in a Computer Science Linked-courses Learning Community Reduces Isolation
Venue: arXiv cs.OH 2017
Year: 2017

In our previous work we reported on a linked-courses learning community for underrepresented groups in computer science, finding differences in attitudes and resource utilization between students in the community and other programming students. Here we present the first statistically significant differences in pre- to post-quarter student attitudes between those in the learning community and others taking equivalent programming classes. We find that students in the learning community are less likely to feel isolated post-quarter than other programming students. We also present results showing differences in resource utilization by learning-community participants.
The Role of Cloud of Things in Smart Cities
Venue: arXiv cs.CY 2017
Year: 2017

The recent demographic trends indicate towards a rapidly increasing population growth and a significant portion of this increased population now prefer to live mostly in cities. In connection with this, it has become the responsibility of the government to ensure a quality standard of living in the cities and also make sure that these facilities trickle down to the next generation. A program named Smart City Mission has been started for this purpose. With an extremely diverse population, that is only second to China in the world in terms of size, the Indian government has engaged in serious thinking for a better city planning and providing numerous opportunities for the citizenry. It was, therefore, planned that the Smart City Mission program will be able to provide a highly responsive infrastructure, network security, a good living environment and the like. Internet of things (IoT) application in smart cities turns out to be the most challenging in this phase. The information available in the internet has made accessible to many devices through IoT and it also aware the citizen in many aspects. But with the increasing number of devices and information, it is now becoming increasingly difficult to depend on IoT to manage things in the internet space with a similar degree of ease. As a result, cloud-based technologies have given preferences over the existing one and IoT has been replaced by the newly introduced Cloud of Things (CoT) paradigm. This paper intends to connect different smart city applications for the betterment of city life with the Cloud of Things (CoT). Our proposed smart city architecture is based on Cloud of Things, and the focus is also given to identify the existing as well as the forthcoming challenges for the concerned program of the government. By identifying the difficulties it is expected that the project will be materialized with a great success.
Structured Production System (extended abstract)
Venue: arXiv cs.AI 2017
Year: 2017

In this extended abstract, we propose Structured Production Systems (SPS), which extend traditional production systems with well-formed syntactic structures. Due to the richness of structures, structured production systems significantly enhance the expressive power as well as the flexibility of production systems, for instance, to handle uncertainty. We show that different rule application strategies can be reduced into the basic one by utilizing structures. Also, many fundamental approaches in computer science, including automata, grammar and logic, can be captured by structured production systems.
Replica Symmetry Breaking in Compressive Sensing
Venue: arXiv cs.IT 2017
Year: 2017

For noisy compressive sensing systems, the asymptotic distortion with respect to an arbitrary distortion function is determined when a general class of least-square based reconstruction schemes is employed. The sampling matrix is considered to belong to a large ensemble of random matrices including i.i.d. and projector matrices, and the source vector is assumed to be i.i.d. with a desired distribution. We take a statistical mechanical approach by representing the asymptotic distortion as a macroscopic parameter of a spin glass and employing the replica method for the large-system analysis. In contrast to earlier studies, we evaluate the general replica ansatz which includes the RS ansatz as well as RSB. The generality of the solution enables us to study the impact of symmetry breaking. Our numerical investigations depict that for the reconstruction scheme with the "zero-norm" penalty function, the RS fails to predict the asymptotic distortion for relatively large compression rates; however, the one-step RSB ansatz gives a valid prediction of the performance within a larger regime of compression rates.
Systematizing Decentralization and Privacy: Lessons from 15 Years of Research and Deployments
Venue: arXiv cs.CR 2017
Year: 2017

Decentralized systems are a subset of distributed systems where multiple authorities control different components and no authority is fully trusted by all. This implies that any component in a decentralized system is potentially adversarial. We revise fifteen years of research on decentralization and privacy, and provide an overview of key systems, as well as key insights for designers of future systems. We show that decentralized designs can enhance privacy, integrity, and availability but also require careful trade-offs in terms of system complexity, properties provided, and degree of decentralization. These trade-offs need to be understood and navigated by designers. We argue that a combination of insights from cryptography, distributed systems, and mechanism design, aligned with the development of adequate incentives, are necessary to build scalable and successful privacy-preserving decentralized systems.
Using a new parsimonious AHP methodology combined with the Choquet integral: An application for evaluating social housing initiatives
Venue: arXiv cs.AI 2017
Year: 2017

We propose a development of the Analytic Hierarchy Process (AHP) permitting to use the methodology also in cases of decision problems with a very large number of alternatives evaluated with respect to several criteria. While the application of the original AHP method involves many pairwise comparisons between alternatives and criteria, our proposal is composed of three steps: (i) direct evaluation of the alternatives at hand on the considered criteria, (ii) selection of some reference evaluations; (iii) application of the original AHP method to reference evaluations; (iv) revision of the direct evaluation on the basis of the prioritization supplied by AHP on reference evaluations. The new proposal has been tested and validated in an experiment conducted on a sample of university students. The new methodology has been therefore applied to a real world problem involving the evaluation of 21 Social Housing initiatives sited in the Piedmont region (Italy). To take into account interaction between criteria, the Choquet integral preference model has been considered within a Non Additive Robust Ordinal Regression approach.
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with $ n $ nodes and $ m $ edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We further demonstrate how to obtain both an algorithm with running time $ n^3 / 2^{Ω{(\sqrt{\log n})}} $ on general graphs and an algorithm with running time $ \tilde O (n) $ on constant treewidth graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest.
Idle Period Propagation in Message-Passing Applications
Venue: arXiv cs.DC 2017
Year: 2017

Idle periods on different processes of Message Passing applications are unavoidable. While the origin of idle periods on a single process is well understood as the effect of system and architectural random delays, yet it is unclear how these idle periods propagate from one process to another. It is important to understand idle period propagation in Message Passing applications as it allows application developers to design communication patterns avoiding idle period propagation and the consequent performance degradation in their applications. To understand idle period propagation, we introduce a methodology to trace idle periods when a process is waiting for data from a remote delayed process in MPI applications. We apply this technique in an MPI application that solves the heat equation to study idle period propagation on three different systems. We confirm that idle periods move between processes in the form of waves and that there are different stages in idle period propagation. Our methodology enables us to identify a self-synchronization phenomenon that occurs on two systems where some processes run slower than the other processes.
The MacGyver Test - A Framework for Evaluating Machine Resourcefulness and Creative Problem Solving
Venue: arXiv cs.AI 2017
Year: 2017

Current measures of machine intelligence are either difficult to evaluate or lack the ability to test a robot's problem-solving capacity in open worlds. We propose a novel evaluation framework based on the formal notion of MacGyver Test which provides a practical way for assessing the resilience and resourcefulness of artificial agents.
Predicting language diversity with complex network
Venue: arXiv cs.SI 2017
Year: 2017

Evolution and propagation of the world's languages is a complex phenomenon, driven, to a large extent, by social interactions. Multilingual society can be seen as a system of interacting agents, where the interaction leads to a modification of the language spoken by the individuals. Two people can reach the state of full linguistic compatibility due to the positive interactions, like transfer of loanwords. But, on the other hand, if they speak entirely different languages, they will separate from each other. These simple observations make the network science the most suitable framework to describe and analyze dynamics of language change. Although many mechanisms have been explained, we lack a qualitative description of the scaling behavior for different sizes of a population. Here we address the issue of the language diversity in societies of different sizes, and we show that local interactions are crucial to capture characteristics of the empirical data. We propose a model of social interactions, extending the idea from, that explains the growth of the language diversity with the size of a population of country or society. We argue that high clustering and network disintegration are the most important characteristics of models properly describing empirical data. Furthermore, we cancel the contradiction between previous models and the Solomon Islands case. Our results demonstrate the importance of the topology of the network, and the rewiring mechanism in the process of language change.