OpenRaiser/Intern-Atlas huggingface dataset:
Locality-based Network Creation Games
Venue: arXiv cs.GT 2016
Year: 2016

Network creation games have been extensively studied, both from economists and computer scientists, due to their versatility in modeling individual-based community formation processes, which in turn are the theoretical counterpart of several economics, social, and computational applications on the Internet. In their several variants, these games model the tension of a player between her two antagonistic goals: to be as close as possible to the other players, and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a \emph{common and complete} information about the ongoing network, which is quite unrealistic in practice. In this paper, we consider a more compelling scenario in which players have only limited information about the network they are embedded in. More precisely, we explore the game-theoretic and computational implications of assuming that players have a complete knowledge of the network structure only up to a given radius $k$, which is one of the most qualified \emph{local-knowledge models} used in distributed computing. To this respect, we define a suitable equilibrium concept, and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of $k$, and for the two classic variants of the game, namely those in which a player's cost --- besides the activation cost of the owned links --- depends on the maximum/sum of all the distances to the other nodes in the network, respectively. These bounds are finally assessed through an extensive set of experiments.
Rate-Distortion Dimension of Stochastic Processes
Venue: arXiv cs.IT 2016
Year: 2016

The rate-distortion dimension (RDD) of an analog stationary process is studied as a measure of complexity that captures the amount of information contained in the process. It is shown that the RDD of a process, defined as two times the asymptotic ratio of its rate-distortion function $R(D)$ to $\log {1\over D}$ as the distortion $D$ approaches zero, is equal to its information dimension (ID). This generalizes an earlier result by Kawabata and Dembo and provides an operational approach to evaluate the ID of a process, which previously was shown to be closely related to the effective dimension of the underlying process and also to the fundamental limits of compressed sensing. The relation between RDD and ID is illustrated for a piecewise constant process.
Social Politics: Agenda Setting and Political Communication on Social Media
Venue: arXiv cs.SI 2016
Year: 2016

Social media play an increasingly important role in political communication. Various studies investigated how individuals adopt social media for political discussion, to share their views about politics and policy, or to mobilize and protest against social issues. Yet, little attention has been devoted to the main actors of political discussions: the politicians. In this paper, we explore the topics of discussion of U.S. President Obama and the 50 U.S. State Governors using Twitter data and agenda-setting theory as a tool to describe the patterns of daily political discussion, uncovering the main topics of attention and interest of these actors. We examine over one hundred thousand tweets produced by these politicians and identify seven macro-topics of conversation, finding that Twitter represents a particularly appealing vehicle of conversation for American opposition politicians. We highlight the main motifs of political conversation of the two parties, discovering that Republican and Democrat Governors are more or less similarly active on Twitter but exhibit different styles of communication. Finally, by reconstructing the networks of occurrences of Governors' hashtags and keywords related to political issues, we observe that Republicans form a tight core, with a stronger shared agenda on many issues of discussion.
Unsupervised Learning from Continuous Video in a Scalable Predictive Recurrent Network
Venue: arXiv cs.CV 2016
Year: 2016

Understanding visual reality involves acquiring common-sense knowledge about countless regularities in the visual world, e.g., how illumination alters the appearance of objects in a scene, and how motion changes their apparent spatial relationship. These regularities are hard to label for training supervised machine learning algorithms; consequently, algorithms need to learn these regularities from the real world in an unsupervised way. We present a novel network meta-architecture that can learn world dynamics from raw, continuous video. The components of this network can be implemented using any algorithm that possesses three key capabilities: prediction of a signal over time, reduction of signal dimensionality (compression), and the ability to use supplementary contextual information to inform the prediction. The presented architecture is highly-parallelized and scalable, and is implemented using localized connectivity, processing, and learning. We demonstrate an implementation of this architecture where the components are built from multi-layer perceptrons. We apply the implementation to create a system capable of stable and robust visual tracking of objects as seen by a moving camera. Results show performance on par with or exceeding state-of-the-art tracking algorithms. The tracker can be trained in either fully supervised or unsupervised-then-briefly-supervised regimes. Success of the briefly-supervised regime suggests that the unsupervised portion of the model extracts useful information about visual reality. The results suggest a new class of AI algorithms that uniquely combine prediction and scalability in a way that makes them suitable for learning from and --- and eventually acting within --- the real world.
Processing Natural Language About Ongoing Actions
Venue: arXiv cs.AI 2016
Year: 2016

Actions may not proceed as planned; they may be interrupted, resumed or overridden. This is a challenge to handle in a natural language understanding system. We describe extensions to an existing implementation for the control of autonomous systems by natural language, to enable such systems to handle incoming language requests regarding actions. Language Communication with Autonomous Systems (LCAS) has been extended with support for X-nets, parameterized executable schemas representing actions. X-nets enable the system to control actions at a desired level of granularity, while providing a mechanism for language requests to be processed asynchronously. Standard semantics supported include requests to stop, continue, or override the existing action. The specific domain demonstrated is the control of motion of a simulated robot, but the approach is general, and could be applied to other domains.
Satisfiability Checking and Symbolic Computation
Venue: arXiv cs.SC 2016
Year: 2016

Symbolic Computation and Satisfiability Checking are viewed as individual research areas, but they share common interests in the development, implementation and application of decision procedures for arithmetic theories. Despite these commonalities, the two communities are currently only weakly connected. We introduce a new project SC-square to build a joint community in this area, supported by a newly accepted EU (H2020-FETOPEN-CSA) project of the same name. We aim to strengthen the connection between these communities by creating common platforms, initiating interaction and exchange, identifying common challenges, and developing a common roadmap. This abstract and accompanying poster describes the motivation and aims for the project, and reports on the first activities.
Neural Sentence Ordering
Venue: arXiv cs.CL 2016
Year: 2016

Sentence ordering is a general and critical task for natural language generation applications. Previous works have focused on improving its performance in an external, downstream task, such as multi-document summarization. Given its importance, we propose to study it as an isolated task. We collect a large corpus of academic texts, and derive a data driven approach to learn pairwise ordering of sentences, and validate the efficacy with extensive experiments. Source codes and dataset of this paper will be made publicly available.
Combined Classifiers for Invariant Face Recognition
Venue: arXiv cs.CV 2016
Year: 2016

No single classifier can alone solve the complex problem of face recognition. Researchers found that combining some base classifiers usually enhances their recognition rate. The weaknesses of the base classifiers are reflected on the resulting combined system. In this work, a system for combining unstable, low performance classifiers is proposed. The system is applied to face images of 392 persons. The system shows remarkable stability and high recognition rate using a reduced number of parameters. The system illustrates the possibility of designing a combined system that benefits from the strengths of its base classifiers while avoiding many of their weaknesses.
Academic Presenter: a New Storytelling Presentation Software for Academic Purposes
Venue: arXiv cs.HC 2016
Year: 2016

From the dawn of civilization, people have used folktales and stories to share information and knowledge. After the invention of printing in the 15th century, technology provided helpful yet complicated utilities to exchange ideas. In the present computerized world, the art of storytelling is becoming more influential through the unprecedented multimedia capabilities of computers. In this article, we introduce a state-of-the-art presentation software by which academicians can present nonlinear topics efficiently and sharpen their storytelling skills. We show how the proposed software can improve the scientific presentation style. We conducted a survey to measure the attractiveness of proposed utility among other alternatives. Results show that academicians prefer the proposed platform to others.
Fronthauling for 5G LTE-U Ultra Dense Cloud Small Cell Networks
Venue: arXiv cs.IT 2016
Year: 2016

Ultra dense cloud small cell network (UDCSNet), which combines cloud computing and massive deployment of small cells, is a promising technology for the fifth-generation (5G) LTE-U mobile communications because it can accommodate the anticipated explosive growth of mobile users' data traffic. As a result, fronthauling becomes a challenging problem in 5G LTE-U UDCSNet. In this article, we present an overview of the challenges and requirements of the fronthaul technology in 5G \mbox{LTE-U} UDCSNets. We survey the advantages and challenges for various candidate fronthaul technologies such as optical fiber, millimeter-wave based unlicensed spectrum, Wi-Fi based unlicensed spectrum, sub 6GHz based licensed spectrum, and free-space optical based unlicensed spectrum.
Analytical Modeling of IEEE 802.11 Type CSMA/CA Networks with Short Term Unfairness
Venue: arXiv cs.NI 2016
Year: 2016

We consider single-hop topologies with saturated transmitting nodes, using IEEE~802.11 DCF for medium access. However, unlike the conventional WiFi, we study systems where one or more of the protocol parameters are different from the standard, and/or where the propagation delays among the nodes are not negligible compared to the duration of a backoff slot. We observe that for several classes of protocol parameters, and for large propagation delays, such systems exhibit a certain performance anomaly known as short term unfairness, which may lead to severe performance degradation. The standard fixed point analysis technique (and its simple extensions) do not predict the system behavior well in such cases; a mean field model based asymptotic approach also is not adequate to predict the performance for networks of practical sizes in such cases. We provide a detailed stochastic model that accurately captures the system evolution. Since an exact analysis of this model is computationally intractable, we develop a novel approximate, but accurate, analysis that uses a parsimonious state representation for computational tractability. Apart from providing insights into the system behavior, the analytical method is also able to quantify the extent of short term unfairness in the system, and can therefore be used for tuning the protocol parameters to achieve desired throughput and fairness objectives.
Impact of Physical Activity on Sleep:A Deep Learning Based Exploration
Venue: arXiv cs.LG 2016
Year: 2016

The importance of sleep is paramount for maintaining physical, emotional and mental wellbeing. Though the relationship between sleep and physical activity is known to be important, it is not yet fully understood. The explosion in popularity of actigraphy and wearable devices, provides a unique opportunity to understand this relationship. Leveraging this information source requires new tools to be developed to facilitate data-driven research for sleep and activity patient-recommendations. In this paper we explore the use of deep learning to build sleep quality prediction models based on actigraphy data. We first use deep learning as a pure model building device by performing human activity recognition (HAR) on raw sensor data, and using deep learning to build sleep prediction models. We compare the deep learning models with those build using classical approaches, i.e. logistic regression, support vector machines, random forest and adaboost. Secondly, we employ the advantage of deep learning with its ability to handle high dimensional datasets. We explore several deep learning models on the raw wearable sensor output without performing HAR or any other feature extraction. Our results show that using a convolutional neural network on the raw wearables output improves the predictive value of sleep quality from physical activity, by an additional 8% compared to state-of-the-art non-deep learning approaches, which itself shows a 15% improvement over current practice. Moreover, utilizing deep learning on raw data eliminates the need for data pre-processing and simplifies the overall workflow to analyze actigraphy data for sleep and physical activity research.
Large-Scale Video Search with Efficient Temporal Voting Structure
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we propose a fast content-based video querying system for large-scale video search. The proposed system is distinguished from similar works with two major contributions. First contribution is superiority of joint usage of repeated content representation and efficient hashing mechanisms. Repeated content representation is utilized with a simple yet robust feature, which is based on edge energy of frames. Each of the representation is converted into hash code with Hamming Embedding method for further queries. Second contribution is novel queue-based voting scheme that leads to modest memory requirements with gradual memory allocation capability, contrary to complete brute-force temporal voting schemes. This aspect enables us to make queries on large video databases conveniently, even on commodity computers with limited memory capacity. Our results show that the system can respond to video queries on a large video database with fast query times, high recall rate and very low memory and disk requirements.
A Sugiyama-like decoding algorithm for convolutional codes
Venue: arXiv cs.IT 2016
Year: 2016

We propose a decoding algorithm for a class of convolutional codes called skew BCH convolutional codes. These are convolutional codes of designed Hamming distance endowed with a cyclic structure yielding a left ideal of a non-commutative ring (a quotient of a skew polynomial ring). In this setting, right and left division algorithms exist, so our algorithm follows the guidelines of the Sugiyama's procedure for finding the error locator and error evaluator polynomials for BCH block codes.
Tracking with multi-level features
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel formulation of the multiple object tracking problem which integrates low and mid-level features. In particular, we formulate the tracking problem as a quadratic program coupling detections and dense point trajectories. Due to the computational complexity of the initial QP, we propose an approximation by two auxiliary problems, a temporal and spatial association, where the temporal subproblem can be efficiently solved by a linear program and the spatial association by a clustering algorithm. The objective function of the QP is used in order to find the optimal number of clusters, where each cluster ideally represents one person. Evaluation is provided for multiple scenarios, showing the superiority of our method with respect to classic tracking-by-detection methods and also other methods that greedily integrate low-level features.
Meta-Prod2Vec - Product Embeddings Using Side-Information for Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

We propose Meta-Prod2vec, a novel method to compute item similarities for recommendation that leverages existing item metadata. Such scenarios are frequently encountered in applications such as content recommendation, ad targeting and web search. Our method leverages past user interactions with items and their attributes to compute low-dimensional embeddings of items. Specifically, the item metadata is in- jected into the model as side information to regularize the item embeddings. We show that the new item representa- tions lead to better performance on recommendation tasks on an open music dataset.
Coherent Product Superposition for Downlink Multiuser MIMO
Venue: arXiv cs.IT 2016
Year: 2016

In a two-user broadcast channel where one user has full CSIR and the other has none, a recent result showed that TDMA is strictly suboptimal and a product superposition requiring non-coherent signaling achieves DoF gains under many antenna configurations. This work introduces product superposition in the domain of coherent signaling with pilots, demonstrates the advantages of product superposition in low-SNR as well as high-SNR, and establishes DoF gains in a wider set of receiver antenna configurations. Two classes of decoders, with and without interference cancellation, are studied. Achievable rates are established by analysis and illustrated by simulations.
Identifying Depression on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

Social media has recently emerged as a premier method to disseminate information online. Through these online networks, tens of millions of individuals communicate their thoughts, personal experiences, and social ideals. We therefore explore the potential of social media to predict, even prior to onset, Major Depressive Disorder (MDD) in online personas. We employ a crowdsourced method to compile a list of Twitter users who profess to being diagnosed with depression. Using up to a year of prior social media postings, we utilize a Bag of Words approach to quantify each tweet. Lastly, we leverage several statistical classifiers to provide estimates to the risk of depression. Our work posits a new methodology for constructing our classifier by treating social as a text-classification problem, rather than a behavioral one on social media platforms. By using a corpus of 2.5M tweets, we achieved an 81% accuracy rate in classification, with a precision score of .86. We believe that this method may be helpful in developing tools that estimate the risk of an individual being depressed, can be employed by physicians, concerned individuals, and healthcare agencies to aid in diagnosis, even possibly enabling those suffering from depression to be more proactive about recovering from their mental health.
Much Ado About Time: Exhaustive Annotation of Temporal Data
Venue: arXiv cs.HC 2016
Year: 2016

Large-scale annotated datasets allow AI systems to learn from and build upon the knowledge of the crowd. Many crowdsourcing techniques have been developed for collecting image annotations. These techniques often implicitly rely on the fact that a new input image takes a negligible amount of time to perceive. In contrast, we investigate and determine the most cost-effective way of obtaining high-quality multi-label annotations for temporal data such as videos. Watching even a short 30-second video clip requires a significant time investment from a crowd worker; thus, requesting multiple annotations following a single viewing is an important cost-saving strategy. But how many questions should we ask per video? We conclude that the optimal strategy is to ask as many questions as possible in a HIT (up to 52 binary questions after watching a 30-second video clip in our experiments). We demonstrate that while workers may not correctly answer all questions, the cost-benefit analysis nevertheless favors consensus from multiple such cheap-yet-imperfect iterations over more complex alternatives. When compared with a one-question-per-video baseline, our method is able to achieve a 10% improvement in recall 76.7% ours versus 66.7% baseline) at comparable precision (83.8% ours versus 83.0% baseline) in about half the annotation time (3.8 minutes ours compared to 7.1 minutes baseline). We demonstrate the effectiveness of our method by collecting multi-label annotations of 157 human activities on 1,815 videos.
Efficient Multi-Agent Global Navigation Using Interpolating Bridges
Venue: arXiv cs.RO 2016
Year: 2016

We present a novel approach for collision-free global navigation for continuous-time multi-agent systems with general linear dynamics. Our approach is general and can be used to perform collision-free navigation in 2D and 3D workspaces with narrow passages and crowded regions. As part of pre-computation, we compute multiple bridges in the narrow or tight regions in the workspace using kinodynamic RRT algorithms. Our bridge has certain geometric characteristics, that en- able us to calculate a collision-free trajectory for each agent using simple interpolation at runtime. Moreover, we combine interpolated bridge trajectories with local multi-agent navigation algorithms to compute global collision-free paths for each agent. The overall approach combines the performance benefits of coupled multi-agent algorithms with the pre- computed trajectories of the bridges to handle challenging scenarios. In practice, our approach can handle tens to hundreds of agents in real-time on a single CPU core in 2D and 3D workspaces.
Collision-Free Poisson Motion Planning in Ultra High-Dimensional Molecular Conformation Spaces
Venue: arXiv cs.RO 2016
Year: 2016

The function of protein, RNA, and DNA is modulated by fast, dynamic exchanges between three-dimensional conformations. Conformational sampling of biomolecules with exact and nullspace inverse kinematics, using rotatable bonds as revolute joints and non-covalent interactions as holonomic constraints, can accurately characterize these native ensembles. However, sampling biomolecules remains challenging owing to their ultra-high dimensional configuration spaces, and the requirement to avoid (self-) collisions, which results in low acceptance rates. Here, we present two novel mechanisms to overcome these limitations. First, we introduced temporary constraints between near-colliding links. The resulting constraint varieties instantaneously redirect the search for collision-free conformations, and couple motions between distant parts of the linkage. Second, we adapted a randomized Poisson-disk motion planner, which prevents local oversampling and widens the search, to ultra-high dimensions. We evaluated our algorithm on several model systems. Our contributions apply to general high-dimensional motion planning problems in static and dynamic environments with obstacles.