OpenRaiser/Intern-Atlas huggingface dataset:
Towards balanced clustering - part 1 (preliminaries)
Venue: arXiv cs.DS 2017
Year: 2017

The article contains a preliminary glance at balanced clustering problems. Basic balanced structures and combinatorial balanced problems are briefly described. A special attention is targeted to various balance/unbalance indices (including some new versions of the indices): by cluster cardinality, by cluster weights, by inter-cluster edge/arc weights, by cluster element structure (for element multi-type clustering). Further, versions of optimization clustering problems are suggested (including multicriteria problem formulations). Illustrative numerical examples describe calculation of balance indices and element multi-type balance clustering problems (including example for design of student teams).
Big Data, Data Science, and Civil Rights
Venue: arXiv cs.CY 2017
Year: 2017

Advances in data analytics bring with them civil rights implications. Data-driven and algorithmic decision making increasingly determine how businesses target advertisements to consumers, how police departments monitor individuals or groups, how banks decide who gets a loan and who does not, how employers hire, how colleges and universities make admissions and financial aid decisions, and much more. As data-driven decisions increasingly affect every corner of our lives, there is an urgent need to ensure they do not become instruments of discrimination, barriers to equality, threats to social justice, and sources of unfairness. In this paper, we argue for a concrete research agenda aimed at addressing these concerns, comprising five areas of emphasis: (i) Determining if models and modeling procedures exhibit objectionable bias; (ii) Building awareness of fairness into machine learning methods; (iii) Improving the transparency and control of data- and model-driven decision making; (iv) Looking beyond the algorithm(s) for sources of bias and unfairness-in the myriad human decisions made during the problem formulation and modeling process; and (v) Supporting the cross-disciplinary scholarship necessary to do all of that well.
A Focal Any-Angle Path-finding Algorithm Based on A* on Visibility Graphs
Venue: arXiv cs.AI 2017
Year: 2017

In this research, we investigate the subject of path-finding. A pruned version of visibility graph based on Candidate Vertices is formulated, followed by a new visibility check technique. Such combination enables us to quickly identify the useful vertices and thus find the optimal path more efficiently. The algorithm proposed is demonstrated on various path-finding cases. The performance of the new technique on visibility graphs is compared to the traditional A* on Grids, Theta* and A* on Visibility Graphs in terms of path length, number of nodes evaluated, as well as computational time. The key algorithmic contribution is that the new approach combines the merits of grid-based method and visibility graph-based method and thus yields better overall performance.
Trimming and Improving Skip-thought Vectors
Venue: arXiv cs.CL 2017
Year: 2017

The skip-thought model has been proven to be effective at learning sentence representations and capturing sentence semantics. In this paper, we propose a suite of techniques to trim and improve it. First, we validate a hypothesis that, given a current sentence, inferring the previous and inferring the next sentence provide similar supervision power, therefore only one decoder for predicting the next sentence is preserved in our trimmed skip-thought model. Second, we present a connection layer between encoder and decoder to help the model to generalize better on semantic relatedness tasks. Third, we found that a good word embedding initialization is also essential for learning better sentence representations. We train our model unsupervised on a large corpus with contiguous sentences, and then evaluate the trained model on 7 supervised tasks, which includes semantic relatedness, paraphrase detection, and text classification benchmarks. We empirically show that, our proposed model is a faster, lighter-weight and equally powerful alternative to the original skip-thought model.
Adaptive Interference Removal for Un-coordinated Radar/Communication Co-existence
Venue: arXiv cs.SY 2017
Year: 2017

Most existing approaches to co-existing communication/radar systems assume that the radar and communication systems are coordinated, i.e., they share information, such as relative position, transmitted waveforms and channel state. In this paper, we consider an un-coordinated scenario where a communication receiver is to operate in the presence of a number of radars, of which only a sub-set may be active, which poses the problem of estimating the active waveforms and the relevant parameters thereof, so as to cancel them prior to demodulation. Two algorithms are proposed for such a joint waveform estimation/data demodulation problem, both exploiting sparsity of a proper representation of the interference and of the vector containing the errors of the data block, so as to implement an iterative joint interference removal/data demodulation process. The former algorithm is based on classical on-grid compressed sensing (CS), while the latter forces an atomic norm (AN) constraint: in both cases the radar parameters and the communication demodulation errors can be estimated by solving a convex problem. We also propose a way to improve the efficiency of the AN-based algorithm. The performance of these algorithms are demonstrated through extensive simulations, taking into account a variety of conditions concerning both the interferers and the respective channel states.
Toward Optimal Run Racing: Application to Deep Learning Calibration
Venue: arXiv cs.LG 2017
Year: 2017

This paper aims at one-shot learning of deep neural nets, where a highly parallel setting is considered to address the algorithm calibration problem - selecting the best neural architecture and learning hyper-parameter values depending on the dataset at hand. The notoriously expensive calibration problem is optimally reduced by detecting and early stopping non-optimal runs. The theoretical contribution regards the optimality guarantees within the multiple hypothesis testing framework. Experimentations on the Cifar10, PTB and Wiki benchmarks demonstrate the relevance of the approach with a principled and consistent improvement on the state of the art with no extra hyper-parameter.
Simulations and Antichains for Efficient Handling of Finite Automata
Venue: arXiv cs.FL 2017
Year: 2017

This thesis is focused on techniques for finite automata and their use in practice, with the main emphasis on nondeterministic tree automata. This concerns namely techniques for size reduction and language inclusion testing, which are two problems that are crucial for many applications of tree automata. For size reduction of tree automata, we adapt the simulation quotient technique that is well established for finite word automata. We give efficient algorithms for computing tree automata simulations and we also introduce a new type of relation that arises from a combination of tree automata downward and upward simulation and that is very well suited for quotienting. The combination principle is relevant also for word automata. We then generalise the so called antichain universality and language inclusion checking technique developed originally for finite word automata for tree automata. Subsequently, we improve the antichain technique for both word and tree automata by combining it with the simulation-based inclusion checking techniques, significantly improving efficiency of the antichain method. We then show how the developed reduction and inclusion checking methods improve the method of abstract regular tree model checking, the method that was the original motivation for starting the work on tree automata. Both the reduction and the language inclusion methods are based on relatively simple and general principles that can be further extended for other types of automata and related formalisms. An example is our adaptation of the reduction methods for alternating Büchi automata, which results in an efficient alternating automata size reduction technique.
Proposal for a High Precision Tensor Processing Unit
Venue: arXiv cs.AR 2017
Year: 2017

This whitepaper proposes the design and adoption of a new generation of Tensor Processing Unit which has the performance of Google's TPU, yet performs operations on wide precision data. The new generation TPU is made possible by implementing arithmetic circuits which compute using a new general purpose, fractional arithmetic based on the residue number system.
On Hash-Based Work Distribution Methods for Parallel Best-First Search
Venue: arXiv cs.AI 2017
Year: 2017

Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.
Maximum Area Rectangle Separating Red and Blue Points
Venue: arXiv cs.CG 2017
Year: 2017

Given a set R of n red points and a set B of m blue points, we study the problem of finding a rectangle that contains all the red points, the minimum number of blue points and has the largest area. We call such rectangle a maximum separating rectangle. We address the planar, axis-aligned (2D) version, and present an O(mlogm+n) time, O(m+n) space algorithm. The running time reduces to O(m + n) if the points are pre-sorted by one of the coordinates. We further prove that our algorithm is optimal in the decision model of computation.
A Framework for Exploring and Evaluating Mechanics in Human Computation Games
Venue: arXiv cs.HC 2017
Year: 2017

Human computation games (HCGs) are a crowdsourcing approach to solving computationally-intractable tasks using games. In this paper, we describe the need for generalizable HCG design knowledge that accommodates the needs of both players and tasks. We propose a formal representation of the mechanics in HCGs, providing a structural breakdown to visualize, compare, and explore the space of HCG mechanics. We present a methodology based on small-scale design experiments using fixed tasks while varying game elements to observe effects on both the player experience and the human computation task completion. Finally we discuss applications of our framework using comparisons of prior HCGs and recent design experiments. Ultimately, we wish to enable easier exploration and development of HCGs, helping these games provide meaningful player experiences while solving difficult problems.
Educational Data Mining and Learning Analytics - Educational Assistance for Teaching and Learning
Venue: arXiv cs.SY 2017
Year: 2017

Teaching and Learning process of an educational institution needs to be monitored and effectively analysed for enhancement. Teaching and Learning is a vital element for an educational institution. It is also one of the criteria set by majority of the Accreditation Agencies around the world. Learning analytics and Educational Data Mining are relatively new. Learning analytics refers to the collection of large volume of data about students in an educational setting and to analyse the data to predict the students' future performance and identify risk. Educational Data Mining (EDM) is develops methods to analyse the data produced by the students in educational settings and these methods helps to understand the students and the setting where they learn. Aim of this research is to collect large collection of data on students' performance in their assessment to discover the students at risk of failing the final exam. This analysis will help to understand how the students are progressing. The proposed research aimed to utilize the result of the analysis to identify the students at risk and provide recommendations for improvement. The proposed research aimed to collect and analyse the result of the assessment at the course level to enhance the teaching and learning process. The research aimed to discuss two feature selection techniques namely information gain and gain ratio and adopted to use gain ratio as the feature selection technique.
Explicit Lower Bounds on the Outage Probability of Integer Forcing over Nrx2 Channels
Venue: arXiv cs.IT 2017
Year: 2017

The performance of integer-forcing equalization for communication over the compound multiple-input multipleoutput channel is investigated. An upper bound on the resulting outage probability as a function of the gap to capacity has been derived previously, assuming a random precoding matrix drawn from the circular unitary ensemble is applied prior to transmission. In the present work a simple and explicit lower bound on the worst-case outage probability is derived for the case of a system with two transmit antennas and two or more receive antennas, leveraging the properties of the Jacobi ensemble. The derived lower bound is also extended to random space-time precoding, and may serve as a useful benchmark for assessing the relative merits of various algebraic space-time precoding schemes. We further show that the lower bound may be adapted to the case of a $1 \times N_t$ system. As an application of this, we derive closed-form bounds for the symmetric-rate capacity of the Rayleigh fading multiple-access channel where all terminals are equipped with a single antenna. Lastly, we demonstrate that the integer-forcing equalization coupled with distributed space-time coding is able to approach these bounds.
Decentralized Certificate Authorities
Venue: arXiv cs.CR 2017
Year: 2017

The security of TLS depends on trust in certificate authorities, and that trust stems from their ability to protect and control the use of a private signing key. The signing key is the key asset of a certificate authority (CA), and its value is based on trust in the corresponding public key which is primarily distributed by browser vendors. Compromise of a CA private key represents a single point-of-failure that could have disastrous consequences, so CAs go to great lengths to attempt to protect and control the use of their private keys. Nevertheless, keys are sometimes compromised and may be misused accidentally or intentionally by insiders. We propose splitting a CA's private key among multiple parties, and producing signatures using a generic secure multi-party computation protocol that never exposes the actual signing key. This could be used by a single CA to reduce the risk that its signing key would be compromised or misused. It could also enable new models for certificate generation, where multiple CAs would need to agree and cooperate before a new certificate can be generated, or even where certificate generation would require cooperation between a CA and the certificate recipient (subject). Although more efficient solutions are possible with custom protocols, we demonstrate the feasibility of implementing a decentralized CA using a generic two-party secure computation protocol with an evaluation of a prototype implementation that uses secure two-party computation to generate certificates signed using ECDSA on curve secp192k1.
Modeling Multi-Object Configurations via Medial/Skeletal Linking Structures
Venue: arXiv cs.CV 2017
Year: 2017

We introduce a method for modeling a configuration of objects in 2D or 3D images using a mathematical "skeletal linking structure" which will simultaneously capture the individual shape features of the objects and their positional information relative to one another. The objects may either have smooth boundaries and be disjoint from the others or share common portions of their boundaries with other objects in a piecewise smooth manner. These structures include a special class of "Blum medial linking structures," which are intrinsically associated to the configuration and build upon the Blum medial axes of the individual objects. We give a classification of the properties of Blum linking structures for generic configurations. The skeletal linking structures add increased flexibility for modeling configurations of objects by relaxing the Blum conditions and they extend in a minimal way the individual "skeletal structures" which have been previously used for modeling individual objects and capturing their geometric properties. This allows for the mathematical methods introduced for single objects to be significantly extended to the entire configuration of objects. These methods not only capture the internal shape structures of the individual objects but also the external structure of the neighboring regions of the objects.
SU-RUG at the CoNLL-SIGMORPHON 2017 shared task: Morphological Inflection with Attentional Sequence-to-Sequence Models
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the Stockholm University/University of Groningen (SU-RUG) system for the SIGMORPHON 2017 shared task on morphological inflection. Our system is based on an attentional sequence-to-sequence neural network model using Long Short-Term Memory (LSTM) cells, with joint training of morphological inflection and the inverse transformation, i.e. lemmatization and morphological analysis. Our system outperforms the baseline with a large margin, and our submission ranks as the 4th best team for the track we participate in (task 1, high-resource).
A Minimal Set of Shannon-type Inequalities for Functional Dependence Structures
Venue: arXiv cs.IT 2017
Year: 2017

The minimal set of Shannon-type inequalities (referred to as elemental inequalities), plays a central role in determining whether a given inequality is Shannon-type. Often, there arises a situation where one needs to check whether a given inequality is a constrained Shannon-type inequality. Another important application of elemental inequalities is to formulate and compute the Shannon outer bound for multi-source multi-sink network coding capacity. Under this formulation, it is the region of feasible source rates subject to the elemental inequalities and network coding constraints that is of interest. Hence it is of fundamental interest to identify the redundancies induced amongst elemental inequalities when given a set of functional dependence constraints. In this paper, we characterize a minimal set of Shannon-type inequalities when functional dependence constraints are present.
Signal Processing for Gigabit-Rate Wireline Communications
Venue: arXiv cs.IT 2017
Year: 2017

Signal processing played an important role in improving the quality of communications over copper cables in earlier DSL technologies. Even more powerful signal processing techniques are required to enable a gigabit per second data rate in the upcoming G.fast standard. This new standard is different from its predecessors in many respects. In particular, G.fast will use a significantly higher bandwidth. At such a high bandwidth, crosstalk between different lines in a binder will reach unprecedented levels, which are beyond the capabilities of most efficient techniques for interference mitigation. In this article, we survey the state of the art and research challenges in the design of signal processing algorithms for the G.fast system, with a focus on novel research approaches and design considerations for efficient interference mitigation in G.fast systems. We also detail relevant VDSL techniques and points out their strengths and limitations for the G.fast system.
Engineering Inertial and Primary-frequency Response for Distributed Energy Resources
Venue: arXiv cs.SY 2017
Year: 2017

We propose a framework to engineer synthetic-inertia and droop-control parameters for distributed energy resources (DERs) so that the system frequency in a network composed of DERs and synchronous generators conforms to prescribed transient and steady-state performance specifications. Our approach is grounded in a second-order lumped-parameter model that captures the dynamics of synchronous generators and frequency-responsive DERs endowed with inertial and droop control. A key feature of this reduced-order model is that its parameters can be related to those of the originating higher-order dynamical model. This allows one to systematically design the DER inertial and droop-control coefficients leveraging classical frequency-domain response characteristics of second-order systems. Time-domain simulations validate the accuracy of the model-reduction method and demonstrate how DER controllers can be designed to meet steady-state-regulation and transient-performance specifications.
User Tolerance and Self-Regulation in Congestion Control
Venue: arXiv cs.NI 2017
Year: 2017

In response to poor quality of service (QoS), users self-regulate, i.e. they immediately release bandwidth and abandon network. However, there are studies that show users are willing to tolerate poor QoS for some time to evaluate if network performance will improve before abandoning the network. In this paper, we investigate how users willingness to wait for improved QoS may influence network activities, such as network pricing, bandwidth allocation, network revenue, and performance. We develop and employ a self-regulation model that includes user evaluation of QoS before deciding to abandon or stay in the network. This model considers these two factors: user tolerance of low QoS and the price per unit a user is willing to pay. Our investigation uncovers a double edged problem network may be populated with lower paying users, who are also dissatisfied. These lower paying users drive the price higher than the price produced by conventional solution for network congestion. This leads to our proposal for a market informed congestion control scheme, where network resolves congestion based on user profile that is defined by their ability to pay and demand for bandwidth.
Tackling Over-pruning in Variational Autoencoders
Venue: arXiv cs.LG 2017
Year: 2017

Variational autoencoders (VAE) are directed generative models that learn factorial latent variables. As noted by Burda et al. (2015), these models exhibit the problem of factor over-pruning where a significant number of stochastic factors fail to learn anything and become inactive. This can limit their modeling power and their ability to learn diverse and meaningful latent representations. In this paper, we evaluate several methods to address this problem and propose a more effective model-based approach called the epitomic variational autoencoder (eVAE). The so-called epitomes of this model are groups of mutually exclusive latent factors that compete to explain the data. This approach helps prevent inactive units since each group is pressured to explain the data. We compare the approaches with qualitative and quantitative results on MNIST and TFD datasets. Our results show that eVAE makes efficient use of model capacity and generalizes better than VAE.