OpenRaiser/Intern-Atlas huggingface dataset:
A Cross Entropy based Optimization Algorithm with Global Convergence Guarantees
Venue: arXiv cs.AI 2018
Year: 2018

The cross entropy (CE) method is a model based search method to solve optimization problems where the objective function has minimal structure. The Monte-Carlo version of the CE method employs the naive sample averaging technique which is inefficient, both computationally and space wise. We provide a novel stochastic approximation version of the CE method, where the sample averaging is replaced with incremental geometric averaging. This approach can save considerable computational and storage costs. Our algorithm is incremental in nature and possesses additional attractive features such as accuracy, stability, robustness and convergence to the global optimum for a particular class of objective functions. We evaluate the algorithm on a variety of global optimization benchmark problems and the results obtained corroborate our theoretical findings.
Constraint Estimation and Derivative-Free Recovery for Robot Learning from Demonstrations
Venue: arXiv cs.RO 2018
Year: 2018

Learning from human demonstrations can facilitate automation but is risky because the execution of the learned policy might lead to collisions and other failures. Adding explicit constraints to avoid unsafe states is generally not possible when the state representations are complex. Furthermore, enforcing these constraints during execution of the learned policy can be challenging in environments where dynamics are difficult to model such as push mechanics in grasping. In this paper, we propose Derivative-Free Recovery (DFR), a two-phase method for generating robust policies from demonstrations in robotic manipulation tasks where the system comes to rest at each time step. In the first phase, we use support estimation of supervisor demonstrations and treat the support as implicit constraints on states. We also propose a time-varying modification for sequential tasks. In the second phase, we use this support estimate to derive a switching policy that employs the learned policy in the interior of the support and switches to a recovery policy to steer the robot away from the boundary of the support if it drifts too close. We present additional conditions, which linearly bound the difference in state at each time step by the magnitude of control, allowing us to prove that the robot will not violate the constraints using the recovery policy. A simulated pushing task in MuJoCo suggests that DFR can reduce collisions by 83\%. On a physical line tracking task using a da Vinci Surgical Robot and a moving Stewart platform, DFR reduced collisions by 84\%.
Understanding Web Archiving Services and Their (Mis)Use on Social Media
Venue: arXiv cs.CY 2018
Year: 2018

Web archiving services play an increasingly important role in today's information ecosystem, by ensuring the continuing availability of information, or by deliberately caching content that might get deleted or removed. Among these, the Wayback Machine has been proactively archiving, since 2001, versions of a large number of Web pages, while newer services like archive.is allow users to create on-demand snapshots of specific Web pages, which serve as time capsules that can be shared across the Web. In this paper, we present a large-scale analysis of Web archiving services and their use on social media, shedding light on the actors involved in this ecosystem, the content that gets archived, and how it is shared. We crawl and study: 1) 21M URLs from archive.is, spanning almost two years, and 2) 356K archive.is plus 391K Wayback Machine URLs that were shared on four social networks: Reddit, Twitter, Gab, and 4chan's Politically Incorrect board (/pol/) over 14 months. We observe that news and social media posts are the most common types of content archived, likely due to their perceived ephemeral and/or controversial nature. Moreover, URLs of archiving services are extensively shared on "fringe" communities within Reddit and 4chan to preserve possibly contentious content. Lastly, we find evidence of moderators nudging or even forcing users to use archives, instead of direct links, for news sources with opposing ideologies, potentially depriving them of ad revenue.
'It's Reducing a Human Being to a Percentage'; Perceptions of Justice in Algorithmic Decisions
Venue: arXiv cs.HC 2018
Year: 2018

Data-driven decision-making consequential to individuals raises important questions of accountability and justice. Indeed, European law provides individuals limited rights to 'meaningful information about the logic' behind significant, autonomous decisions such as loan approvals, insurance quotes, and CV filtering. We undertake three experimental studies examining people's perceptions of justice in algorithmic decision-making under different scenarios and explanation styles. Dimensions of justice previously observed in response to human decision-making appear similarly engaged in response to algorithmic decisions. Qualitative analysis identified several concerns and heuristics involved in justice perceptions including arbitrariness, generalisation, and (in)dignity. Quantitative analysis indicates that explanation styles primarily matter to justice perceptions only when subjects are exposed to multiple different styles---under repeated exposure of one style, scenario effects obscure any explanation effects. Our results suggests there may be no 'best' approach to explaining algorithmic decisions, and that reflection on their automated nature both implicates and mitigates justice dimensions.
Multilayer Network Planning - A Practical Perspective
Venue: arXiv cs.NI 2018
Year: 2018

The paper presents a pragmatic and practical multilayer network planning approach based on a candidate lightpath auxiliary graph model. The paper discusses, how this approach can be applied to offline network planning as well as dynamic planning and provisioning of services.
Lower Bounds for Synchronizing Word Lengths in Partial Automata
Venue: arXiv cs.FL 2018
Year: 2018

It was conjectured by Černý in 1964, that a synchronizing DFA on $n$ states always has a synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reaching this bound was only given for $n \leq 5$, and with bounds on the number of symbols for $n \leq 12$. Here we give the full analysis for $n \leq 7$, without bounds on the number of symbols. For PFAs (partial automata) on $\leq 7$ states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n-1)^2$ for $n \geq 4$. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on $\leq 10$ states and two symbols we investigate all occurring synchronizing word lengths. We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of $n$. For $n=6,7,8,9$, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than $(n-1)^2$, although still quadratic. Based on string rewriting, for arbitrary size we construct a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions. We give a transformation of this PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive. Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.
Deep Learning Works in Practice. But Does it Work in Theory?
Venue: arXiv cs.AI 2018
Year: 2018

Deep learning relies on a very specific kind of neural networks: those superposing several neural layers. In the last few years, deep learning achieved major breakthroughs in many tasks such as image analysis, speech recognition, natural language processing, and so on. Yet, there is no theoretical explanation of this success. In particular, it is not clear why the deeper the network, the better it actually performs. We argue that the explanation is intimately connected to a key feature of the data collected from our surrounding universe to feed the machine learning algorithms: large non-parallelizable logical depth. Roughly speaking, we conjecture that the shortest computational descriptions of the universe are algorithms with inherently large computation times, even when a large number of computers are available for parallelization. Interestingly, this conjecture, combined with the folklore conjecture in theoretical computer science that $ P \neq NC$, explains the success of deep learning.
Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time
Venue: arXiv cs.RO 2018
Year: 2018

Let $G = (V, E)$ be an $m_1 \times \ldots \times m_k$ grid. Assuming that each $v \in V$ is occupied by a robot and a robot may move to a neighboring vertex in a step via synchronized rotations along cycles of $G$, we first establish that the arbitrary reconfiguration of labeled robots on $G$ can be performed in $O(k\sum_i m_i)$ makespan and requires $O(|V|^2)$ running time in the worst case and $o(|V|^2)$ when $G$ is non-degenerate (in the current context, a grid is degenerate if it is nearly one dimensional). The resulting algorithm, iSAG, provides average case $O(1)$-approximate (i.e., constant-factor) time optimality guarantee. When all dimensions are of similar size $O(|V|^{\frac{1}{k}})$, the running time of iSAG approaches a linear $O(|V|)$. Define $d_g(p)$ as the largest distance between individual initial and goal configurations over all robots for a given problem instance $p$, building on iSAG, we develop the PartitionAndFlow (PAF) algorithm that computes $O(d_g(p))$ makespan solutions for arbitrary fixed $k \ge 2$, using mostly $o(|V|^2)$ running time. PAF provides worst case $O(1)$-approximation regarding solution time optimality. We note that the worst case running time for the problem is $Ω(|V|^2)$.
New Size Hierarchies for Two Way Automata
Venue: arXiv cs.FL 2018
Year: 2018

We introduce a new type of nonuniform two--way automaton that can use a different transition function for each tape square. We also enhance this model by allowing to shuffle the given input at the beginning of the computation. Then we present some hierarchy and incomparability results on the number of states for the types of deterministic, nondeterministic, and bounded-error probabilistic models. For this purpose, we provide some lower bounds for all three models based on the numbers of subfunctions and we define two witness functions.
Recognising and Generating Terms using Derivatives of Parsing Expression Grammars
Venue: arXiv cs.PL 2018
Year: 2018

Grammar-based sentence generation has been thoroughly explored for Context-Free Grammars (CFGs), but remains unsolved for recognition-based approaches such as Parsing Expression Grammars (PEGs). Lacking tool support, language designers using PEGs have difficulty predicting the behaviour of their parsers. In this paper, we extend the idea of derivatives, originally formulated for regular expressions, to PEGs. We then present a novel technique for sentence generation based on derivatives, applicable to any grammatical formalism for which the derivative can be defined--now including PEGs. Finally, we propose applying derivatives more generally to other problems facing language designers and implementers.
Deep Predictive Models in Interactive Music
Venue: arXiv cs.SD 2018
Year: 2018

Musical performance requires prediction to operate instruments, to perform in groups and to improvise. In this paper, we investigate how a number of digital musical instruments (DMIs), including two of our own, have applied predictive machine learning models that assist users by predicting unknown states of musical processes. We characterise these predictions as focussed within a musical instrument, at the level of individual performers, and between members of an ensemble. These models can connect to existing frameworks for DMI design and have parallels in the cognitive predictions of human musicians. We discuss how recent advances in deep learning highlight the role of prediction in DMIs, by allowing data-driven predictive models with a long memory of past states. The systems we review are used to motivate musical use-cases where prediction is a necessary component, and to highlight a number of challenges for DMI designers seeking to apply deep predictive models in interactive music systems of the future.
Comments on "Dual-rail asynchronous logic multi-level implementation"
Venue: arXiv cs.ET 2018
Year: 2018

In this research communication, we comment on "Dual-rail asynchronous logic multi-level implementation" [Integration, the VLSI Journal 47 (2014) 148-159] by expounding the problematic issues, and provide some clarifications on delay-insensitivity, robust asynchronous logic, multi-level decomposition, and physical implementation.
Redundancy of unbounded memory Markov classes with continuity conditions
Venue: arXiv cs.IT 2018
Year: 2018

We study the redundancy of universally compressing strings $X_1,\dots, X_n$ generated by a binary Markov source $p$ without any bound on the memory. To better understand the connection between compression and estimation in the Markov regime, we consider a class of Markov sources restricted by a continuity condition. In the absence of an upper bound on memory, the continuity condition implies that $p(X_0|X^{-1}_{-m})$ gets closer to the true probability $p(X_0|X_{-\infty}^{-1})$ as $m$ increases, rather than vary around arbitrarily. For such sources, we prove asymptotically matching upper and lower bounds on the redundancy. In the process, we identify what sources in the class matter the most from a redundancy perspective.
Throughput Analysis of IEEE 802.11 Multi-hop Wireless Networks with Routing Consideration: A General Framework
Venue: arXiv cs.NI 2018
Year: 2018

The end-to-end throughput of multi-hop communication in wireless ad hoc networks is affected by the conflict between forwarding nodes. It has been shown that sending more packets than maximum achievable end-to-end throughput not only fails to increase throughput, but also decreases throughput owing to high contention and collision. Accordingly, it is of crucial importance for a source node to know the maximum end-to-end throughput. The end-to-end throughput depends on multiple factors, such as physical layer limitations, MAC protocol properties, routing policy and nodes distribution. There have been many studies on analytical modeling of end-to-end throughput but none of them has taken routing policy and nodes distribution as well as MAC layer altogether into account. In this paper, the end-to-end throughput with perfect MAC layer is obtained based on routing policy and nodes distribution in one and two dimensional networks. Then, imperfections of IEEE 802:11 protocol is added to the model to obtain precise value. An exhaustive simulation is also made to validate the proposed models using NS2 simulator. Results show that if the distribution to the next hop for a particular routing policy is known, our methodology can obtain the maximum end-to-end throughput precisely.
Perceptual Compressive Sensing
Venue: arXiv cs.CV 2018
Year: 2018

Compressive sensing (CS) works to acquire measurements at sub-Nyquist rate and recover the scene images. Existing CS methods always recover the scene images in pixel level. This causes the smoothness of recovered images and lack of structure information, especially at a low measurement rate. To overcome this drawback, in this paper, we propose perceptual CS to obtain high-level structured recovery. Our task no longer focuses on pixel level. Instead, we work to make a better visual effect. In detail, we employ perceptual loss, defined on feature level, to enhance the structure information of the recovered images. Experiments show that our method achieves better visual results with stronger structure information than existing CS methods at the same measurement rate.
Machine learning and evolutionary techniques in interplanetary trajectory design
Venue: arXiv cs.NE 2018
Year: 2018

After providing a brief historical overview on the synergies between artificial intelligence research, in the areas of evolutionary computations and machine learning, and the optimal design of interplanetary trajectories, we propose and study the use of deep artificial neural networks to represent, on-board, the optimal guidance profile of an interplanetary mission. The results, limited to the chosen test case of an Earth-Mars orbital transfer, extend the findings made previously for landing scenarios and quadcopter dynamics, opening a new research area in interplanetary trajectory planning.
Clustering and Unsupervised Anomaly Detection with L2 Normalized Deep Auto-Encoder Representations
Venue: arXiv cs.LG 2018
Year: 2018

Clustering is essential to many tasks in pattern recognition and computer vision. With the advent of deep learning, there is an increasing interest in learning deep unsupervised representations for clustering analysis. Many works on this domain rely on variants of auto-encoders and use the encoder outputs as representations/features for clustering. In this paper, we show that an l2 normalization constraint on these representations during auto-encoder training, makes the representations more separable and compact in the Euclidean space after training. This greatly improves the clustering accuracy when k-means clustering is employed on the representations. We also propose a clustering based unsupervised anomaly detection method using l2 normalized deep auto-encoder representations. We show the effect of l2 normalization on anomaly detection accuracy. We further show that the proposed anomaly detection method greatly improves accuracy compared to previously proposed deep methods such as reconstruction error based anomaly detection.
Towards Reliable (and Efficient) Job Executions in a Practical Geo-distributed Data Analytics System
Venue: arXiv cs.DC 2018
Year: 2018

Geo-distributed data analytics are increasingly common to derive useful information in large organisations. Naive extension of existing cluster-scale data analytics systems to the scale of geo-distributed data centers faces unique challenges including WAN bandwidth limits, regulatory constraints, changeable/unreliable runtime environment, and monetary costs. Our goal in this work is to develop a practical geo-distribued data analytics system that (1) employs an intelligent mechanism for jobs to efficiently utilize (adjust to) the resources (changeable environment) across data centers; (2) guarantees the reliability of jobs due to the possible failures; and (3) is generic and flexible enough to run a wide range of data analytics jobs without requiring any changes. To this end, we present a new, general geo-distributed data analytics system, HOUTU, that is composed of multiple autonomous systems, each operating in a sovereign data center. HOUTU maintains a job manager (JM) for a geo-distributed job in each data center, so that these replicated JMs could individually and cooperatively manage resources and assign tasks. Our experiments on the prototype of HOUTU running across four Alibaba Cloud regions show that HOUTU provides nearly efficient job performance as in the existing centralized architecture, and guarantees reliable job executions when facing failures.
A Nonparametric Delayed Feedback Model for Conversion Rate Prediction
Venue: arXiv cs.LG 2018
Year: 2018

Predicting conversion rates (CVRs) in display advertising (e.g., predicting the proportion of users who purchase an item (i.e., a conversion) after its corresponding ad is clicked) is important when measuring the effects of ads shown to users and to understanding the interests of the users. There is generally a time delay (i.e., so-called {\it delayed feedback}) between the ad click and conversion. Owing to the delayed feedback, samples that are converted after an observation period may be treated as negative. To overcome this drawback, CVR prediction assuming that the time delay follows an exponential distribution has been proposed. In practice, however, there is no guarantee that the delay is generated from the exponential distribution, and the best distribution with which to represent the delay depends on the data. In this paper, we propose a nonparametric delayed feedback model for CVR prediction that represents the distribution of the time delay without assuming a parametric distribution, such as an exponential or Weibull distribution. Because the distribution of the time delay is modeled depending on the content of an ad and the features of a user, various shapes of the distribution can be represented potentially. In experiments, we show that the proposed model can capture the distribution for the time delay on a synthetic dataset, even when the distribution is complicated. Moreover, on a real dataset, we show that the proposed model outperforms the existing method that assumes an exponential distribution for the time delay in terms of conversion rate prediction.
A Semantic Model for Historical Manuscripts
Venue: arXiv cs.AI 2018
Year: 2018

The study and publication of historical scientific manuscripts are com- plex tasks that involve, among others, the explicit representation of the text mean- ings and reasoning on temporal entities. In this paper we present the first results of an interdisciplinary project dedicated to the study of Saussure's manuscripts. These results aim to fulfill requirements elaborated with Saussurean humanists. They comprise a model for the representation of time-varying statements and time-varying domain knowledge (in particular terminologies) as well as imple- mentation techniques for the semantic indexing of manuscripts and for temporal reasoning on knowledge extracted from the manuscripts.
Digitalization of Swedish Government Agencies - A Perspective Through the Lens of a Software Development Census
Venue: arXiv cs.SE 2018
Year: 2018

Software engineering is at the core of the digitalization of society. Ill-informed decisions can have major consequences, as made evident in the 2017 government crisis in Sweden, originating in a data breach caused by an outsourcing deal made by the Swedish Transport Agency. Many Government Agencies (GovAgs) in Sweden are rapidly undergoing a digital transition, thus it is important to overview how widespread, and mature, software development is in this part of the public sector. We present a software development census of Swedish GovAgs, complemented by document analysis and a survey. We show that 39.2% of the GovAgs develop software internally, some matching the number of developers in large companies. Our findings suggest that the development largely resembles private sector counterparts, and that established best practices are implemented. Still, we identify improvement potential in the areas of strategic sourcing, openness, collaboration across GovAgs, and quality requirements. The Swedish Government has announced the establishment of a new digitalization agency next year, and our hope is that the software engineering community will contribute its expertise with a clear voice.
State-Adaptive Coded Caching for Symmetric Broadcast Channels
Venue: arXiv cs.IT 2018
Year: 2018

Coded-caching delivery is considered over a symmetric noisy broadcast channel whose state is unknown at the transmitter during the cache placement phase. In particular, the delivery phase is modeled by a state-dependent broadcast channel where the state remains constant over each transmission block and is learned by the transmitter (and the receivers) only at the beginning of each block. A state-adaptive coded caching scheme is proposed that improves either on rate or decoding latency over two baseline schemes that are based on standard coded caching.