OpenRaiser/Intern-Atlas huggingface dataset:
Management of Cascading Outage Risk Based on Risk Gradient and Markovian Tree Search
Venue: arXiv cs.SY 2017
Year: 2017

Since cascading outages are major threats to power systems, it is important to reduce the risk of potential cascading outages. In this paper, a risk management method of cascading outages based on Markovian tree search is proposed. With the tree expansion on the cascading outage risk, risk gradient is computed efficiently by a forward-backward tree search scheme with good convergence, and it is then employed in an optimization model to minimize control cost while effectively reducing the cascading outage risk. To overcome the limitation with linearization in computing risk gradient, an iterative risk management (IRM) approach is further developed. Tests on the RTS-96 3-area system verify the accuracy of the computed risk gradient and its effectiveness for risk reduction. Time performance of the proposed IRM approach is tested on the RTS-96 system, a 410-bus US-Canada northeast system and a 1354-bus Mid-European system, and demonstrates its potentials for decision support on practical power systems online or on hourly basis.
Subspace Identification with Multiple Data Records: unlocking the archive
Venue: arXiv cs.SY 2017
Year: 2017

We develop an approach to subspace system identification using multiple data records and present a simple rank-based test for the adequacy of these data for fitting the unique linear, noise-free, dynamic model of prescribed state-vector, input-vector and output-vector dimensions. The approach is motivated by the prospect of sorting through archives of operational data and extracting a sequence of not-necessarily-contiguous data records individually insufficient for providing identifiability but collectively making this possible. The test of identifiability then becomes the sorting criterion for accepting or rejecting new data records. En passant, the familiar Hankel structure of the data matrices of subspace system identification is reinterpreted and revised.
0/1/all CSPs, Half-Integral $A$-path Packing, and Linear-Time FPT Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP relaxations. In other words, starting with a half-integral optimal solution to an LP relaxation, we assign integral values to variables one-by-one by branch and bound. This technique is general and the resulting time complexity has a low dependency on the parameter. However, the time complexity often becomes a large polynomial in the input size because we need to compute half-integral optimal LP solutions. In this paper, we address this issue by providing an $O(km)$-time algorithm for solving the LPs arising from various FPT problems, where $k$ is the optimal value and $m$ is the number of edges/constraints. Our algorithm is based on interesting connections among 0/1/all constraints, which has been studied in the field of constraints satisfaction, $A$-path packing, which has been studied in the field of combinatorial optimization, and the LPs used in FPT algorithms. With the aid of this algorithm, we obtain improved FPT algorithms for various problems, including Group Feedback Vertex Set, Subset Feedback Vertex Set, Node Multiway Cut, Node Unique Label Cover, and Non-monochromatic Cycle Transversal. The obtained running time for each of these problems is linear in the input size and has the current smallest dependency on the parameter. In particular, these algorithms are the first linear-time FPT algorithms for problems including Group Feedback Vertex Set and Non-monochromatic Cycle Transversal.
Automatic Liver Lesion Detection using Cascaded Deep Residual Networks
Venue: arXiv cs.CV 2017
Year: 2017

Automatic segmentation of liver lesions is a fundamental requirement towards the creation of computer aided diagnosis (CAD) and decision support systems (CDS). Traditional segmentation approaches depend heavily upon hand-crafted features and a priori knowledge of the user. As such, these methods are difficult to adopt within a clinical environment. Recently, deep learning methods based on fully convolutional networks (FCNs) have been successful in many segmentation problems primarily because they leverage a large labelled dataset to hierarchically learn the features that best correspond to the shallow visual appearance as well as the deep semantics of the areas to be segmented. However, FCNs based on a 16 layer VGGNet architecture have limited capacity to add additional layers. Therefore, it is challenging to learn more discriminative features among different classes for FCNs. In this study, we overcome these limitations using deep residual networks (ResNet) to segment liver lesions. ResNet contain skip connections between convolutional layers, which solved the problem of the training degradation of training accuracy in very deep networks and thereby enables the use of additional layers for learning more discriminative features. In addition, we achieve more precise boundary definitions through a novel cascaded ResNet architecture with multi-scale fusion to gradually learn and infer the boundaries of both the liver and the liver lesions. Our proposed method achieved 4th place in the ISBI 2017 Liver Tumor Segmentation Challenge by the submission deadline.
Prover efficient public verification of dense or sparse/structured matrix-vector multiplication
Venue: arXiv cs.CR 2017
Year: 2017

With the emergence of cloud computing services, computationally weak devices (Clients) can delegate expensive tasks to more powerful entities (Servers). This raises the question of verifying a result at a lower cost than that of recomputing it. This verification can be private, between the Client and the Server, or public, when the result can be verified by any third party. We here present protocols for the verification of matrix-vector multiplications, that are secure against malicious Servers. The obtained algorithms are essentially optimal in the amortized model: the overhead for the Server is limited to a very small constant factor, even in the sparse or structured matrix case; and the computational time for the public Verifier is linear in the dimension. Our protocols combine probabilistic checks and cryptographic operations, but minimize the latter to preserve practical efficiency. Therefore our protocols are overall more than two orders of magnitude faster than existing ones.
Parsimonious Random Vector Functional Link Network for Data Streams
Venue: arXiv cs.NE 2017
Year: 2017

The theory of random vector functional link network (RVFLN) has provided a breakthrough in the design of neural networks (NNs) since it conveys solid theoretical justification of randomized learning. Existing works in RVFLN are hardly scalable for data stream analytics because they are inherent to the issue of complexity as a result of the absence of structural learning scenarios. A novel class of RVLFN, namely parsimonious random vector functional link network (pRVFLN), is proposed in this paper. pRVFLN features an open structure paradigm where its network structure can be built from scratch and can be automatically generated in accordance with degree of nonlinearity and time-varying property of system being modelled. pRVFLN is equipped with complexity reduction scenarios where inconsequential hidden nodes can be pruned and input features can be dynamically selected. pRVFLN puts into perspective an online active learning mechanism which expedites the training process and relieves operator labelling efforts. In addition, pRVFLN introduces a non-parametric type of hidden node, developed using an interval-valued data cloud. The hidden node completely reflects the real data distribution and is not constrained by a specific shape of the cluster. All learning procedures of pRVFLN follow a strictly single-pass learning mode, which is applicable for an online real-time deployment. The efficacy of pRVFLN was rigorously validated through numerous simulations and comparisons with state-of-the art algorithms where it produced the most encouraging numerical results. Furthermore, the robustness of pRVFLN was investigated and a new conclusion is made to the scope of random parameters where it plays vital role to the success of randomized learning.
Making Defeating CAPTCHAs Harder for Bots
Venue: arXiv cs.CR 2017
Year: 2017

For a number of years, many websites have used CAPTCHAs to filter out interactions by bots. However, attackers have found ways to circumvent CAPTCHAs by programming bots to solve or bypass them, or even relay them for humans to solve. In order to reduce the chances of success of such attacks, CAPTCHAs can be strengthened by the addition of certain safeguards. In this paper, we discuss seven existing safeguards as well as five novel safeguards designed to make circumventing CAPTCHAs harder. These safeguards are not mutually exclusive and can add multiple layers of protection to a CAPTCHA. We further provide a high-level comparison of their effectiveness in addressing the threat posed by CAPTCHA-defeating techniques. In order to focus on safeguards that are usable, we restrict our attention to those which have minimal adverse effect on the user experience.
Throughput Optimal Random Medium Access Control for Relay Networks with Time-Varying Channels
Venue: arXiv cs.NI 2017
Year: 2017

The use of existing network devices as relays has a potential to improve the overall network performance. In this work, we consider a two-hop wireless relay setting, where the channels between the source and relay nodes to the destination node are time varying. The relay nodes are able to overhear the transmissions of the source node which may have a weak connection to the destination, and they help the source node by forwarding its messages to the destination on its behalf, whenever this is needed. We develop a distributed scheme for relay selection and channel access that is suitable for time-varying channels, and prove that this scheme is throughput optimal. We obtain the achievable rate region of our proposed scheme analytically for a relay network with a single source and a single relay node. Meanwhile, for a more general network with more than one relay nodes, we perform Monte-Carlo simulations to obtain the achievable rate region. In both cases, we demonstrate that the achievable rate region attained with our distributed scheme is the same as the one attained with centralized optimal scheme.
A Hidden Markov Restless Multi-armed Bandit Model for Playout Recommendation Systems
Venue: arXiv cs.SY 2017
Year: 2017

We consider a restless multi-armed bandit (RMAB) in which there are two types of arms, say A and B. Each arm can be in one of two states, say $0$ or $1.$ Playing a type A arm brings it to state $0$ with probability one and not playing it induces state transitions with arm-dependent probabilities. Whereas playing a type B arm leads it to state $1$ with probability $1$ and not playing it gets state that dependent on transition probabilities of arm. Further, play of an arm generates a unit reward with a probability that depends on the state of the arm. The belief about the state of the arm can be calculated using a Bayesian update after every play. This RMAB has been designed for use in recommendation systems where the user's preferences depend on the history of recommendations. This RMAB can also be used in applications like creating of playlists or placement of advertisements. In this paper we formulate the long term reward maximization problem as infinite horizon discounted reward and average reward problem. We analyse the RMAB by first studying discounted reward scenario. We show that it is Whittle-indexable and then obtain a closed form expression for the Whittle index for each arm calculated from the belief about its state and the parameters that describe the arm. We next analyse the average reward problem using vanishing discounted approach and derive the closed form expression for Whittle index. For a RMAB to be useful in practice, we need to be able to learn the parameters of the arms. We present an algorithm derived from Thompson sampling scheme, that learns the parameters of the arms and also illustrate its performance numerically.
Fast Learning and Prediction for Object Detection using Whitened CNN Features
Venue: arXiv cs.CV 2017
Year: 2017

We combine features extracted from pre-trained convolutional neural networks (CNNs) with the fast, linear Exemplar-LDA classifier to get the advantages of both: the high detection performance of CNNs, automatic feature engineering, fast model learning from few training samples and efficient sliding-window detection. The Adaptive Real-Time Object Detection System (ARTOS) has been refactored broadly to be used in combination with Caffe for the experimental studies reported in this work.
Minor-matching hypertree width
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we present a new width measure for a tree decomposition, minor-matching hypertree width, $μ\text{-}tw$, for graphs and hypergraphs, such that bounding the width guarantees that set of maximal independent sets has a polynomially-sized restriction to each decomposition bag. The relaxed conditions of the decomposition allow a much wider class of graphs and hypergraphs of bounded width compared to other tree decompositions. We show that, for fixed $k$, there are $2^{(1 - \frac1k + o(1)){n \choose 2}}$ $n$-vertex graphs of minor-matching hypertree width at most $k$. A number of problems including Maximum Independence Set, $k$-Colouring, and Homomorphism of uniform hypergraphs permit polynomial-time solutions for hypergraphs with bounded minor-matching hypertree width and bounded rank. We show that for any given $k$ and any graph $G$, it is possible to construct a decomposition of minor-matching hypertree width at most $O(k^3)$, or to prove that $μ\text{-}tw(G) > k$ in time $n^{O(k^3)}$. This is done by presenting a general algorithm for approximating the hypertree width of well-behaved measures, and reducing $μ\text{-}tw$ to such measure. The result relating the restriction of the maximal independent sets to a set $S$ with the set of induced matchings intersecting $S$ in graphs, and minor matchings intersecting $S$ in hypergraphs, might be of independent interest.
Automatic Classification of the Complexity of Nonfiction Texts in Portuguese for Early School Years
Venue: arXiv cs.CL 2017
Year: 2017

Recent research shows that most Brazilian students have serious problems regarding their reading skills. The full development of this skill is key for the academic and professional future of every citizen. Tools for classifying the complexity of reading materials for children aim to improve the quality of the model of teaching reading and text comprehension. For English, Fengs work [11] is considered the state-of-art in grade level prediction and achieved 74% of accuracy in automatically classifying 4 levels of textual complexity for close school grades. There are no classifiers for nonfiction texts for close grades in Portuguese. In this article, we propose a scheme for manual annotation of texts in 5 grade levels, which will be used for customized reading to avoid the lack of interest by students who are more advanced in reading and the blocking of those that still need to make further progress. We obtained 52% of accuracy in classifying texts into 5 levels and 74% in 3 levels. The results prove to be promising when compared to the state-of-art work.9
Towards an Empirical Study of Affine Types for Isolated Actors in Scala
Venue: arXiv cs.PL 2017
Year: 2017

LaCasa is a type system and programming model to enforce the object capability discipline in Scala, and to provide affine types. One important application of LaCasa's type system is software isolation of concurrent processes. Isolation is important for several reasons including security and data-race freedom. Moreover, LaCasa's affine references enable efficient, by-reference message passing while guaranteeing a "deep-copy" semantics. This deep-copy semantics enables programmers to seamlessly port concurrent programs running on a single machine to distributed programs running on large-scale clusters of machines. This paper presents an integration of LaCasa with actors in Scala, specifically, the Akka actor-based middleware, one of the most widely-used actor systems in industry. The goal of this integration is to statically ensure the isolation of Akka actors. Importantly, we present the results of an empirical study investigating the effort required to use LaCasa's type system in existing open-source Akka-based systems and applications.
Quantifying and Explaining Immutability in Scala
Venue: arXiv cs.PL 2017
Year: 2017

Functional programming typically emphasizes programming with first-class functions and immutable data. Immutable data types enable fault tolerance in distributed systems, and ensure process isolation in message-passing concurrency, among other applications. However, beyond the distinction between reassignable and non-reassignable fields, Scala's type system does not have a built-in notion of immutability for type definitions. As a result, immutability is "by-convention" in Scala, and statistics about the use of immutability in real-world Scala code are non-existent. This paper reports on the results of an empirical study on the use of immutability in several medium-to-large Scala open-source code bases, including Scala's standard library and the Akka actor framework. The study investigates both shallow and deep immutability, two widely-used forms of immutability in Scala. Perhaps most interestingly, for type definitions determined to be mutable, explanations are provided for why neither the shallow nor the deep immutability property holds; in turn, these explanations are aggregated into statistics in order to determine the most common reasons for why type definitions are mutable rather than immutable.
Compile-Time Extensions to Hybrid ODEs
Venue: arXiv cs.PL 2017
Year: 2017

Reachability analysis for hybrid systems is an active area of development and has resulted in many promising prototype tools. Most of these tools allow users to express hybrid system as automata with a set of ordinary differential equations (ODEs) associated with each state, as well as rules for transitions between states. Significant effort goes into developing and verifying and correctly implementing those tools. As such, it is desirable to expand the scope of applicability tools of such as far as possible. With this goal, we show how compile-time transformations can be used to extend the basic hybrid ODE formalism traditionally supported in hybrid reachability tools such as SpaceEx or Flow*. The extension supports certain types of partial derivatives and equational constraints. These extensions allow users to express, among other things, the Euler-Lagrangian equation, and to capture practically relevant constraints that arise naturally in mechanical systems. Achieving this level of expressiveness requires using a binding time-analysis (BTA), program differentiation, symbolic Gaussian elimination, and abstract interpretation using interval analysis. Except for BTA, the other components are either readily available or can be easily added to most reachability tools. The paper therefore focuses on presenting both the declarative and algorithmic specifications for the BTA phase, and establishes the soundness of the algorithmic specifications with respect to the declarative one.
Restoration of Atmospheric Turbulence-distorted Images via RPCA and Quasiconformal Maps
Venue: arXiv cs.CV 2017
Year: 2017

We address the problem of restoring a high-quality image from an observed image sequence strongly distorted by atmospheric turbulence. A novel algorithm is proposed in this paper to reduce geometric distortion as well as space-and-time-varying blur due to strong turbulence. By considering a suitable energy functional, our algorithm first obtains a sharp reference image and a subsampled image sequence containing sharp and mildly distorted image frames with respect to the reference image. The subsampled image sequence is then stabilized by applying the Robust Principal Component Analysis (RPCA) on the deformation fields between image frames and warping the image frames by a quasiconformal map associated with the low-rank part of the deformation matrix. After image frames are registered to the reference image, the low-rank part of them are deblurred via a blind deconvolution, and the deblurred frames are then fused with the enhanced sparse part. Experiments have been carried out on both synthetic and real turbulence-distorted video. Results demonstrate that our method is effective in alleviating distortions and blur, restoring image details and enhancing visual quality.
FMMU: A Hardware-Automated Flash Map Management Unit for Scalable Performance of NAND Flash-Based SSDs
Venue: arXiv cs.AR 2017
Year: 2017

NAND flash-based Solid State Drives (SSDs), which are widely used from embedded systems to enterprise servers, are enhancing performance by exploiting the parallelism of NAND flash memories. To cope with the performance improvement of SSDs, storage systems have rapidly adopted the host interface for SSDs from Serial-ATA, which is used for existing hard disk drives, to high-speed PCI express. Since NAND flash memory does not allow in-place updates, it requires special software called Flash Translation Layer (FTL), and SSDs are equipped with embedded processors to run FTL. Existing SSDs increase the clock frequency of embedded processors or increase the number of embedded processors in order to prevent FTL from acting as bottleneck of SSD performance, but these approaches are not scalable. This paper proposes a hardware-automated Flash Map Management Unit, called FMMU, that handles the address translation process dominating the execution time of the FTL by hardware automation. FMMU provides methods for exploiting the parallelism of flash memory by processing outstanding requests in a non-blocking manner while reducing the number of flash operations. The experimental results show that the FMMU reduces the FTL execution time in the map cache hit case and the miss case by 44% and 37%, respectively, compared with the existing software-based approach operating in 4-core. FMMU also prevents FTL from acting as a performance bottleneck for up to 32-channel, 8-way SSD using PCIe 3.0 x32 host interface.
Simplified Stochastic Feedforward Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

It has been believed that stochastic feedforward neural networks (SFNNs) have several advantages beyond deterministic deep neural networks (DNNs): they have more expressive power allowing multi-modal mappings and regularize better due to their stochastic nature. However, training large-scale SFNN is notoriously harder. In this paper, we aim at developing efficient training methods for SFNN, in particular using known architectures and pre-trained parameters of DNN. To this end, we propose a new intermediate stochastic model, called Simplified-SFNN, which can be built upon any baseline DNNand approximates certain SFNN by simplifying its upper latent units above stochastic ones. The main novelty of our approach is in establishing the connection between three models, i.e., DNN->Simplified-SFNN->SFNN, which naturally leads to an efficient training procedure of the stochastic models utilizing pre-trained parameters of DNN. Using several popular DNNs, we show how they can be effectively transferred to the corresponding stochastic models for both multi-modal and classification tasks on MNIST, TFD, CASIA, CIFAR-10, CIFAR-100 and SVHN datasets. In particular, we train a stochastic model of 28 layers and 36 million parameters, where training such a large-scale stochastic network is significantly challenging without using Simplified-SFNN