OpenRaiser/Intern-Atlas huggingface dataset:
Human Social Interaction Modeling Using Temporal Deep Networks
Venue: arXiv cs.CY 2015
Year: 2015

We present a novel approach to computational modeling of social interactions based on modeling of essential social interaction predicates (ESIPs) such as joint attention and entrainment. Based on sound social psychological theory and methodology, we collect a new "Tower Game" dataset consisting of audio-visual capture of dyadic interactions labeled with the ESIPs. We expect this dataset to provide a new avenue for research in computational social interaction modeling. We propose a novel joint Discriminative Conditional Restricted Boltzmann Machine (DCRBM) model that combines a discriminative component with the generative power of CRBMs. Such a combination enables us to uncover actionable constituents of the ESIPs in two steps. First, we train the DCRBM model on the labeled data and get accurate (76\%-49\% across various ESIPs) detection of the predicates. Second, we exploit the generative capability of DCRBMs to activate the trained model so as to generate the lower-level data corresponding to the specific ESIP that closely matches the actual training data (with mean square error 0.01-0.1 for generating 100 frames). We are thus able to decompose the ESIPs into their constituent actionable behaviors. Such a purely computational determination of how to establish an ESIP such as engagement is unprecedented.
Optimal Morse functions and $H(\mathcal{M}^2,\mathbb{A})$ in $\tilde{O}(N)$ time
Venue: arXiv cs.CG 2015
Year: 2015

In this work, we design a nearly linear time discrete Morse theory based algorithm for computing homology groups of 2-manifolds, thereby establishing the fact that computing homology groups of 2-manifolds is remarkably easy. Unlike previous algorithms of similar flavor, our method works with coefficients from arbitrary abelian groups. Another advantage of our method lies in the fact that our algorithm actually elucidates the topological reason that makes computation on 2-manifolds easy. This is made possible owing to a new simple homotopy based construct that is referred to as \emph{expansion frames}. To being with we obtain an optimal discrete gradient vector field using expansion frames. This is followed by a pseudo-linear time dynamic programming based computation of discrete Morse boundary operator. The efficient design of optimal gradient vector field followed by fast computation of boundary operator affords us near linearity in computation of homology groups. Moreover, we define a new criterion for nearly optimal Morse functions called pseudo-optimality. A Morse function is pseudo-optimal if we can obtain an optimal Morse function from it, simply by means of critical cell cancellations. Using expansion frames, we establish the surprising fact that an arbitrary discrete Morse function on 2-manifolds is pseudo-optimal.
Performance Evaluation of Vision-Based Algorithms for MAVs
Venue: arXiv cs.CV 2015
Year: 2015

An important focus of current research in the field of Micro Aerial Vehicles (MAVs) is to increase the safety of their operation in general unstructured environments. Especially indoors, where GPS cannot be used for localization, reliable algorithms for localization and mapping of the environment are necessary in order to keep an MAV airborne safely. In this paper, we compare vision-based real-time capable methods for localization and mapping and point out their strengths and weaknesses. Additionally, we describe algorithms for state estimation, control and navigation, which use the localization and mapping results of our vision-based algorithms as input.
Quasi-cyclic Codes of Index 1.5
Venue: arXiv cs.IT 2015
Year: 2015

We introduce quasi-cyclic codes of index 1.5, construct such codes in terms of polynomials and matrices; and prove that the quasi-cyclic codes of index 1.5 are asymptotically good.
Ability to Count Is Worth $Θ(Δ)$ Rounds
Venue: arXiv cs.DC 2015
Year: 2015

Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different models of distributed computing - one of which is the port-numbering model - and provided a complete classification of their computational power relative to each other. However, one of their simulation results involves an additive overhead of $2Δ-2$ communication rounds, and it was not clear, if this is actually optimal. In this paper we give a positive answer: there is a matching linear-in-$Δ$ lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds.
Picking vs. Guessing Secrets: A Game-Theoretic Analysis (Technical Report)
Venue: arXiv cs.GT 2015
Year: 2015

Choosing a hard-to-guess secret is a prerequisite in many security applications. Whether it is a password for user authentication or a secret key for a cryptographic primitive, picking it requires the user to trade-off usability costs with resistance against an adversary: a simple password is easier to remember but is also easier to guess; likewise, a shorter cryptographic key may require fewer computational and storage resources but it is also easier to attack. A fundamental question is how one can optimally resolve this trade-off. A big challenge is the fact that an adversary can also utilize the knowledge of such usability vs. security trade-offs to strengthen its attack. In this paper, we propose a game-theoretic framework for analyzing the optimal trade-offs in the face of strategic adversaries. We consider two types of adversaries: those limited in their number of tries, and those that are ruled by the cost of making individual guesses. For each type, we derive the mutually-optimal decisions as Nash Equilibria, the strategically pessimistic decisions as maximin, and optimal commitments as Strong Stackelberg Equilibria of the game. We establish that when the adversaries are faced with a capped number of guesses, the user's optimal trade-off is a uniform randomization over a subset of the secret domain. On the other hand, when the attacker strategy is ruled by the cost of making individual guesses, Nash Equilibria may completely fail to provide the user with any level of security, signifying the crucial role of credible commitment for such cases. We illustrate our results using numerical examples based on real-world samples and discuss some policy implications of our work.
Solutions to Integrals Involving the Marcum Q-Function and Applications
Venue: arXiv cs.IT 2015
Year: 2015

Novel analytic solutions are derived for integrals that involve the generalized Marcum Q-function, exponential functions and arbitrary powers. Simple closed-form expressions are also derived for the specific cases of the generic integrals. The offered expressions are both convenient and versatile, which is particularly useful in applications relating to natural sciences and engineering, including wireless cpmmunications and signal processing. To this end, they are employed in the derivation of the channel capacity for fixed rate and channel inversion in the case of correlated multipath fading and switched diversity.
Bounded-Distortion Metric Learning
Venue: arXiv cs.LG 2015
Year: 2015

Metric learning aims to embed one metric space into another to benefit tasks like classification and clustering. Although a greatly distorted metric space has a high degree of freedom to fit training data, it is prone to overfitting and numerical inaccuracy. This paper presents {\it bounded-distortion metric learning} (BDML), a new metric learning framework which amounts to finding an optimal Mahalanobis metric space with a bounded-distortion constraint. An efficient solver based on the multiplicative weights update method is proposed. Moreover, we generalize BDML to pseudo-metric learning and devise the semidefinite relaxation and a randomized algorithm to approximately solve it. We further provide theoretical analysis to show that distortion is a key ingredient for stability and generalization ability of our BDML algorithm. Extensive experiments on several benchmark datasets yield promising results.
UbiBreathe: A Ubiquitous non-Invasive WiFi-based Breathing Estimator
Venue: arXiv cs.OH 2015
Year: 2015

Monitoring breathing rates and patterns helps in the diagnosis and potential avoidance of various health problems. Current solutions for respiratory monitoring, however, are usually invasive and/or limited to medical facilities. In this paper, we propose a novel respiratory monitoring system, UbiBreathe, based on ubiquitous off-the-shelf WiFi-enabled devices. Our experiments show that the received signal strength (RSS) at a WiFi-enabled device held on a person's chest is affected by the breathing process. This effect extends to scenarios when the person is situated on the line-of-sight (LOS) between the access point and the device, even without holding it. UbiBreathe leverages these changes in the WiFi RSS patterns to enable ubiquitous non-invasive respiratory rate estimation, as well as apnea detection. We propose the full architecture and design for UbiBreathe, incorporating various modules that help reliably extract the hidden breathing signal from a noisy WiFi RSS. The system handles various challenges such as noise elimination, interfering humans, sudden user movements, as well as detecting abnormal breathing situations. Our implementation of UbiBreathe using off-the-shelf devices in a wide range of environmental conditions shows that it can estimate different breathing rates with less than 1 breaths per minute (bpm) error. In addition, UbiBreathe can detect apnea with more than 96% accuracy in both the device-on-chest and hands-free scenarios. This highlights its suitability for a new class of anywhere respiratory monitoring.
The Computational Universality of Metabolic Computing
Venue: arXiv cs.ET 2015
Year: 2015

System and synthetic biology are rapidly evolving systems, but both lack tools such as those used in engineering environments to shift the their focus from the design of parts (details) to the design of systems (behaviors); to aggravate, there are insufficient theoretical justifications on the computational limits of biological systems. To diminish these deficiencies, we present theoretical results over the Turing-equivalence of metabolic systems, defines rules for translations of algorithms into metabolic P systems and presents a software tool to assist the task in an automatic way.
Fast Rhetorical Structure Theory Discourse Parsing
Venue: arXiv cs.CL 2015
Year: 2015

In recent years, There has been a variety of research on discourse parsing, particularly RST discourse parsing. Most of the recent work on RST parsing has focused on implementing new types of features or learning algorithms in order to improve accuracy, with relatively little focus on efficiency, robustness, or practical use. Also, most implementations are not widely available. Here, we describe an RST segmentation and parsing system that adapts models and feature sets from various previous work, as described below. Its accuracy is near state-of-the-art, and it was developed to be fast, robust, and practical. For example, it can process short documents such as news articles or essays in less than a second.
Probabilistic Belief Embedding for Knowledge Base Completion
Venue: arXiv cs.AI 2015
Year: 2015

This paper contributes a novel embedding model which measures the probability of each belief $\langle h,r,t,m\rangle$ in a large-scale knowledge repository via simultaneously learning distributed representations for entities ($h$ and $t$), relations ($r$), and the words in relation mentions ($m$). It facilitates knowledge completion by means of simple vector operations to discover new beliefs. Given an imperfect belief, we can not only infer the missing entities, predict the unknown relations, but also tell the plausibility of the belief, just leveraging the learnt embeddings of remaining evidences. To demonstrate the scalability and the effectiveness of our model, we conduct experiments on several large-scale repositories which contain millions of beliefs from WordNet, Freebase and NELL, and compare it with other cutting-edge approaches via competing the performances assessed by the tasks of entity inference, relation prediction and triplet classification with respective metrics. Extensive experimental results show that the proposed model outperforms the state-of-the-arts with significant improvements.
Deep Learning for Semantic Part Segmentation with High-Level Guidance
Venue: arXiv cs.CV 2015
Year: 2015

In this work we address the task of segmenting an object into its parts, or semantic part segmentation. We start by adapting a state-of-the-art semantic segmentation system to this task, and show that a combination of a fully-convolutional Deep CNN system coupled with Dense CRF labelling provides excellent results for a broad range of object categories. Still, this approach remains agnostic to high-level constraints between object parts. We introduce such prior information by means of the Restricted Boltzmann Machine, adapted to our task and train our model in an discriminative fashion, as a hidden CRF, demonstrating that prior information can yield additional improvements. We also investigate the performance of our approach ``in the wild'', without information concerning the objects' bounding boxes, using an object detector to guide a multi-scale segmentation scheme. We evaluate the performance of our approach on the Penn-Fudan and LFW datasets for the tasks of pedestrian parsing and face labelling respectively. We show superior performance with respect to competitive methods that have been extensively engineered on these benchmarks, as well as realistic qualitative results on part segmentation, even for occluded or deformable objects. We also provide quantitative and extensive qualitative results on three classes from the PASCAL Parts dataset. Finally, we show that our multi-scale segmentation scheme can boost accuracy, recovering segmentations for finer parts.
Automating change of representation for proofs in discrete mathematics
Venue: arXiv cs.AI 2015
Year: 2015

Representation determines how we can reason about a specific problem. Sometimes one representation helps us find a proof more easily than others. Most current automated reasoning tools focus on reasoning within one representation. There is, therefore, a need for the development of better tools to mechanise and automate formal and logically sound changes of representation. In this paper we look at examples of representational transformations in discrete mathematics, and show how we have used Isabelle's Transfer tool to automate the use of these transformations in proofs. We give a brief overview of a general theory of transformations that we consider appropriate for thinking about the matter, and we explain how it relates to the Transfer package. We show our progress towards developing a general tactic that incorporates the automatic search for representation within the proving process.
A Two-Layer Local Constrained Sparse Coding Method for Fine-Grained Visual Categorization
Venue: arXiv cs.CV 2015
Year: 2015

Fine-grained categories are more difficulty distinguished than generic categories due to the similarity of inter-class and the diversity of intra-class. Therefore, the fine-grained visual categorization (FGVC) is considered as one of challenge problems in computer vision recently. A new feature learning framework, which is based on a two-layer local constrained sparse coding architecture, is proposed in this paper. The two-layer architecture is introduced for learning intermediate-level features, and the local constrained term is applied to guarantee the local smooth of coding coefficients. For extracting more discriminative information, local orientation histograms are the input of sparse coding instead of raw pixels. Moreover, a quick dictionary updating process is derived to further improve the training speed. Two experimental results show that our method achieves 85.29% accuracy on the Oxford 102 flowers dataset and 67.8% accuracy on the CUB-200-2011 bird dataset, and the performance of our framework is highly competitive with existing literatures.
Inter organizational System Management for integrated service delivery: an Enterprise Architecture Perspective
Venue: arXiv cs.SE 2015
Year: 2015

Service sharing is a prominent operating model to support business. Many large inter-organizational networks have implemented some form of value added integrated services in order to reach efficiency and to reduce costs sustainably. Coupling Service orientation with enterprise architecture paradigm is very important at improving organizational performance through business process optimization. Indeed, enterprise architecture management is increasingly discussed because of information system role as part of achieving the strategic direction of value creation and contribution to economic growth. Also, system architecture promotes synergy and business efficiency for inter-organizational collaboration. For this purpose, this work proposes a review of service oriented enterprise architecture. This review, enumerates several integrative and collaborative frameworks for integrated service delivery.
Improving neural networks with bunches of neurons modeled by Kumaraswamy units: Preliminary study
Venue: arXiv cs.LG 2015
Year: 2015

Deep neural networks have recently achieved state-of-the-art results in many machine learning problems, e.g., speech recognition or object recognition. Hitherto, work on rectified linear units (ReLU) provides empirical and theoretical evidence on performance increase of neural networks comparing to typically used sigmoid activation function. In this paper, we investigate a new manner of improving neural networks by introducing a bunch of copies of the same neuron modeled by the generalized Kumaraswamy distribution. As a result, we propose novel non-linear activation function which we refer to as Kumaraswamy unit which is closely related to ReLU. In the experimental study with MNIST image corpora we evaluate the Kumaraswamy unit applied to single-layer (shallow) neural network and report a significant drop in test classification error and test cross-entropy in comparison to sigmoid unit, ReLU and Noisy ReLU.
Linear Time Approximation Schemes for Geometric Maximum Coverage
Venue: arXiv cs.CG 2015
Year: 2015

We study approximation algorithms for the following geometric version of the maximum coverage problem: Let P be a set of n weighted points in the plane. We want to place m a * b rectangles such that the sum of the weights of the points in P covered by these rectangles is maximized.For any fixed > 0, we present efficient approximation schemes that can find (1-ε)-approximation to the optimal solution.In particular, for m = 1, our algorithm runs in linear time O(n log( 1/ε)), improving over the previous result. For m > 1, we present an algorithm that runs in O(n/εlog(1/ε)+m(1/ε)^(O(min(sqrt(m),1/ε))) time.
Cell-Free Massive MIMO: Uniformly Great Service For Everyone
Venue: arXiv cs.IT 2015
Year: 2015

We consider the downlink of Cell-Free Massive MIMO systems, where a very large number of distributed access points (APs) simultaneously serve a much smaller number of users. Each AP uses local channel estimates obtained from received uplink pilots and applies conjugate beamforming to transmit data to the users. We derive a closed-form expression for the achievable rate. This expression enables us to design an optimal max-min power control scheme that gives equal quality of service to all users. We further compare the performance of the Cell-Free Massive MIMO system to that of a conventional small-cell network and show that the throughput of the Cell-Free system is much more concentrated around its median compared to that of the small-cell system. The Cell-Free Massive MIMO system can provide an almost $20-$fold increase in 95%-likely per-user throughput, compared with the small-cell system. Furthermore, Cell-Free systems are more robust to shadow fading correlation than small-cell systems.
A Graph Model for Opportunistic Network Coding
Venue: arXiv cs.IT 2015
Year: 2015

Recent advancements in graph-based analysis and solutions of instantly decodable network coding (IDNC) trigger the interest to extend them to more complicated opportunistic network coding (ONC) scenarios, with limited increase in complexity. In this paper, we design a simple IDNC-like graph model for a specific subclass of ONC, by introducing a more generalized definition of its vertices and the notion of vertex aggregation in order to represent the storage of non-instantly-decodable packets in ONC. Based on this representation, we determine the set of pairwise vertex adjacency conditions that can populate this graph with edges so as to guarantee decodability or aggregation for the vertices of each clique in this graph. We then develop the algorithmic procedures that can be applied on the designed graph model to optimize any performance metric for this ONC subclass. A case study on reducing the completion time shows that the proposed framework improves on the performance of IDNC and gets very close to the optimal performance.
Dropshipping - a new business revolution
Venue: arXiv cs.CY 2015
Year: 2015

Article about the new form of trade in a network the Internet. Advantages of dropshipping open to the Russian manufacturers and businessmen new horizons in international trade and marketing. The author considers features of evolution and a role of dropshipping in electronic commerce of a new millennium.
Marketing features of dropshipping in system of e-commerce
Venue: arXiv cs.CY 2015
Year: 2015

Today dropshipping wins the Internet promptly and transformed to one of the basic tools of marketing in e-commerce. Marketing features, mechanisms and value dropshipping in the conditions of network economy of the XXI century reveal in article. The author carries out the comparative analysis of institutional development dropshipping in the USA, China and Russia.
Sampling of stochastic operators
Venue: arXiv cs.IT 2015
Year: 2015

We develop sampling methodology aimed at determining stochastic operators that satisfy a support size restriction on the autocorrelation of the operators stochastic spreading function. The data that we use to reconstruct the operator (or, in some cases only the autocorrelation of the spreading function) is based on the response of the unknown operator to a known, deterministic test signal.
Tempus Fugit: The Impact of Time in Knowledge Mobilization Networks
Venue: arXiv cs.SI 2015
Year: 2015

The temporal component of social networks is often neglected in their analysis, and statistical measures are typically performed on a "static" representation of the network. As a result, measures of importance (like betweenness centrality) cannot reveal any temporal role of the entities involved. Our goal is to start filling this limitation by proposing a form of temporal betweenness measure, and by using it to analyse a knowledge mobilization network. We show that this measure, which takes time explicitly into account, allows us to detect centrality roles that were completely hidden in the classical statistical analysis. In particular, we uncover nodes whose static centrality was considered negligible, but whose temporal role is instead important to accelerate mobilization flow in the network. We also observe the reverse behaviour by detecting nodes with high static centrality, whose role as temporal bridges is instead very low. By revealing important temporal roles, this study is a first step towards a better understanding of the impact of time in social networks, and opens the road to further investigation.
Polynomial enumeration of chordless cycles on cyclically orientable graphs
Venue: arXiv cs.DS 2015
Year: 2015

In a finite undirected simple graph, a chordless cycle is an induced subgraph which is a cycle. A graph is called cyclically orientable if it admits an orientation in which every chordless cycle is cyclically oriented. We propose an algorithm to enumerate all chordless cycles of such a graph. Compared to other similar algorithms, the proposed algorithm have the advantage of finding each chordless cycle only once in time complexity $\mathcal{O}(n^2)$ in the input size, where $n$ is the number of vertices.