OpenRaiser/Intern-Atlas huggingface dataset:
Revenue Maximizing Envy-Free Pricing in Matching Markets with Budgets
Venue: arXiv cs.GT 2016
Year: 2016

We study envy-free pricing mechanisms in matching markets with $m$ items and $n$ budget constrained buyers. Each buyer is interested in a subset of the items on sale, and she appraises at some single-value every item in her preference-set. Moreover, each buyer has a budget that constraints the maximum affordable payment, while she aims to obtain as many items as possible of her preference-set. Our goal is to compute an envy-free pricing allocation that maximizes the revenue, i.e., the total payment charged to the buyers. This pricing problem is hard to approximate better than $Ω({\rm min} \{n,m\}^{1/2-ε})$ for any $ε>0$, unless $P=NP$. The hardness result is due to the presence of the matching constraints given that the simpler multi-unit case can be approximated up to a constant factor of $2$. The goal of this paper is to circumvent the hardness result by restricting ourselves to specific settings of valuations and budgets. Two particularly significant scenarios are: each buyer has a budget that is greater than her single-value valuation, and each buyer has a budget that is lower than her single-value valuation. Surprisingly, in both scenarios we are able to achieve a $1/4$-approximation to the optimal envy-free revenue. The algorithms utilize a novel version of the Ausebel ascending price auction. These results may suggest that, although it is difficult to approximate the optimal revenue in general, ascending price auctions could achieve relatively good revenue in most of the practical settings.
Toward Implicit Sample Noise Modeling: Deviation-driven Matrix Factorization
Venue: arXiv cs.LG 2016
Year: 2016

The objective function of a matrix factorization model usually aims to minimize the average of a regression error contributed by each element. However, given the existence of stochastic noises, the implicit deviations of sample data from their true values are almost surely diverse, which makes each data point not equally suitable for fitting a model. In this case, simply averaging the cost among data in the objective function is not ideal. Intuitively we would like to emphasize more on the reliable instances (i.e., those contain smaller noise) while training a model. Motivated by such observation, we derive our formula from a theoretical framework for optimal weighting under heteroscedastic noise distribution. Specifically, by modeling and learning the deviation of data, we design a novel matrix factorization model. Our model has two advantages. First, it jointly learns the deviation and conducts dynamic reweighting of instances, allowing the model to converge to a better solution. Second, during learning the deviated instances are assigned lower weights, which leads to faster convergence since the model does not need to overfit the noise. The experiments are conducted in clean recommendation and noisy sensor datasets to test the effectiveness of the model in various scenarios. The results show that our model outperforms the state-of-the-art factorization and deep learning models in both accuracy and efficiency.
Real-time Online Action Detection Forests using Spatio-temporal Contexts
Venue: arXiv cs.CV 2016
Year: 2016

Online action detection (OAD) is challenging since 1) robust yet computationally expensive features cannot be straightforwardly used due to the real-time processing requirements and 2) the localization and classification of actions have to be performed even before they are fully observed. We propose a new random forest (RF)-based online action detection framework that addresses these challenges. Our algorithm uses computationally efficient skeletal joint features. High accuracy is achieved by using robust convolutional neural network (CNN)-based features which are extracted from the raw RGBD images, plus the temporal relationships between the current frame of interest, and the past and future frames. While these high-quality features are not available in real-time testing scenario, we demonstrate that they can be effectively exploited in training RF classifiers: We use these spatio-temporal contexts to craft RF's new split functions improving RFs' leaf node statistics. Experiments with challenging MSRAction3D, G3D, and OAD datasets demonstrate that our algorithm significantly improves the accuracy over the state-of-the-art online action detection algorithms while achieving the real-time efficiency of existing skeleton-based RF classifiers.
A MAP-MRF filter for phase-sensitive coil combination in autocalibrating partially parallel susceptibility weighted MRI
Venue: arXiv cs.CV 2016
Year: 2016

A statistical approach for combination of channel phases is developed for optimizing the Contrast-to-Noise Ratio (CNR) in Susceptibility Weighted Images (SWI) acquired using autocalibrating partially parallel techniques. The unwrapped phase images of each coil are filtered using local random field based probabilistic weights, derived using energy functions representative of noisy sensitivity and tissue information pertaining to venous structure in the individual channel phase images. The channel energy functions are obtained as functions of local image intensities, first or second order clique phase difference and a threshold scaling parameter dependent on the input noise level. Whereas the expectation of the individual energy functions with respect to the noise distribution in clique phase differences is to be maximized for optimal filtering, the expectation of tissue energy function decreases and noise energy function increases with increase in threshold scale parameter. The optimum scaling parameter is shown to occur at the point where expectations of both energy functions contribute to the largest possible extent. It is shown that implementation of the filter in the same lines as that of Iterated Conditional Modes (ICM) algorithm provides structural enhancement in the coil combined phase, with reduced noise amplification. Application to simulated and in vivo multi-channel SWI shows that CNR of combined phase obtained using MAP-MRF filter is higher as compared to that of coil combination using weighted average.
The Joint Signature and Encryption Revisited
Venue: arXiv cs.CR 2016
Year: 2016

We study the Sign_then_Encrypt, Commit_then_Encrypt_and_Sign, and Encrypt_then_Sign paradigms in the context of two cryptographic primitives, namely designated confirmer signatures and signcryption. Our study identifies weaknesses in those paradigms which impose the use of expensive encryption (as a building block) in order to meet a reasonable security level. Next, we propose some optimizations which annihilate the found weaknesses and allow consequently cheap encryption without compromising the overall security. Our optimizations further enjoy verifiability, a property profoundly needed in many real-life applications of the studied primitives.
Data Source Selection for Information Integration in Big Data Era
Venue: arXiv cs.DB 2016
Year: 2016

In Big data era, information integration often requires abundant data extracted from massive data sources. Due to a large number of data sources, data source selection plays a crucial role in information integration, since it is costly and even impossible to access all data sources. Data Source selection should consider both efficiency and effectiveness issues. For efficiency, the approach should achieve high performance and be scalability to fit large data source amount. From effectiveness aspect, data quality and overlapping of sources are to be considered, since data quality varies much from data sources, with significant differences in the accuracy and coverage of the data provided, and the overlapping of sources can even lower the quality of data integrated from selected data sources. In this paper, we study source selection problem in \textit{Big Data Era} and propose methods which can scale to datasets with up to millions of data sources and guarantee the quality of results. Motivated by this, we propose a new object function taking the expected number of true values a source can provide as a criteria to evaluate the contribution of a data source. Based on our proposed index we present a scalable algorithm and two pruning strategies to improve the efficiency without sacrificing precision. Experimental results on both real world and synthetic data sets show that our methods can select sources providing a large proportion of true values efficiently and can scale to massive data sources.
Sequence-to-sequence neural network models for transliteration
Venue: arXiv cs.CL 2016
Year: 2016

Transliteration is a key component of machine translation systems and software internationalization. This paper demonstrates that neural sequence-to-sequence models obtain state of the art or close to state of the art results on existing datasets. In an effort to make machine transliteration accessible, we open source a new Arabic to English transliteration dataset and our trained models.
Generalized Haar Filter based Deep Networks for Real-Time Object Detection in Traffic Scene
Venue: arXiv cs.CV 2016
Year: 2016

Vision-based object detection is one of the fundamental functions in numerous traffic scene applications such as self-driving vehicle systems and advance driver assistance systems (ADAS). However, it is also a challenging task due to the diversity of traffic scene and the storage, power and computing source limitations of the platforms for traffic scene applications. This paper presents a generalized Haar filter based deep network which is suitable for the object detection tasks in traffic scene. In this approach, we first decompose a object detection task into several easier local regression tasks. Then, we handle the local regression tasks by using several tiny deep networks which simultaneously output the bounding boxes, categories and confidence scores of detected objects. To reduce the consumption of storage and computing resources, the weights of the deep networks are constrained to the form of generalized Haar filter in training phase. Additionally, we introduce the strategy of sparse windows generation to improve the efficiency of the algorithm. Finally, we perform several experiments to validate the performance of our proposed approach. Experimental results demonstrate that the proposed approach is both efficient and effective in traffic scene compared with the state-of-the-art.
Computing a clique tree with algorithm MLS (Maximal Label Search)
Venue: arXiv cs.DS 2016
Year: 2016

Algorithm MLS (Maximal Label Search) is a graph search algorithm which generalizes algorithms MCS, LexBFS, LexDFS and MNS. On a chordal graph, MLS computes a peo (perfect elimination ordering) of the graph. We show how algorithm MLS can be modified to compute a pmo (perfect moplex ordering) as well as a clique tree and the minimal separators of a chordal graph. We give a necessary and sufficient condition on the labeling structure for the beginning of a new clique in the clique tree to be detected by a condition on labels. MLS is also used to compute a clique tree of the complement graph, and new cliques in the complement graph can be detected by a condition on labels for any labeling structure. A linear time algorithm computing a pmo and the generators of the maximal cliques and minimal separators w.r.t. this pmo of the complement graph is provided. On a non-chordal graph, algorithm MLSM is used to compute an atom tree of the clique minimal separator decomposition of any graph.
A Bibliometric Study of Asia Pacific Software Engineering Conference from 2010 to 2015
Venue: arXiv cs.SE 2016
Year: 2016

The Asia-Pacific Software Engineering Conference (APSEC) is a reputed and a long-running conference which has successfully completed more than two decades as of year 2015. We conduct a bibliometric and scientific publication mining based study to how the conference has evolved over the recent past six years (year 2010 to 2015). Our objective is to perform in-depth examination of the state of APSEC so that the APSEC community can identify strengths, areas of improvements and future directions for the conference. Our empirical analysis is based on various perspectives such as: paper submission acceptance rate trends, conference location, scholarly productivity and contributions from various countries, analysis of keynotes, workshops, conference organizers and sponsors, tutorials, identification of prolific authors, computation of citation impact of papers and contributing authors, internal and external collaboration, university and industry participation and collaboration, measurement of gender imbalance, topical analysis, yearly author churn and program committee characteristics.
Energy-Efficient Heterogeneous Cellular Networks with Spectrum Underlay and Overlay Access
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we provide joint subcarrier assignment and power allocation schemes for quality-of-service (QoS)-constrained energy-efficiency (EE) optimization in the downlink of an orthogonal frequency division multiple access (OFDMA)-based two-tier heterogeneous cellular network (HCN). Considering underlay transmission, where spectrum-efficiency (SE) is fully exploited, the EE solution involves tackling a complex mixed-combinatorial and non-convex optimization problem. With appropriate decomposition of the original problem and leveraging on the quasi-concavity of the EE function, we propose a dual-layer resource allocation approach and provide a complete solution using difference-of-two-concave-functions approximation, successive convex approximation, and gradient-search methods. On the other hand, the inherent inter-tier interference from spectrum underlay access may degrade EE particularly under dense small-cell deployment and large bandwidth utilization. We therefore develop a novel resource allocation approach based on the concepts of spectrum overlay access and resource efficiency (RE) (normalized EE-SE trade-off). Specifically, the optimization procedure is separated in this case such that the macro-cell optimal RE and corresponding bandwidth is first determined, then the EE of small-cells utilizing the remaining spectrum is maximized. Simulation results confirm the theoretical findings and demonstrate that the proposed resource allocation schemes can approach the optimal EE with each strategy being superior under certain system settings.
Subquadratic Submodular Function Minimization
Venue: arXiv cs.DS 2016
Year: 2016

Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and machine learning, fast SFM algorithms are highly desirable. The current fastest algorithms [Lee, Sidford, Wong, FOCS 2015] run in $O(n^{2}\log nM\cdot\textrm{EO} +n^{3}\log^{O(1)}nM)$ time and $O(n^{3}\log^{2}n\cdot \textrm{EO} +n^{4}\log^{O(1)}n$) time respectively, where $M$ is the largest absolute value of the function (assuming the range is integers) and $\textrm{EO}$ is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only $Ω(n)$, the current shortest non-deterministic proof certifying the optimum value of a function requires $Θ(n^{2})$ function evaluations. The main contribution of this paper are subquadratic SFM algorithms. For integer-valued submodular functions, we give an SFM algorithm which runs in $O(nM^{3}\log n\cdot\textrm{EO})$ time giving the first nearly linear time algorithm in any known regime. For real-valued submodular functions with range in $[-1,1]$, we give an algorithm which in $\tilde{O}(n^{5/3}\cdot\textrm{EO}/\varepsilon^{2})$ time returns an $\varepsilon$-additive approximate solution. At the heart of it, our algorithms are projected stochastic subgradient descent methods on the Lovasz extension of submodular functions where we crucially exploit submodularity and data structures to obtain fast, i.e. sublinear time subgradient updates. . The latter is crucial for beating the $n^{2}$ bound as we show that algorithms which access only subgradients of the Lovasz extension, and these include the theoretically best algorithms mentioned above, must make $Ω(n)$ subgradient calls (even for functions whose range is $\{-1,0,1\}$).
Joint Transceiver and Power Splitter Design Over Two-Way Relaying Channel with Lattice Codes and Energy Harvesting
Venue: arXiv cs.IT 2016
Year: 2016

This letter considers a compute-and-forward two-way relaying channel with simultaneous wireless information and power transfer. Specifically, two single-antenna users exchange information via a multi-antenna relay station based on nested lattice codes. Meanwhile, wireless energies flow from the relay to users for circuit consumption and uplink transmission. Based on this model, an optimization problem is formulated to minimize the transmit power at relay, while guaranteeing the minimal transmission rate at each user. To solve the problem, we propose an efficient iterative algorithm to jointly optimize the transmitter, receiver and power splitter, based on semi-definite relaxation and semi-definite programming. Numerical results of relay transmission powers validate our analysis.
Mining Social Media for Open Innovation in Transportation Systems
Venue: arXiv cs.CY 2016
Year: 2016

This work proposes a novel framework for the development of new products and services in transportation through an open innovation approach based on automatic content analysis of social media data. The framework is able to extract users comments from Online Social Networks (OSN), to process and analyze text through information extraction and sentiment analysis techniques to obtain relevant information about product reception on the market. A use case was developed using the mobile application Uber, which is today one of the fastest growing technology companies in the world. We measured how a controversial, highly diffused event influences the volume of tweets about Uber and the perception of its users. While there is no change in the image of Uber, a large increase in the number of tweets mentioning the company is observed, which meant a free and important diffusion of its product.
Sentiment Analysis of Review Datasets Using Naive Bayes and K-NN Classifier
Venue: arXiv cs.IR 2016
Year: 2016

The advent of Web 2.0 has led to an increase in the amount of sentimental content available in the Web. Such content is often found in social media web sites in the form of movie or product reviews, user comments, testimonials, messages in discussion forums etc. Timely discovery of the sentimental or opinionated web content has a number of advantages, the most important of all being monetization. Understanding of the sentiments of human masses towards different entities and products enables better services for contextual advertisements, recommendation systems and analysis of market trends. The focus of our project is sentiment focussed web crawling framework to facilitate the quick discovery of sentimental contents of movie reviews and hotel reviews and analysis of the same. We use statistical methods to capture elements of subjective style and the sentence polarity. The paper elaborately discusses two supervised machine learning algorithms: K-Nearest Neighbour(K-NN) and Naive Bayes and compares their overall accuracy, precisions as well as recall values. It was seen that in case of movie reviews Naive Bayes gave far better results than K-NN but for hotel reviews these algorithms gave lesser, almost same accuracies.
Submodular Optimization over Sliding Windows
Venue: arXiv cs.DS 2016
Year: 2016

Maximizing submodular functions under cardinality constraints lies at the core of numerous data mining and machine learning applications, including data diversification, data summarization, and coverage problems. In this work, we study this question in the context of data streams, where elements arrive one at a time, and we want to design low-memory and fast update-time algorithms that maintain a good solution. Specifically, we focus on the sliding window model, where we are asked to maintain a solution that considers only the last $W$ items. In this context, we provide the first non-trivial algorithm that maintains a provable approximation of the optimum using space sublinear in the size of the window. In particular we give a $\frac{1}{3} - ε$ approximation algorithm that uses space polylogarithmic in the spread of the values of the elements, $Φ$, and linear in the solution size $k$ for any constant $ε> 0$ . At the same time, processing each element only requires a polylogarithmic number of evaluations of the function itself. When a better approximation is desired, we show a different algorithm that, at the cost of using more memory, provides a $\frac{1}{2} - ε$ approximation and allows a tunable trade-off between average update time and space. This algorithm matches the best known approximation guarantees for submodular optimization in insertion-only streams, a less general formulation of the problem. We demonstrate the efficacy of the algorithms on a number of real world datasets, showing that their practical performance far exceeds the theoretical bounds. The algorithms preserve high quality solutions in streams with millions of items, while storing a negligible fraction of them.
Tracking Infection Diffusion in Social Networks: Filtering Algorithms and Threshold Bounds
Venue: arXiv cs.SI 2016
Year: 2016

This paper deals with the statistical signal pro- cessing over graphs for tracking infection diffusion in social networks. Infection (or Information) diffusion is modeled using the Susceptible-Infected-Susceptible (SIS) model. Mean field approximation is employed to approximate the discrete valued infected degree distribution evolution by a deterministic ordinary differential equation for obtaining a generative model for the infection diffusion. The infected degree distribution is shown to follow polynomial dynamics and is estimated using an exact non- linear Bayesian filter. We compute posterior Cramer-Rao bounds to obtain the fundamental limits of the filter which depend on the structure of the network. Considering the time-varying nature of the real world networks, the relationship between the diffusion thresholds and the degree distribution is investigated using generative models for real world networks. In addition, we validate the efficacy of our method with the diffusion data from a real-world online social system, Twitter. We find that SIS model is a good fit for the information diffusion and the non-linear filter effectively tracks the information diffusion.
A Detailed Rubric for Motion Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Motion segmentation is currently an active area of research in computer Vision. The task of comparing different methods of motion segmentation is complicated by the fact that researchers may use subtly different definitions of the problem. Questions such as "Which objects are moving?", "What is background?", and "How can we use motion of the camera to segment objects, whether they are static or moving?" are clearly related to each other, but lead to different algorithms, and imply different versions of the ground truth. This report has two goals. The first is to offer a precise definition of motion segmentation so that the intent of an algorithm is as well-defined as possible. The second is to report on new versions of three previously existing data sets that are compatible with this definition. We hope that this more detailed definition, and the three data sets that go with it, will allow more meaningful comparisons of certain motion segmentation methods.