OpenRaiser/Intern-Atlas huggingface dataset:
A Price Driven Hazard Approach to User Retention
Venue: arXiv cs.SI 2017
Year: 2017

Customer loyalty is crucial for internet services since retaining users of a service to ensure the staying time of the service is of significance for increasing revenue. It demands the retention of customers to be high enough to meet the needs for yielding profit for the internet servers. Besides, the growing of rich purchasing interaction feedback helps in uncovering the inner mechanism of purchasing intent of the customers. In this work, we exploit the rich interaction data of user to build a customers retention evaluation model focusing on the return time of a user to a product. Three aspects, namely the consilience between user and product, the sensitivity of the user to price and the external influence the user might receive, are promoted to effect the purchase intents, which are jointly modeled by a probability model based on Cox's proportional hazard approach. The hazard based model provides benefits in the dynamics in user retention and it can conveniently incorporate covariates in the model. Extensive experiments on real world purchasing data have demonstrated the superiority of the proposed model over state-of-the-art algorithms.
Multi-armed Bandits with Constrained Arms and Hidden States
Venue: arXiv cs.SY 2017
Year: 2017

The problem of rested and restless multi-armed bandits with constrained availability of arms is considered. The states of arms evolve in Markovian manner and the exact states are hidden from the decision maker. First, some structural results on value functions are claimed. Following these results, the optimal policy turns out to be a \textit{threshold policy}. Further, \textit{indexability} of rested bandits is established and index formula is derived. The performance of index policy is illustrated and compared with myopic policy using numerical examples.
A Two-Phase Safe Vehicle Routing and Scheduling Problem: Formulations and Solution Algorithms
Venue: arXiv cs.AI 2017
Year: 2017

We propose a two phase time dependent vehicle routing and scheduling optimization model that identifies the safest routes, as a substitute for the classical objectives given in the literature such as shortest distance or travel time, through (1) avoiding recurring congestions, and (2) selecting routes that have a lower probability of crash occurrences and non-recurring congestion caused by those crashes. In the first phase, we solve a mixed-integer programming model which takes the dynamic speed variations into account on a graph of roadway networks according to the time of day, and identify the routing of a fleet and sequence of nodes on the safest feasible paths. Second phase considers each route as an independent transit path (fixed route with fixed node sequences), and tries to avoid congestion by rescheduling the departure times of each vehicle from each node, and by adjusting the sub-optimal speed on each arc. A modified simulated annealing (SA) algorithm is formulated to solve both complex models iteratively, which is found to be capable of providing solutions in a considerably short amount of time.
Preserving Local and Global Information for Network Embedding
Venue: arXiv cs.SI 2017
Year: 2017

Networks such as social networks, airplane networks, and citation networks are ubiquitous. The adjacency matrix is often adopted to represent a network, which is usually high dimensional and sparse. However, to apply advanced machine learning algorithms to network data, low-dimensional and continuous representations are desired. To achieve this goal, many network embedding methods have been proposed recently. The majority of existing methods facilitate the local information i.e. local connections between nodes, to learn the representations, while completely neglecting global information (or node status), which has been proven to boost numerous network mining tasks such as link prediction and social recommendation. Hence, it also has potential to advance network embedding. In this paper, we study the problem of preserving local and global information for network embedding. In particular, we introduce an approach to capture global information and propose a network embedding framework LOG, which can coherently model {\bf LO}cal and {\bf G}lobal information. Experimental results demonstrate the ability to preserve global information of the proposed framework. Further experiments are conducted to demonstrate the effectiveness of learned representations of the proposed framework.
Formally Secure Compilation of Unsafe Low-Level Components (Extended Abstract)
Venue: arXiv cs.CR 2017
Year: 2017

We propose a new formal criterion for secure compilation, providing strong security guarantees for components written in unsafe, low-level languages with C-style undefined behavior. Our criterion goes beyond recent proposals, which protect the trace properties of a single component against an adversarial context, to model dynamic compromise in a system of mutually distrustful components. Each component is protected from all the others until it receives an input that triggers an undefined behavior, causing it to become compromised and attack the remaining uncompromised components. To illustrate this model, we demonstrate a secure compilation chain for an unsafe language with buffers, procedures, and components, compiled to a simple RISC abstract machine with built-in compartmentalization. The protection guarantees offered by this abstract machine can be achieved at the machine-code level using either software fault isolation or tag-based reference monitoring. We are working on machine-checked proofs showing that this compiler satisfies our secure compilation criterion.
Power Plant Performance Modeling with Concept Drift
Venue: arXiv cs.LG 2017
Year: 2017

Power plant is a complex and nonstationary system for which the traditional machine learning modeling approaches fall short of expectations. The ensemble-based online learning methods provide an effective way to continuously learn from the dynamic environment and autonomously update models to respond to environmental changes. This paper proposes such an online ensemble regression approach to model power plant performance, which is critically important for operation optimization. The experimental results on both simulated and real data show that the proposed method can achieve performance with less than 1% mean average percentage error, which meets the general expectations in field operations.
Online Monotone Games
Venue: arXiv cs.GT 2017
Year: 2017

Algorithmic game theory (AGT) focuses on the design and analysis of algorithms for interacting agents, with interactions rigorously formalized within the framework of games. Results from AGT find applications in domains such as online bidding auctions for web advertisements and network routing protocols. Monotone games are games where agent strategies naturally converge to an equilibrium state. Previous results in AGT have been obtained for convex, socially-convex, or smooth games, but not monotone games. Our primary theoretical contributions are defining the monotone game setting and its extension to the online setting, a new notion of regret for this setting, and accompanying algorithms that achieve sub-linear regret. We demonstrate the utility of online monotone game theory on a variety of problem domains including variational inequalities, reinforcement learning, and generative adversarial networks.
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Venue: arXiv cs.IT 2017
Year: 2017

Synchronization strings are recently introduced by Haeupler and Shahrasbi [HS17a] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm it can transform insertion and deletion errors into standard symbol erasures and corruptions. This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood. Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes. Amazingly, [HS17a] showed that for any error parameter $\varepsilon>0$, synchronization strings of arbitrary length exist over an alphabet whose size depends only on $\varepsilon$. Specifically, they obtained an alphabet size of $O(\varepsilon^{-4})$, as well as a randomized construction that runs in expected time $O(n^5)$. However, it remains an interesting question to find deterministic and more efficient constructions. In this paper, we improve the construction in [HS17a] in three aspects: we achieve a smaller alphabet size, a deterministic construction, and a faster algorithm. Along the way we introduce a new combinatorial object, and establish a new connection between synchronization strings and insdel codes --- such codes can be used in a simple way to construct synchronization strings. This new connection complements the connection found in [HS17a], and may be of independent interest. In an independent work [HS17c], Haeupler and Shahrasbi also give deterministic constructions of synchronization strings over arbitrary length (or even infinite length). Their constructions can achieve linear construction time, but have alphabet size $\varepsilon^{-O(1)}$, which may be larger than ours.
Light-weight place recognition and loop detection using road markings
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose an efficient algorithm for robust place recognition and loop detection using camera information only. Our pipeline purely relies on spatial localization and semantic information of road markings. The creation of the database of road markings sequences is performed online, which makes the method applicable for real-time loop closure for visual SLAM techniques. Furthermore, our algorithm is robust to various weather conditions, occlusions from vehicles, and shadows. We have performed an extensive number of experiments which highlight the effectiveness and scalability of the proposed method.
A Semantically Motivated Approach to Compute ROUGE Scores
Venue: arXiv cs.CL 2017
Year: 2017

ROUGE is one of the first and most widely used evaluation metrics for text summarization. However, its assessment merely relies on surface similarities between peer and model summaries. Consequently, ROUGE is unable to fairly evaluate abstractive summaries including lexical variations and paraphrasing. Exploring the effectiveness of lexical resource-based models to address this issue, we adopt a graph-based algorithm into ROUGE to capture the semantic similarities between peer and model summaries. Our semantically motivated approach computes ROUGE scores based on both lexical and semantic similarities. Experiment results over TAC AESOP datasets indicate that exploiting the lexico-semantic similarity of the words used in summaries would significantly help ROUGE correlate better with human judgments.
Probabilistic Analysis of the Dual-Pivot Quicksort "Count"
Venue: arXiv cs.DS 2017
Year: 2017

Recently, Aumüller and Dietzfelbinger proposed a version of a dual-pivot quicksort, called "Count", which is optimal among dual-pivot versions with respect to the average number of key comparisons required. In this note we provide further probabilistic analysis of "Count". We derive an exact formula for the average number of swaps needed by "Count" as well as an asymptotic formula for the variance of the number of swaps and a limit law. Also for the number of key comparisons the asymptotic variance and a limit law are identified. We also consider both complexity measures jointly and find their asymptotic correlation.
Employing Fusion of Learned and Handcrafted Features for Unconstrained Ear Recognition
Venue: arXiv cs.CV 2017
Year: 2017

We present an unconstrained ear recognition framework that outperforms state-of-the-art systems in different publicly available image databases. To this end, we developed CNN-based solutions for ear normalization and description, we used well-known handcrafted descriptors, and we fused learned and handcrafted features to improve recognition. We designed a two-stage landmark detector that successfully worked under untrained scenarios. We used the results generated to perform a geometric image normalization that boosted the performance of all evaluated descriptors. Our CNN descriptor outperformed other CNN-based works in the literature, specially in more difficult scenarios. The fusion of learned and handcrafted matchers appears to be complementary as it achieved the best performance in all experiments. The obtained results outperformed all other reported results for the UERC challenge, which contains the most difficult database nowadays.
The Design and Implementation of Modern Online Programming Competitions
Venue: arXiv cs.CY 2017
Year: 2017

This paper presents a framework for the implementation of online programming competitions, including a set of principles for the design of the multiplayer game and a practical framework for the construction of the competition environment. The paper presents a successful example competition, the 2016-17 Halite challenge, and briefly mentions a second competition, the Halite II challenge, which launched in October 2017.
Program Synthesis using Abstraction Refinement
Venue: arXiv cs.PL 2017
Year: 2017

We present a new approach to example-guided program synthesis based on counterexample-guided abstraction refinement. Our method uses the abstract semantics of the underlying DSL to find a program $P$ whose abstract behavior satisfies the examples. However, since program $P$ may be spurious with respect to the concrete semantics, our approach iteratively refines the abstraction until we either find a program that satisfies the examples or prove that no such DSL program exists. Because many programs have the same input-output behavior in terms of their abstract semantics, this synthesis methodology significantly reduces the search space compared to existing techniques that use purely concrete semantics. While synthesis using abstraction refinement (SYNGAR) could be implemented in different settings, we propose a refinement-based synthesis algorithm that uses abstract finite tree automata (AFTA). Our technique uses a coarse initial program abstraction to construct an initial AFTA, which is iteratively refined by constructing a proof of incorrectness of any spurious program. In addition to ruling out the spurious program accepted by the previous AFTA, proofs of incorrectness are also useful for ruling out many other spurious programs. We implement these ideas in a framework called \tool. We have used the BLAZE framework to build synthesizers for string and matrix transformations, and we compare BLAZE with existing techniques. Our results for the string domain show that BLAZE compares favorably with FlashFill, a domain-specific synthesizer that is now deployed in Microsoft PowerShell. In the context of matrix manipulations, we compare BLAZE against Prose, a state-of-the-art general-purpose VSA-based synthesizer, and show that BLAZE results in a 90x speed-up over Prose.
Twin Sort Technique
Venue: arXiv cs.DS 2017
Year: 2017

The objective behind the Twin Sort technique is to sort the list of unordered data elements efficiently and to allow efficient and simple arrangement of data elements within the data structure with optimization of comparisons and iterations in the sorting method. This sorting technique effectively terminates the iterations when there is no need of comparison if the elements are all sorted in between the iterations. Unlike Quick sort, Merge sorting technique, this new sorting technique is based on the iterative method of sorting elements within the data structure. So it will be advantageous for optimization of iterations when there is no need for sorting elements. Finally, the Twin Sort technique is more efficient and simple method of arranging elements within a data structure and it is easy to implement when comparing to the other sorting technique. By the introduction of optimization of comparison and iterations, it will never allow the arranging task on the ordered elements.
Optimum Interference Management in Underlay Inband D2D-Enhanced Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

For device-to-device (D2D) communications underlaying a cellular network with uplink resource sharing, both cellular and D2D links cause significant co-channel interference. In this paper, we address the critical issue of interference management in the network considering a practical path loss model incorporating both line-of-sight (LoS) and non-line-of-sight (NLoS) transmissions. To reduce the severe interference caused by active D2D links, we consider a mode selection scheme based on the maximum received signal strength (MRSS) for each user equipment (UE) to control the D2D-to-cellular interference. Specifically, a UE will operate in a cellular mode, only if its received signal strength from the strongest base station (BS) is larger than a threshold beta; otherwise, the UE will operate in a D2D mode. Furthermore, we analyze the performance in terms of the coverage probability and the area spectral efficiency (ASE) for both the cellular network and the D2D one. Analytical results are obtained and the accuracy of the proposed analytical framework is validated through Monte Carol simulations. Through our theoretical and numerical analyses, we quantify the performance gains brought by D2D communications in cellular networks and we find an optimum mode selection threshold beta to maximize the total ASE in the network.
Tracking bitcoin users activity using community detection on a network of weak signals
Venue: arXiv cs.CR 2017
Year: 2017

Bitcoin is a cryptocurrency attracting a lot of interest both from the general public and researchers. There is an ongoing debate on the question of users' anonymity: while the Bitcoin protocol has been designed to ensure that the activity of individual users could not be tracked, some methods have been proposed to partially bypass this limitation. In this article, we show how the Bitcoin transaction network can be studied using complex networks analysis techniques, and in particular how community detection can be efficiently used to re-identify multiple addresses belonging to a same user.
Performance Bounds of Concatenated Polar Coding Schemes
Venue: arXiv cs.IT 2017
Year: 2017

A concatenated coding scheme over binary memoryless symmetric (BMS) channels using a polarization transformation followed by outer sub-codes is analyzed. Achievable error exponents and upper bounds on the error rate are derived. The first bound is obtained using outer codes which are typical linear codes from the ensemble of parity check matrices whose elements are chosen independently and uniformly. As a byproduct of this bound, it determines the required rate split of the total rate to the rates of the outer codes. A lower bound on the error exponent that holds for all BMS channels with a given capacity is then derived. Improved bounds and approximations for finite blocklength codes using channel dispersions (normal approximation), as well as converse and approximate converse results, are also obtained. The bounds are compared to actual simulation results from the literature. For the cases considered, when transmitting over the binary input additive white Gaussian noise channel, there was only a small gap between the normal approximation prediction and the actual error rate of concatenated BCH-polar codes.
Does it matter which search engine is used? A user study using post-task relevance judgments
Venue: arXiv cs.HC 2017
Year: 2017

The objective of this research was to find out how the two search engines Google and Bing perform when users work freely on pre-defined tasks, and judge the relevance of the results immediately after finishing their search session. In a user study, 64 participants conducted two search tasks each, and then judged the results on the following: (1) The quality of the results they selected in their search sessions, (2) The quality of the results they were presented with in their search sessions (but which they did not click on), (3) The quality of the results from the competing search engine for their queries (which they did not see in their search session). We found that users heavily relied on Google, that Google produced more relevant results than Bing, that users were well able to select relevant results from the results lists, and that users judged the relevance of results lower when they regarded a task as difficult and did not find the correct information.
Fixed Price Approximability of the Optimal Gain From Trade
Venue: arXiv cs.GT 2017
Year: 2017

Bilateral trade is a fundamental economic scenario comprising a strategically acting buyer and seller, each holding valuations for the item, drawn from publicly known distributions. A mechanism is supposed to facilitate trade between these agents, if such trade is beneficial. It was recently shown that the only mechanisms that are simultaneously DSIC, SBB, and ex-post IR, are fixed price mechanisms, i.e., mechanisms that are parametrised by a price p, and trade occurs if and only if the valuation of the buyer is at least p and the valuation of the seller is at most p. The gain from trade is the increase in welfare that results from applying a mechanism; here we study the gain from trade achievable by fixed price mechanisms. We explore this question for both the bilateral trade setting, and a double auction setting where there are multiple buyers and sellers. We first identify a fixed price mechanism that achieves a gain from trade of at least 2/r times the optimum, where r is the probability that the seller's valuation does not exceed the buyer's valuation. This extends a previous result by McAfee. Subsequently, we improve this approximation factor in an asymptotic sense, by showing that a more sophisticated rule for setting the fixed price results in an expected gain from trade within a factor O(log(1/r)) of the optimal gain from trade. This is asymptotically the best approximation factor possible. Lastly, we extend our study of fixed price mechanisms to the double auction setting defined by a set of multiple i.i.d. unit demand buyers, and i.i.d. unit supply sellers. We present a fixed price mechanism that achieves a gain from trade that achieves for all epsilon > 0 a gain from trade of at least (1-epsilon) times the expected optimal gain from trade with probability 1 - 2/e^{#T epsilon^2 /2}, where #T is the expected number of trades resulting from the double auction.