OpenRaiser/Intern-Atlas huggingface dataset:
Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
Venue: arXiv cs.GT 2016
Year: 2016

We study a type of reverse (procurement) auction problems in the presence of budget constraints. The general algorithmic problem is to purchase a set of resources, which come at a cost, so as not to exceed a given budget and at the same time maximize a given valuation function. This framework captures the budgeted version of several well known optimization problems, and when the resources are owned by strategic agents the goal is to design truthful and budget feasible mechanisms, i.e. elicit the true cost of the resources and ensure the payments of the mechanism do not exceed the budget. Budget feasibility introduces more challenges in mechanism design, and we study instantiations of this problem for certain classes of submodular and XOS valuation functions. We first obtain mechanisms with an improved approximation ratio for weighted coverage valuations, a special class of submodular functions that has already attracted attention in previous works. We then provide a general scheme for designing randomized and deterministic polynomial time mechanisms for a class of XOS problems. This class contains problems whose feasible set forms an independence system (a more general structure than matroids), and some representative problems include, among others, finding maximum weighted matchings, maximum weighted matroid members, and maximum weighted 3D-matchings. For most of these problems, only randomized mechanisms with very high approximation ratios were known prior to our results.
Next-to-leading order corrections to capacity for nondispersive nonlinear optical fiber channel in intermediate power region
Venue: arXiv cs.IT 2016
Year: 2016

We consider the optical fiber channel modelled by the nonlinear Shrödinger equation with zero dispersion and additive Gaussian noise. Using Feynman path-integral approach for the model we find corrections to conditional probability density function, output signal distribution, conditional and output signal entropies, and the channel capacity at large signal-to-noise ratio. We demonstrate that the correction to the channel capacity is positive for large signal power. Therefore, this correction increases the earlier calculated capacity for a nondispersive nonlinear optical fiber channel in the intermediate power region.
Embracing data abundance: BookTest Dataset for Reading Comprehension
Venue: arXiv cs.CL 2016
Year: 2016

There is a practically unlimited amount of natural language data available. Still, recent work in text comprehension has focused on datasets which are small relative to current computing possibilities. This article is making a case for the community to move to larger data and as a step in that direction it is proposing the BookTest, a new dataset similar to the popular Children's Book Test (CBT), however more than 60 times larger. We show that training on the new data improves the accuracy of our Attention-Sum Reader model on the original CBT test data by a much larger margin than many recent attempts to improve the model architecture. On one version of the dataset our ensemble even exceeds the human baseline provided by Facebook. We then show in our own human study that there is still space for further improvement.
Integration of higher IT education in Ukraine in the global IT-educational space
Venue: arXiv cs.CY 2016
Year: 2016

The article presents the results of a study of the current state of higher IT education system in Ukraine. The problems of reforming higher IT education system of Ukraine in accordance with the commitments made by Ukraine in connection with the ratification of the EU-Ukraine Agreement Law of Ukraine N 1678-VII of September 16, 2014. An indicator of the presence or absence of a real reform of the system of higher IT education in Ukraine is detected. A comparative analysis of lists of IT-specialties of higher education in Ukraine in 2005 and 2015 with similar lists adopted by the international system of higher IT education is made. A discrepancy between the list of IT-specialties in Ukraine and international list of IT specialties are identified. The conclusion about the need for immediate correction of the list of higher education in Ukraine IT-specialties in order to bring it into line with international standards. It recommended a series of actions that will lead to the solution of the problem.
Deciding equivalence with sums and the empty type
Venue: arXiv cs.PL 2016
Year: 2016

The logical technique of focusing can be applied to the $λ$-calculus; in a simple type system with atomic types and negative type formers (functions, products, the unit type), its normal forms coincide with $βη$-normal forms. Introducing a saturation phase gives a notion of quasi-normal forms in presence of positive types (sum types and the empty type). This rich structure let us prove the decidability of $βη$-equivalence in presence of the empty type, the fact that it coincides with contextual equivalence, and a finite model property.
ECAT: Event Capture Annotation Tool
Venue: arXiv cs.CL 2016
Year: 2016

This paper introduces the Event Capture Annotation Tool (ECAT), a user-friendly, open-source interface tool for annotating events and their participants in video, capable of extracting the 3D positions and orientations of objects in video captured by Microsoft's Kinect(R) hardware. The modeling language VoxML (Pustejovsky and Krishnaswamy, 2016) underlies ECAT's object, program, and attribute representations, although ECAT uses its own spec for explicit labeling of motion instances. The demonstration will show the tool's workflow and the options available for capturing event-participant relations and browsing visual data. Mapping ECAT's output to VoxML will also be addressed.
Nash-Peering: A New Techno-Economic Framework for Internet Interconnections
Venue: arXiv cs.GT 2016
Year: 2016

The current framework of Internet interconnections, based on transit and settlement-free peering relations, has systemic problems that often cause peering disputes. We propose a new techno-economic interconnection framework called Nash-Peering, which is based on the principles of Nash Bargaining in game theory and economics. Nash-Peering constitutes a radical departure from current interconnection practices, providing a broader and more economically efficient set of interdomain relations. In particular, the direction of payment is not determined by the direction of traffic or by rigid customer-provider relationships but based on which AS benefits more from the interconnection. We argue that Nash-Peering can address the root cause of various types of peering disputes.
Monaural Multi-Talker Speech Recognition using Factorial Speech Processing Models
Venue: arXiv cs.CL 2016
Year: 2016

A Pascal challenge entitled monaural multi-talker speech recognition was developed, targeting the problem of robust automatic speech recognition against speech like noises which significantly degrades the performance of automatic speech recognition systems. In this challenge, two competing speakers say a simple command simultaneously and the objective is to recognize speech of the target speaker. Surprisingly during the challenge, a team from IBM research, could achieve a performance better than human listeners on this task. The proposed method of the IBM team, consist of an intermediate speech separation and then a single-talker speech recognition. This paper reconsiders the task of this challenge based on gain adapted factorial speech processing models. It develops a joint-token passing algorithm for direct utterance decoding of both target and masker speakers, simultaneously. Comparing it to the challenge winner, it uses maximum uncertainty during the decoding which cannot be used in the past two-phased method. It provides detailed derivation of inference on these models based on general inference procedures of probabilistic graphical models. As another improvement, it uses deep neural networks for joint-speaker identification and gain estimation which makes these two steps easier than before producing competitive results for these steps. The proposed method of this work outperforms past super-human results and even the results were achieved recently by Microsoft research, using deep neural networks. It achieved 5.5% absolute task performance improvement compared to the first super-human system and 2.7% absolute task performance improvement compared to its recent competitor.
The Predictive Context Tree: Predicting Contexts and Interactions
Venue: arXiv cs.AI 2016
Year: 2016

With a large proportion of people carrying location-aware smartphones, we have an unprecedented platform from which to understand individuals and predict their future actions. This work builds upon the Context Tree data structure that summarises the historical contexts of individuals from augmented geospatial trajectories, and constructs a predictive model for their likely future contexts. The Predictive Context Tree (PCT) is constructed as a hierarchical classifier, capable of predicting both the future locations that a user will visit and the contexts that a user will be immersed within. The PCT is evaluated over real-world geospatial trajectories, and compared against existing location extraction and prediction techniques, as well as a proposed hybrid approach that uses identified land usage elements in combination with machine learning to predict future interactions. Our results demonstrate that higher predictive accuracies can be achieved using this hybrid approach over traditional extracted location datasets, and the PCT itself matches the performance of the hybrid approach at predicting future interactions, while adding utility in the form of context predictions. Such a prediction system is capable of understanding not only where a user will visit, but also their context, in terms of what they are likely to be doing.
A Probably Approximately Correct Answer to Distributed Stochastic Optimization in a Non-stationary Environment
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a distributed stochastic optimization problem where the goal is to minimize the time average of a cost function subject to a set of constraints on the time averages of a related stochastic processes called penalties. We assume that a delayed information about an event in the system is available as a common information at every user, and the state of the system is evolving in an independent and non-stationary fashion. We show that an approximate Drift-plus-penalty (DPP) algorithm that we propose achieves a time average cost that is within some positive constant epsilon of the optimal cost with high probability. Further, we provide a condition on the waiting time for this result to hold. The condition is shown to be a function of the mixing coefficient, the number of samples (w) used to compute an estimate of the distribution of the state, and the delay. Unlike the existing work, the method used in the paper can be adapted to prove high probability results when the state is evolving in a non-i.i.d and non-stationary fashion. Under mild conditions, we show that the dependency of the error bound on w is exponential, which is a significant improvement compared to the exiting work.
A new algorithm for identity verification based on the analysis of a handwritten dynamic signature
Venue: arXiv cs.CV 2016
Year: 2016

Identity verification based on authenticity assessment of a handwritten signature is an important issue in biometrics. There are many effective methods for signature verification taking into account dynamics of a signing process. Methods based on partitioning take a very important place among them. In this paper we propose a new approach to signature partitioning. Its most important feature is the possibility of selecting and processing of hybrid partitions in order to increase a precision of the test signature analysis. Partitions are formed by a combination of vertical and horizontal sections of the signature. Vertical sections correspond to the initial, middle, and final time moments of the signing process. In turn, horizontal sections correspond to the signature areas associated with high and low pen velocity and high and low pen pressure on the surface of a graphics tablet. Our previous research on vertical and horizontal sections of the dynamic signature (created independently) led us to develop the algorithm presented in this paper. Selection of sections, among others, allows us to define the stability of the signing process in the partitions, promoting signature areas of greater stability (and vice versa). In the test of the proposed method two databases were used: public MCYT-100 and paid BioSecure.
Towards a Drone Cinematographer: Guiding Quadrotor Cameras using Visual Composition Principles
Venue: arXiv cs.GR 2016
Year: 2016

We present a system to capture video footage of human subjects in the real world. Our system leverages a quadrotor camera to automatically capture well-composed video of two subjects. Subjects are tracked in a large-scale outdoor environment using RTK GPS and IMU sensors. Then, given the tracked state of our subjects, our system automatically computes static shots based on well-established visual composition principles and canonical shots from cinematography literature. To transition between these static shots, we calculate feasible, safe, and visually pleasing transitions using a novel real-time trajectory planning algorithm. We evaluate the performance of our tracking system, and experimentally show that RTK GPS significantly outperforms conventional GPS in capturing a variety of canonical shots. Lastly, we demonstrate our system guiding a consumer quadrotor camera autonomously capturing footage of two subjects in a variety of use cases. This is the first end-to-end system that enables people to leverage the mobility of quadrotors, as well as the knowledge of expert filmmakers, to autonomously capture high-quality footage of people in the real world.
A Deep Spatial Contextual Long-term Recurrent Convolutional Network for Saliency Detection
Venue: arXiv cs.CV 2016
Year: 2016

Traditional saliency models usually adopt hand-crafted image features and human-designed mechanisms to calculate local or global contrast. In this paper, we propose a novel computational saliency model, i.e., deep spatial contextual long-term recurrent convolutional network (DSCLRCN) to predict where people looks in natural scenes. DSCLRCN first automatically learns saliency related local features on each image location in parallel. Then, in contrast with most other deep network based saliency models which infer saliency in local contexts, DSCLRCN can mimic the cortical lateral inhibition mechanisms in human visual system to incorporate global contexts to assess the saliency of each image location by leveraging the deep spatial long short-term memory (DSLSTM) model. Moreover, we also integrate scene context modulation in DSLSTM for saliency inference, leading to a novel deep spatial contextual LSTM (DSCLSTM) model. The whole network can be trained end-to-end and works efficiently when testing. Experimental results on two benchmark datasets show that DSCLRCN can achieve state-of-the-art performance on saliency detection. Furthermore, the proposed DSCLSTM model can significantly boost the saliency detection performance by incorporating both global spatial interconnections and scene context modulation, which may uncover novel inspirations for studies on them in computational saliency models.
Generating Simulations of Motion Events from Verbal Descriptions
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we describe a computational model for motion events in natural language that maps from linguistic expressions, through a dynamic event interpretation, into three-dimensional temporal simulations in a model. Starting with the model from (Pustejovsky and Moszkowicz, 2011), we analyze motion events using temporally-traced Labelled Transition Systems. We model the distinction between path- and manner-motion in an operational semantics, and further distinguish different types of manner-of-motion verbs in terms of the mereo-topological relations that hold throughout the process of movement. From these representations, we generate minimal models, which are realized as three-dimensional simulations in software developed with the game engine, Unity. The generated simulations act as a conceptual "debugger" for the semantics of different motion verbs: that is, by testing for consistency and informativeness in the model, simulations expose the presuppositions associated with linguistic expressions and their compositions. Because the model generation component is still incomplete, this paper focuses on an implementation which maps directly from linguistic interpretations into the Unity code snippets that create the simulations.
Computer Network Defense Through Radial Wave Functions
Venue: arXiv cs.CR 2016
Year: 2016

The purpose of this research was to synthesize basic and fundamental findings in quantum computing, as applied to the attack and defense of conventional computer networks. The concept focuses on uses of radio waves as a shield for, and attack against traditional computers. A logic bomb is analogous to a landmine in a computer network, and if one was to implement it as non-trivial mitigation, it will aid computer network defense. As has been seen in kinetic warfare, the use of landmines has been devastating to geopolitical regions in that they are severely difficult for a civilian to avoid triggering given the unknown position of a landmine. Thus, the importance of understanding a logic bomb is relevant and has corollaries to quantum mechanics as well. The research synthesizes quantum logic phase shifts in certain respects using the Dynamic Data Exchange protocol in software written for this work, as well as a C-NOT gate applied to a virtual quantum circuit environment by implementing a Quantum Fourier Transform. The research focus applies the principles of coherence and entanglement from quantum physics, the concept of expert systems in artificial intelligence, principles of prime number based cryptography with trapdoor functions, and modeling radio wave propagation against an event from unknown parameters. This comes as a program relying on the artificial intelligence concept of an expert system in conjunction with trigger events for a trapdoor function relying on infinite recursion, as well as system mechanics for elliptic curve cryptography along orbital angular momenta. Here trapdoor both denotes the form of cipher, as well as the implied relationship to logic bombs.
Predicting encounter and colocation events in metropolitan areas
Venue: arXiv cs.SI 2016
Year: 2016

Despite an extensive literature has been devoted to mine and model mobility features, forecasting where, when and whom people will encounter/colocate still deserve further research efforts. Forecasting people's encounter and colocation features is the key point for the success of many applications ranging from epidemiology to the design of new networking paradigms and services such as delay tolerant and opportunistic networks. While many algorithms which rely on both mobility and social information have been proposed, we propose a novel encounter and colocation predictive model which predicts user's encounter and colocation events and their features by exploiting the spatio-temporal regularity in the history of these events. We adopt weighted features Bayesian predictor and evaluate its accuracy on two large scales WiFi and cellular datasets. Results show that our approach could improve prediction accuracy w.r.t standard naive Bayesian and some of the state-of-the-art predictors.
A Joint Detection-Classification Model for Audio Tagging of Weakly Labelled Data
Venue: arXiv cs.SD 2016
Year: 2016

Audio tagging aims to assign one or several tags to an audio clip. Most of the datasets are weakly labelled, which means only the tags of the clip are known, without knowing the occurrence time of the tags. The labeling of an audio clip is often based on the audio events in the clip and no event level label is provided to the user. Previous works have used the bag of frames model assume the tags occur all the time, which is not the case in practice. We propose a joint detection-classification (JDC) model to detect and classify the audio clip simultaneously. The JDC model has the ability to attend to informative and ignore uninformative sounds. Then only informative regions are used for classification. Experimental results on the "CHiME Home" dataset show that the JDC model reduces the equal error rate (EER) from 19.0% to 16.9%. More interestingly, the audio event detector is trained successfully without needing the event level label.
A Robust Framework for Classifying Evolving Document Streams in an Expert-Machine-Crowd Setting
Venue: arXiv cs.CL 2016
Year: 2016

An emerging challenge in the online classification of social media data streams is to keep the categories used for classification up-to-date. In this paper, we propose an innovative framework based on an Expert-Machine-Crowd (EMC) triad to help categorize items by continuously identifying novel concepts in heterogeneous data streams often riddled with outliers. We unify constrained clustering and outlier detection by formulating a novel optimization problem: COD-Means. We design an algorithm to solve the COD-Means problem and show that COD-Means will not only help detect novel categories but also seamlessly discover human annotation errors and improve the overall quality of the categorization process. Experiments on diverse real data sets demonstrate that our approach is both effective and efficient.
Distributed Nash Equilibrium Seeking By Gossip in Games on Graphs
Venue: arXiv cs.SY 2016
Year: 2016

We consider a gossip approach for finding a Nash equilibrium in a distributed multi-player network game. We extend previous results on Nash equilibrium seeking to the case when the players' cost functions may be affected by the actions of any subset of players. An interference graph is employed to illustrate the partially-coupled cost functions and the asymmetric information requirements. For a given interference graph, we design a generalized communication graph so that players with possibly partially-coupled cost functions exchange only their required information and make decisions based on them. Using a set of standard assumptions on the cost functions, interference and communication graphs, we prove almost sure convergence to a Nash equilibrium for diminishing step sizes. We then quantify the effect of the second largest eigenvalue of the expected communication matrix on the convergence rate, and illustrate the trade-off between the parameters associated with the communication and the interference graphs. Finally, the efficacy of the proposed algorithm on a large-scale networked game is demonstrated via simulation.