OpenRaiser/Intern-Atlas huggingface dataset:
Learning Multi-item Auctions with (or without) Samples
Venue: arXiv cs.GT 2017
Year: 2017

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of valuations including unit-demand, additive, constrained additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly studied setting where sample access to the bidders' distributions over valuations is given, for both regular distributions and arbitrary distributions with bounded support. Our algorithms require polynomially many samples in the number of items and bidders. The second is a more general max-min learning setting that we introduce, where we are given "approximate distributions," and we seek to compute an auction whose revenue is approximately optimal simultaneously for all "true distributions" that are close to the given ones. These results are more general in that they imply the sample-based results, and are also applicable in settings where we have no sample access to the underlying distributions but have estimated them indirectly via market research or by observation of previously run, potentially non-truthful auctions. Our results hold for valuation distributions satisfying the standard (and necessary) independence-across-items property. They also generalize and improve upon recent works, which have provided algorithms that learn approximately optimal auctions in more restricted settings with additive, subadditive and unit-demand valuations using sample access to distributions. We generalize these results to the complete unit-demand, additive, and XOS setting, to i.i.d. subadditive bidders, and to the max-min setting. Our results are enabled by new uniform convergence bounds for hypotheses classes under product measures. Our bounds result in exponential savings in sample complexity compared to bounds derived by bounding the VC dimension, and are of independent interest.
Too Far to See? Not Really! --- Pedestrian Detection with Scale-aware Localization Policy
Venue: arXiv cs.CV 2017
Year: 2017

A major bottleneck of pedestrian detection lies on the sharp performance deterioration in the presence of small-size pedestrians that are relatively far from the camera. Motivated by the observation that pedestrians of disparate spatial scales exhibit distinct visual appearances, we propose in this paper an active pedestrian detector that explicitly operates over multiple-layer neuronal representations of the input still image. More specifically, convolutional neural nets such as ResNet and faster R-CNNs are exploited to provide a rich and discriminative hierarchy of feature representations as well as initial pedestrian proposals. Here each pedestrian observation of distinct size could be best characterized in terms of the ResNet feature representation at a certain layer of the hierarchy; Meanwhile, initial pedestrian proposals are attained by faster R-CNNs techniques, i.e. region proposal network and follow-up region of interesting pooling layer employed right after the specific ResNet convolutional layer of interest, to produce joint predictions on the bounding-box proposals' locations and categories (i.e. pedestrian or not). This is engaged as input to our active detector where for each initial pedestrian proposal, a sequence of coordinate transformation actions is carried out to determine its proper x-y 2D location and layer of feature representation, or eventually terminated as being background. Empirically our approach is demonstrated to produce overall lower detection errors on widely-used benchmarks, and it works particularly well with far-scale pedestrians. For example, compared with 60.51% log-average miss rate of the state-of-the-art MS-CNN for far-scale pedestrians (those below 80 pixels in bounding-box height) of the Caltech benchmark, the miss rate of our approach is 41.85%, with a notable reduction of 18.68%.
When Data Sponsoring Meets Edge Caching: A Game-Theoretic Analysis
Venue: arXiv cs.NI 2017
Year: 2017

Data sponsoring is a widely-used incentive method in today's cellular networks, where video content providers (CPs) cover part or all of the cellular data cost for mobile users so as to attract more video users and increase data traffic. In the forthcoming 5G cellular networks, edge caching is emerging as a promising technique to deliver videos with lower cost and higher quality. The key idea is to cache video contents on edge networks (e.g., femtocells and WiFi access points) in advance and deliver the cached contents to local video users directly (without involving cellular data cost for users). In this work, we aim to study how the edge caching will affect the CP's data sponsoring strategy as well as the users' behaviors and the data market. Specifically, we consider a single CP who offers both the edge caching service and the data sponsoring service to a set of heterogeneous mobile video users (with different mobility and video request patterns). We formulate the interactions of the CP and the users as a two-stage Stackelberg game, where the CP (leader) determines the budgets (efforts) for both services in Stage I, and the users (followers) decide whether and which service(s) they would like to subscribe to. We analyze the sub-game perfect equilibrium (SPE) of the proposed game systematically. Our analysis and experimental results show that by introducing the edge caching, the CP can increase his revenue by 105%.
An Email Attachment is Worth a Thousand Words, or Is It?
Venue: arXiv cs.SI 2017
Year: 2017

There is an extensive body of research on Social Network Analysis (SNA) based on the email archive. The network used in the analysis is generally extracted either by capturing the email communication in From, To, Cc and Bcc email header fields or by the entities contained in the email message. In the latter case, the entities could be, for instance, the bag of words, url's, names, phones, etc. It could also include the textual content of attachments, for instance Microsoft Word documents, excel spreadsheets, or Adobe pdfs. The nodes in this network represent users and entities. The edges represent communication between users and relations to the entities. We suggest taking a different approach to the network extraction and use attachments shared between users as the edges. The motivation for this is two-fold. First, attachments represent the "intimacy" manifestation of the relation's strength. Second, the statistical analysis of private email archives that we collected and Enron email corpus shows that the attachments contribute in average around 80-90% to the archive's disk-space usage, which means that most of the data is presently ignored in the SNA of email archives. Consequently, we hypothesize that this approach might provide more insight into the social structure of the email archive. We extract the communication and shared attachments networks from Enron email corpus. We further analyze degree, betweenness, closeness, and eigenvector centrality measures in both networks and review the differences and what can be learned from them. We use nearest neighbor algorithm to generate similarity groups for five Enron employees. The groups are consistent with Enron's organizational chart, which validates our approach.
Lensless-camera based machine learning for image classification
Venue: arXiv cs.CV 2017
Year: 2017

Machine learning (ML) has been widely applied to image classification. Here, we extend this application to data generated by a camera comprised of only a standard CMOS image sensor with no lens. We first created a database of lensless images of handwritten digits. Then, we trained a ML algorithm on this dataset. Finally, we demonstrated that the trained ML algorithm is able to classify the digits with accuracy as high as 99% for 2 digits. Our approach clearly demonstrates the potential for non-human cameras in machine-based decision-making scenarios.
Symbol Synchronization for Diffusion-Based Molecular Communications
Venue: arXiv cs.IT 2017
Year: 2017

Symbol synchronization refers to the estimation of the start of a symbol interval and is needed for reliable detection. In this paper, we develop several symbol synchronization schemes for molecular communication (MC) systems where we consider some practical challenges which have not been addressed in the literature yet. In particular, we take into account that in MC systems, the transmitter may not be equipped with an internal clock and may not be able to emit molecules with a fixed release frequency. Such restrictions hold for practical nanotransmitters, e.g. modified cells, where the lengths of the symbol intervals may vary due to the inherent randomness in the availability of food and energy for molecule generation, the process for molecule production, and the release process. To address this issue, we develop two synchronization-detection frameworks which both employ two types of molecule. In the first framework, one type of molecule is used for symbol synchronization and the other one is used for data detection, whereas in the second framework, both types of molecule are used for joint symbol synchronization and data detection. For both frameworks, we first derive the optimal maximum likelihood (ML) symbol synchronization schemes as performance upper bounds. Since ML synchronization entails high complexity, for each framework, we also propose three low-complexity suboptimal schemes, namely a linear filter-based scheme, a peak observation-based scheme, and a threshold-trigger scheme which are suitable for MC systems with limited computational capabilities. Furthermore, we study the relative complexity and the constraints associated with the proposed schemes and the impact of the insertion and deletion errors that arise due to imperfect synchronization.
Facial 3D Model Registration Under Occlusions With SensiblePoints-based Reinforced Hypothesis Refinement
Venue: arXiv cs.CV 2017
Year: 2017

Registering a 3D facial model to a 2D image under occlusion is difficult. First, not all of the detected facial landmarks are accurate under occlusions. Second, the number of reliable landmarks may not be enough to constrain the problem. We propose a method to synthesize additional points (SensiblePoints) to create pose hypotheses. The visual clues extracted from the fiducial points, non-fiducial points, and facial contour are jointly employed to verify the hypotheses. We define a reward function to measure whether the projected dense 3D model is well-aligned with the confidence maps generated by two fully convolutional networks, and use the function to train recurrent policy networks to move the SensiblePoints. The same reward function is employed in testing to select the best hypothesis from a candidate pool of hypotheses. Experimentation demonstrates that the proposed approach is very promising in solving the facial model registration problem under occlusion.
An Automated Compatibility Prediction Engine using DISC Theory Based Classification and Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

Traditionally psychometric tests were used for profiling incoming workers. These methods use DISC profiling method to classify people into distinct personality types, which are further used to predict if a person may be a possible fit to the organizational culture. This concept is taken further by introducing a novel technique to predict if a particular pair of an incoming worker and the manager being assigned are compatible at a psychological scale. This is done using multilayer perceptron neural network which can be adaptively trained to showcase the true nature of the compatibility index. The proposed prototype model is used to quantify the relevant attributes, use them to train the prediction engine, and to define the data pipeline required for it.
Dynamic Shortest Path and Transitive Closure Algorithms: A Survey
Venue: arXiv cs.DS 2017
Year: 2017

Algorithms which compute properties over graphs have always been of interest in computer science, with some of the fundamental algorithms, such as Dijkstra's algorithm, dating back to the 50s. Since the 70s there as been interest in computing over graphs which are constantly changing, in a way which is more efficient than simple recomputing after each time the graph changes. In this paper we provide a survey of both the foundational, and the state of the art, algorithms which solve either shortest path or transitive closure problems in either fully or partially dynamic graphs. We balance this with the known conditional lowerbounds.
Distributed Multi-task Formation Control under Parametric Communication Uncertainties
Venue: arXiv cs.SY 2017
Year: 2017

Formation control is a key problem in the coordination of multiple agents. It arises new challenges to traditional formation control strategy when the communication among agents is affected by uncertainties. This paper considers the robust multi-task formation control problem of multiple non-point agents whose communications are disturbed by uncertain parameters. The control objectives include 1. achieving the desired configuration; 2. avoiding collisions; 3. preserving the connectedness of uncertain topology. To achieve these objectives, firstly, a condition of Linear Matrix Inequalities (LMIs) is proposed for checking the connectedness of an uncertain communication topology. Then, by preserving the initial topological connectedness, a gradient-based distributed controller is designed via Lyapunov-like barrier functions. Two numerical examples illustrate the effectiveness of the proposed method.
Cognitive Connectivity Resilience in Multi-layer Remotely Deployed Mobile Internet of Things
Venue: arXiv cs.NI 2017
Year: 2017

Enabling the Internet of things in remote areas without traditional communication infrastructure requires a multi-layer network architecture. The devices in the overlay network are required to provide coverage to the underlay devices as well as to remain connected to other overlay devices. The coordination, planning, and design of such two-layer heterogeneous networks is an important problem to address. Moreover, the mobility of the nodes and their vulnerability to adversaries pose new challenges to the connectivity. For instance, the connectivity of devices can be affected by changes in the network, e.g., the mobility of the underlay devices or the unavailability of overlay devices due to failure or adversarial attacks. To this end, this work proposes a feedback based adaptive, self-configurable, and resilient framework for the overlay network that cognitively adapts to the changes in the network to provide reliable connectivity between spatially dispersed smart devices. Our results show that if sufficient overlay devices are available, the framework leads to a connected configuration that ensures a high coverage of the mobile underlay network. Moreover, the framework can actively reconfigure itself in the event of varying levels of device failure.
Using Summarization to Discover Argument Facets in Online Ideological Dialog
Venue: arXiv cs.AI 2017
Year: 2017

More and more of the information available on the web is dialogic, and a significant portion of it takes place in online forum conversations about current social and political topics. We aim to develop tools to summarize what these conversations are about. What are the CENTRAL PROPOSITIONS associated with different stances on an issue, what are the abstract objects under discussion that are central to a speaker's argument? How can we recognize that two CENTRAL PROPOSITIONS realize the same FACET of the argument? We hypothesize that the CENTRAL PROPOSITIONS are exactly those arguments that people find most salient, and use human summarization as a probe for discovering them. We describe our corpus of human summaries of opinionated dialogs, then show how we can identify similar repeated arguments, and group them into FACETS across many discussions of a topic. We define a new task, ARGUMENT FACET SIMILARITY (AFS), and show that we can predict AFS with a .54 correlation score, versus an ngram system baseline of .39 and a semantic textual similarity system baseline of .45.
Unsupervised feature learning with discriminative encoder
Venue: arXiv cs.CV 2017
Year: 2017

In recent years, deep discriminative models have achieved extraordinary performance on supervised learning tasks, significantly outperforming their generative counterparts. However, their success relies on the presence of a large amount of labeled data. How can one use the same discriminative models for learning useful features in the absence of labels? We address this question in this paper, by jointly modeling the distribution of data and latent features in a manner that explicitly assigns zero probability to unobserved data. Rather than maximizing the marginal probability of observed data, we maximize the joint probability of the data and the latent features using a two step EM-like procedure. To prevent the model from overfitting to our initial selection of latent features, we use adversarial regularization. Depending on the task, we allow the latent features to be one-hot or real-valued vectors and define a suitable prior on the features. For instance, one-hot features correspond to class labels and are directly used for the unsupervised and semi-supervised classification task, whereas real-valued feature vectors are fed as input to simple classifiers for auxiliary supervised discrimination tasks. The proposed model, which we dub discriminative encoder (or DisCoder), is flexible in the type of latent features that it can capture. The proposed model achieves state-of-the-art performance on several challenging tasks.
Disentangling ASR and MT Errors in Speech Translation
Venue: arXiv cs.CL 2017
Year: 2017

The main aim of this paper is to investigate automatic quality assessment for spoken language translation (SLT). More precisely, we investigate SLT errors that can be due to transcription (ASR) or to translation (MT) modules. This paper investigates automatic detection of SLT errors using a single classifier based on joint ASR and MT features. We evaluate both 2-class (good/bad) and 3-class (good/badASR/badMT ) labeling tasks. The 3-class problem necessitates to disentangle ASR and MT errors in the speech translation output and we propose two label extraction methods for this non trivial step. This enables - as a by-product - qualitative analysis on the SLT errors and their origin (are they due to transcription or to translation step?) on our large in-house corpus for French-to-English speech translation.
A multifactor RSA-like scheme with fast decryption based on Rédei rational functions over the Pell hyperbola
Venue: arXiv cs.IT 2017
Year: 2017

We propose a generalization of an RSA-like scheme based on Rédei rational functions over the Pell hyperbola. Instead of a modulus which is a product of two primes, we define the scheme on a multi-factor modulus, i.e. on a product of more than two primes. This results in a scheme with a decryption which is quadratically faster, in the number of primes factoring the modulus, than the original RSA, while preserving a better security. The scheme reaches its best efficiency advantage over RSA for high security levels, since in these cases the modulus can contain more primes. Compared to the analog schemes based on elliptic curves, as the KMOV cryptosystem, the proposed scheme is more efficient. Furthermore a variation of the scheme with larger ciphertext size does not suffer of impossible group operation attacks, as it happens for schemes based on elliptic curves.
Home Location Estimation Using Weather Observation Data
Venue: arXiv cs.SI 2017
Year: 2017

We can extract useful information from social media data by adding the user's home location. However, since the user's home location is generally not publicly available, many researchers have been attempting to develop a more accurate home location estimation. In this study, we propose a method to estimate a Twitter user's home location by using weather observation data from AMeDAS. In our method, we first estimate the weather of the area posted by an estimation target user by using the tweet, Next, we check out the estimated weather against weather observation data, and narrow down the area posted by the user. Finally, the user's home location is estimated as which areas the user frequently posts from. In our experiments, the results indicate that our method functions effectively and also demonstrate that accuracy improves under certain conditions.
Distributed Real-Time HVAC Control for Cost-Efficient Commercial Buildings under Smart Grid Environment
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we investigate the problem of minimizing the long-term total cost (i.e., the sum of energy cost and thermal discomfort cost) associated with a Heating, Ventilation, and Air Conditioning (HVAC) system of a multizone commercial building under smart grid environment. To be specific, we first formulate a stochastic program to minimize the time average expected total cost with the consideration of uncertainties in electricity price, outdoor temperature, the most comfortable temperature level, and external thermal disturbance. Due to the existence of temporally and spatially coupled constraints as well as unknown information about the future system parameters, it is very challenging to solve the formulated problem. To this end, we propose a realtime HVAC control algorithm based on the framework of Lyapunov optimization techniques without the need to predict any system parameters and know their stochastic information. The key idea of the proposed algorithm is to construct and stabilize virtual queues associated with indoor temperatures of all zones. Moreover, we provide a distributed implementation of the proposed realtime algorithm with the aim of protecting user privacy and enhancing algorithmic scalability. Extensive simulation results based on real-world traces show that the proposed algorithm could reduce energy cost effectively with small sacrifice in thermal comfort.
Formalising Type-Logical Grammars in Agda
Venue: arXiv cs.LO 2017
Year: 2017

In recent years, the interest in using proof assistants to formalise and reason about mathematics and programming languages has grown. Type-logical grammars, being closely related to type theories and systems used in functional programming, are a perfect candidate to next apply this curiosity to. The advantages of using proof assistants is that they allow one to write formally verified proofs about one's type-logical systems, and that any theory, once implemented, can immediately be computed with. The downside is that in many cases the formal proofs are written as an afterthought, are incomplete, or use obtuse syntax. This makes it that the verified proofs are often much more difficult to read than the pen-and-paper proofs, and almost never directly published. In this paper, we will try to remedy that by example. Concretely, we use Agda to model the Lambek-Grishin calculus, a grammar logic with a rich vocabulary of type-forming operations. We then present a verified procedure for cut elimination in this system. Then we briefly outline a CPS translation from proofs in the Lambek-Grishin calculus to programs in Agda. And finally, we will put our system to use in the analysis of a simple example sentence.
An Improved Algorithm for E-Generalization
Venue: arXiv cs.LO 2017
Year: 2017

E-generalization computes common generalizations of given ground terms w.r.t. a given equational background theory E. In 2005 [arXiv:1403.8118], we had presented a computation approach based on standard regular tree grammar algorithms, and a Prolog prototype implementation. In this report, we present algorithmic improvements, prove them correct and complete, and give some details of an efficiency-oriented implementation in C that allows us to handle problems larger by several orders of magnitude.