OpenRaiser/Intern-Atlas huggingface dataset:
Strategic play in stable marriage problem
Venue: arXiv cs.GT 2016
Year: 2016

The stable marriage problem, as addressed by Gale and Shapely [1] consists of providing a bipartite matching between n " boys " and n " girls "-each of whom have a totally ordered preference list over the other set-such that there exists no " boy " and no " girl " that would prefer each other over their partner in the matching. In this paper, we analyze the cases of strategic play by the " boys " in the game directly inspired by this problem. We provide an O(n^3) algorithm for determining a matching which is not necessarily stable in the Gale-Shapely sense, but it is coalition-stable, in that no player has a selfish interest to leave the resulting grand coalition to join any potential alternative one which might feasibly form, and is also man-optimal. Thus, under a realistic assumption set, no player has an interest to " destabilize " the matching, even though he theoretically could. The resulting matching is often better than the naïve Gale-Shapely one for some (not all) of the " boys " , being no worse for the rest. This matching is more realistic (stable) than the one produced by top-trading-cycles method, thus offering a qualitative improvement over the latter. Furthermore, we analyze the situation when players are allowed to make strategic threats (i.e. be willing to sacrifice their own outcome to hurt others), offer a relevant example to illustrate the benefits of this form of play, and ultimately provide an exponential time algorithm which tries to determine a good threat-making strategy. We then briefly examine a few other non-conventional possibilities a player has to affect his outcome. Most common variations to the game model are also described and analyzed with regard to applicability of the methods in this paper. Finally, a few examples of real-life problems which can be modeled and solved with the methods in this paper are presented.
Destination-aided Wireless Power Transfer in Energy-limited Cognitive Relay Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers an energy-limited cognitive relay network where a secondary transmitter (ST) assists to forward the traffic from a primary transmitter (PT) to a primary receiver (PR), in exchange for serving its own secondary receiver (SR) in the same frequency. The multiple-antenna ST is assumed to be energy-constrained and powered by both information flow from source (PT) and dedicated energy streams from destinations (PR and SR), which is called destination-aided wireless power transfer (DWPT) scheme. Then, the relay processing matrix, cognitive beamforming vector and power splitter are jointly de- signed to maximize the rate of secondary users under the energy causality constraint and the constraint that the demanded rate of primary users is satisfied. For the perfect channel information state (CSI) case, by adopting semi-definite relax (SDR) technique and Charnes-Cooper transformation, the global optimal solution is given. To reduce the complexity, matrix decomposition, zero forcing (ZF) scheme, and dual method are jointly employed to derive a suboptimal solution. For the imperfect CSI case, S- procedure is used to transform the worst-case robust problem into a tractable semi-definite program (SDP). Simulation results reveal that our proposed DWPT scheme is greatly preferred for both perfect and imperfect CSI cases when ST is close to PR/SR.
Temperature-Based Deep Boltzmann Machines
Venue: arXiv cs.LG 2016
Year: 2016

Deep learning techniques have been paramount in the last years, mainly due to their outstanding results in a number of applications, that range from speech recognition to face-based user identification. Despite other techniques employed for such purposes, Deep Boltzmann Machines are among the most used ones, which are composed of layers of Restricted Boltzmann Machines (RBMs) stacked on top of each other. In this work, we evaluate the concept of temperature in DBMs, which play a key role in Boltzmann-related distributions, but it has never been considered in this context up to date. Therefore, the main contribution of this paper is to take into account this information and to evaluate its influence in DBMs considering the task of binary image reconstruction. We expect this work can foster future research considering the usage of different temperatures during learning in DBMs.
Effect of Human Learning on the Transient Performance of Cloud-based Tiered Applications
Venue: arXiv cs.SE 2016
Year: 2016

Cloud based tiered applications are increasingly becoming popular, be it on phones or on desktops. End users of these applications range from novice to expert depending on how experienced they are in using them. With repeated usage (practice) of an application, a user's think time gradually decreases, known as learning phenomenon. In contrast to the popular notion of constant mean think time of users across all practice sessions, decrease in mean think time over practice sessions does occur due to learning. This decrease gives rise to a different system workload thereby affecting the application's short-term performance. However, such impact of learning on performance has never been accounted for. In this work we propose a model that accounts for human learning behavior in analyzing the transient (short-term) performance of a 3-tier cloud based application. Our approach is based on a closed queueing network model. We solve the model using discrete event simulation. In addition to the overall mean System Response Time (SRT), our model solution also generates the mean SRTs for various types (novice, intermediate, expert) of requests submitted by users at various levels of their expertise. We demonstrate that our model can be used to evaluate various what-if scenarios to decide the number of VMs we need for each tier-a VM configuration-that would meet the response time SLA. The results show that the lack of accountability of learning may lead to a selection of an inappropriate VM configuration. The results further show that the mean SRTs for various types of requests are better measures to consider in VM allocation process in comparison to the overall mean SRT.
Low-Rank Matrix Completion for Mobile Edge Caching in Fog-RAN via Riemannian Optimization
Venue: arXiv cs.IT 2016
Year: 2016

The upcoming big data era is likely to demand tremendous computation and storage resources for communications. By pushing computation and storage to network edges, fog radio access networks (Fog-RAN) can effectively increase network throughput and reduce transmission latency. Furthermore, we can exploit the benefits of cache enabled architecture in Fog-RAN to deliver contents with low latency. Radio access units (RAUs) need content delivery from fog servers through wireline links whereas multiple mobile devices acquire contents from RAUs wirelessly. This work proposes a unified low-rank matrix completion (LRMC) approach to solving the content delivery problem in both wireline and wireless parts of Fog-RAN. To attain a low caching latency, we present a high precision approach with Riemannian trust-region method to solve the challenging LRMC problem by exploiting the quotient manifold geometry of fixed-rank matrices. Numerical results show that the new approach has a faster convergence rate, is able to achieve optimal results, and outperforms other state-of-art algorithms.
Total variation reconstruction for compressive sensing using nonlocal Lagrangian multiplier
Venue: arXiv cs.CV 2016
Year: 2016

Total variation has proved its effectiveness in solving inverse problems for compressive sensing. Besides, the nonlocal means filter used as regularization preserves texture better for recovered images, but it is quite complex to implement. In this paper, based on existence of both noise and image information in the Lagrangian multiplier, we propose a simple method in term of implementation called nonlocal Lagrangian multiplier (NLLM) in order to reduce noise and boost useful image information. Experimental results show that the proposed NLLM is superior both in subjective and objective qualities of recovered image over other recovery algorithms.
Optimizing The Spatial Content Caching Distribution for Device-to-Device Communications
Venue: arXiv cs.IT 2016
Year: 2016

We study the optimal geographic content placement problem for device-to-device (D2D) networks in which the content popularity follows the Zipf law. We consider a D2D caching model where the locations of the D2D users (caches) are modeled by a Poisson point process (PPP) and have limited communication range and finite storage. Unlike most related work which assumes independent placement of content, and does not capture the locations of the users, we model the spatial properties of the network including spatial correlation in terms of the cached content. We propose two novel spatial correlation models, the exchangeable content model and a Matérn (MHC) content placement model, and analyze and optimize the \emph{hit probability}, which is the probability of a given D2D node finding a desired file at another node within its communication range. We contrast these results to the independent placement model, and show that exchangeable placement performs worse. On the other hand, MHC placement yields a higher cache hit probability than independent placement for small cache sizes.
Debugging of Markov Decision Processes (MDPs) Models
Venue: arXiv cs.SE 2016
Year: 2016

In model checking, a counterexample is considered as a valuable tool for debugging. In Probabilistic Model Checking (PMC), counterexample generation has a quantitative aspect. The counterexample in PMC is a set of paths in which a path formula holds, and their accumulative probability mass violates the probability threshold. However, understanding the counterexample is not an easy task. In this paper we address the task of counterexample analysis for Markov Decision Processes (MDPs). We propose an aided-diagnostic method for probabilistic counterexamples based on the notions of causality, responsibility and blame. Given a counterexample for a Probabilistic CTL (PCTL) formula that does not hold over an MDP model, this method guides the user to the most relevant parts of the model that led to the violation.
A Non-stochastic Learning Approach to Energy Efficient Mobility Management
Venue: arXiv cs.NI 2016
Year: 2016

Energy efficient mobility management is an important problem in modern wireless networks with heterogeneous cell sizes and increased nodes densities. We show that optimization-based mobility protocols cannot achieve long-term optimal energy consumption, particularly for ultra-dense networks (UDN). To address the complex dynamics of UDN, we propose a non-stochastic online-learning approach which does not make any assumption on the statistical behavior of the small base station (SBS) activities. In addition, we introduce handover cost to the overall energy consumption, which forces the resulting solution to explicitly minimize frequent handovers. The proposed Batched Randomization with Exponential Weighting (BREW) algorithm relies on batching to explore in bulk, and hence reduces unnecessary handovers. We prove that the regret of BREW is sublinear in time, thus guaranteeing its convergence to the optimal SBS selection. We further study the robustness of the BREW algorithm to delayed or missing feedback. Moreover, we study the setting where SBSs can be dynamically turned on and off. We prove that sublinear regret is impossible with respect to arbitrary SBS on/off, and then develop a novel learning strategy, called ranking expert (RE), that simultaneously takes into account the handover cost and the availability of SBS. To address the high complexity of RE, we propose a contextual ranking expert (CRE) algorithm that only assigns experts in a given context. Rigorous regret bounds are proved for both RE and CRE with respect to the best expert. Simulations show that not only do the proposed mobility algorithms greatly reduce the system energy consumption, but they are also robust to various dynamics which are common in practical ultra-dense wireless networks.
Human-Algorithm Interaction Biases in the Big Data Cycle: A Markov Chain Iterated Learning Framework
Venue: arXiv cs.LG 2016
Year: 2016

Early supervised machine learning algorithms have relied on reliable expert labels to build predictive models. However, the gates of data generation have recently been opened to a wider base of users who started participating increasingly with casual labeling, rating, annotating, etc. The increased online presence and participation of humans has led not only to a democratization of unchecked inputs to algorithms, but also to a wide democratization of the "consumption" of machine learning algorithms' outputs by general users. Hence, these algorithms, many of which are becoming essential building blocks of recommender systems and other information filters, started interacting with users at unprecedented rates. The result is machine learning algorithms that consume more and more data that is unchecked, or at the very least, not fitting conventional assumptions made by various machine learning algorithms. These include biased samples, biased labels, diverging training and testing sets, and cyclical interaction between algorithms, humans, information consumed by humans, and data consumed by algorithms. Yet, the continuous interaction between humans and algorithms is rarely taken into account in machine learning algorithm design and analysis. In this paper, we present a preliminary theoretical model and analysis of the mutual interaction between humans and algorithms, based on an iterated learning framework that is inspired from the study of human language evolution. We also define the concepts of human and algorithm blind spots and outline machine learning approaches to mend iterated bias through two novel notions: antidotes and reactive learning.
Using k-nearest neighbors to construct cancelable minutiae templates
Venue: arXiv cs.CV 2016
Year: 2016

Fingerprint is widely used in a variety of applications. Security measures have to be taken to protect the privacy of fingerprint data. Cancelable biometrics is proposed as an effective mechanism of using and protecting biometrics. In this paper we propose a new method of constructing cancelable fingerprint template by combining real template with synthetic template. Specifically, each user is given one synthetic minutia template generated with random number generator. Every minutia point from the real template is individually thrown into the synthetic template, from which its k-nearest neighbors are found. The verification template is constructed by combining an arbitrary set of the k-nearest neighbors. To prove the validity of the scheme, testing is carried out on three databases. The results show that the constructed templates satisfy the requirements of cancelable biometrics.
Machine Comprehension Using Match-LSTM and Answer Pointer
Venue: arXiv cs.CL 2016
Year: 2016

Machine comprehension of text is an important problem in natural language processing. A recently released dataset, the Stanford Question Answering Dataset (SQuAD), offers a large number of real questions and their answers created by humans through crowdsourcing. SQuAD provides a challenging testbed for evaluating machine comprehension algorithms, partly because compared with previous datasets, in SQuAD the answers do not come from a small set of candidate answers and they have variable lengths. We propose an end-to-end neural architecture for the task. The architecture is based on match-LSTM, a model we proposed previously for textual entailment, and Pointer Net, a sequence-to-sequence model proposed by Vinyals et al.(2015) to constrain the output tokens to be from the input sequences. We propose two ways of using Pointer Net for our task. Our experiments show that both of our two models substantially outperform the best results obtained by Rajpurkar et al.(2016) using logistic regression and manually crafted features.
A Novel Approach to Multimedia Ontology Engineering for Automated Reasoning over Audiovisual LOD Datasets
Venue: arXiv cs.AI 2016
Year: 2016

Multimedia reasoning, which is suitable for, among others, multimedia content analysis and high-level video scene interpretation, relies on the formal and comprehensive conceptualization of the represented knowledge domain. However, most multimedia ontologies are not exhaustive in terms of role definitions, and do not incorporate complex role inclusions and role interdependencies. In fact, most multimedia ontologies do not have a role box at all, and implement only a basic subset of the available logical constructors. Consequently, their application in multimedia reasoning is limited. To address the above issues, VidOnt, the very first multimedia ontology with SROIQ(D) expressivity and a DL-safe ruleset has been introduced for next-generation multimedia reasoning. In contrast to the common practice, the formal grounding has been set in one of the most expressive description logics, and the ontology validated with industry-leading reasoners, namely HermiT and FaCT++. This paper also presents best practices for developing multimedia ontologies, based on my ontology engineering approach.
Scholarly use of social media and altmetrics: a review of the literature
Venue: arXiv cs.DL 2016
Year: 2016

Social media has become integrated into the fabric of the scholarly communication system in fundamental ways: principally through scholarly use of social media platforms and the promotion of new indicators on the basis of interactions with these platforms. Research and scholarship in this area has accelerated since the coining and subsequent advocacy for altmetrics -- that is, research indicators based on social media activity. This review provides an extensive account of the state-of-the art in both scholarly use of social media and altmetrics. The review consists of two main parts: the first examines the use of social media in academia, examining the various functions these platforms have in the scholarly communication process and the factors that affect this use. The second part reviews empirical studies of altmetrics, discussing the various interpretations of altmetrics, data collection and methodological limitations, and differences according to platform. The review ends with a critical discussion of the implications of this transformation in the scholarly communication system.
brTPF: Bindings-Restricted Triple Pattern Fragments (Extended Preprint)
Venue: arXiv cs.DB 2016
Year: 2016

The Triple Pattern Fragment (TPF) interface is a recent proposal for reducing server load in Web-based approaches to execute SPARQL queries over public RDF datasets. The price for less overloaded servers is a higher client-side load and a substantial increase in network load (in terms of both the number of HTTP requests and data transfer). In this paper, we propose a slightly extended interface that allows clients to attach intermediate results to triple pattern requests. The response to such a request is expected to contain triples from the underlying dataset that do not only match the given triple pattern (as in the case of TPF), but that are guaranteed to contribute in a join with the given intermediate result. Our hypothesis is that a distributed query execution using this extended interface can reduce the network load (in comparison to a pure TPF-based query execution) without reducing the overall throughput of the client-server system significantly. Our main contribution in this paper is twofold: we empirically verify the hypothesis and provide an extensive experimental comparison of our proposal and TPF.
Construction of Convex Sets on Quadrilateral Ordered Tiles or Graphs with Propagation Neighborhood Operations. Dales, Concavity Structures. Application to Gray Image Analysis of Human-Readable Shapes
Venue: arXiv cs.CV 2016
Year: 2016

An effort has been made to show mathematicians some new ideas applied to image analysis. Gray images are presented as tilings. Based on topological properties of the tiling, a number of gray convex hulls: maximal, minimal, and oriented ones are constructed and some are proved. They are constructed with only one operation. Two tilings are used in the Constraint and Allowance types of operations. New type of concavity described: a dale. All operations are parallel, possible to realize clock-less. Convexities define what is the background. They are treated as separate gray objects. There are multiple relations among them and their descendants. Via that, topological size of concavities is proposed. Constructed with the same type of operations, Rays and Angles in a tiling define possible spatial relations. Notions like "strokes" are defined through concavities. Unusual effects on levelized gray objects are shown. It is illustrated how alphabet and complex hieroglyphs can be described through concavities and their relations. A hypothesis of living organisms image analysis is proposed. A number of examples with symbols and a human face are calculated with new Asynchwave C++ software library.
Analysis of Home Location Estimation with Iteration on Twitter Following Relationship
Venue: arXiv cs.SI 2016
Year: 2016

User's home locations are used by numerous social media applications, such as social media analysis. However, since the user's home location is not generally open to the public, many researchers have been attempting to develop a more accurate home location estimation. A social network that expresses relationships between users is used to estimate the users' home locations. The network-based home location estimation method with iteration, which propagates the estimated locations, is used to estimate more users' home locations. In this study, we analyze the function of network-based home location estimation with iteration while using the social network based on following relationships on Twitter. The results indicate that the function that selects the most frequent location among the friends' location has the best accuracy. Our analysis also shows that the 88% of users, who are in the social network based on following relationships, has at least one correct home location within one-hop (friends and friends of friends). According to this characteristic of the social network, we indicate that twice is sufficient for iteration.
Egocentric Meets Top-view
Venue: arXiv cs.CV 2016
Year: 2016

Thanks to the availability and increasing popularity of Egocentric cameras such as GoPro cameras, glasses, and etc. we have been provided with a plethora of videos captured from the first person perspective. Surveillance cameras and Unmanned Aerial Vehicles(also known as drones) also offer tremendous amount of videos, mostly with top-down or oblique view-point. Egocentric vision and top-view surveillance videos have been studied extensively in the past in the computer vision community. However, the relationship between the two has yet to be explored thoroughly. In this effort, we attempt to explore this relationship by approaching two questions. First, having a set of egocentric videos and a top-view video, can we verify if the top-view video contains all, or some of the egocentric viewers present in the egocentric set? And second, can we identify the egocentric viewers in the content of the top-view video? In other words, can we find the cameramen in the surveillance videos? These problems can become more challenging when the videos are not time-synchronous. Thus we formalize the problem in a way which handles and also estimates the unknown relative time-delays between the egocentric videos and the top-view video. We formulate the problem as a spectral graph matching instance, and jointly seek the optimal assignments and relative time-delays of the videos. As a result, we spatiotemporally localize the egocentric observers in the top-view video. We model each view (egocentric or top) using a graph, and compute the assignment and time-delays in an iterative-alternative fashion.