OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Low Rank Approximation of Implicit Functions of a Matrix
Venue: arXiv cs.NA 2016
Year: 2016

We study distributed low rank approximation in which the matrix to be approximated is only implicitly represented across the different servers. For example, each of $s$ servers may have an $n \times d$ matrix $A^t$, and we may be interested in computing a low rank approximation to $A = f(\sum_{t=1}^s A^t)$, where $f$ is a function which is applied entrywise to the matrix $\sum_{t=1}^s A^t$. We show for a wide class of functions $f$ it is possible to efficiently compute a $d \times d$ rank-$k$ projection matrix $P$ for which $\|A - AP\|_F^2 \leq \|A - [A]_k\|_F^2 + \varepsilon \|A\|_F^2$, where $AP$ denotes the projection of $A$ onto the row span of $P$, and $[A]_k$ denotes the best rank-$k$ approximation to $A$ given by the singular value decomposition. The communication cost of our protocols is $d \cdot (sk/\varepsilon)^{O(1)}$, and they succeed with high probability. Our framework allows us to efficiently compute a low rank approximation to an entry-wise softmax, to a Gaussian kernel expansion, and to $M$-Estimators applied entrywise (i.e., forms of robust low rank approximation). We also show that our additive error approximation is best possible, in the sense that any protocol achieving relative error for these problems requires significantly more communication. Finally, we experimentally validate our algorithms on real datasets.
Deep Learning Based Semantic Video Indexing and Retrieval
Venue: arXiv cs.IR 2016
Year: 2016

We share the implementation details and testing results for video retrieval system based exclusively on features extracted by convolutional neural networks. We show that deep learned features might serve as universal signature for semantic content of video useful in many search and retrieval tasks. We further show that graph-based storage structure for video index allows to efficiently retrieving the content with complicated spatial and temporal search queries.
Effective Capacity of Retransmission Schemes - A Recurrence Relation Approach
Venue: arXiv cs.IT 2016
Year: 2016

We consider the effective capacity performance measure of persistent- and truncated-retransmission schemes that can involve any combination of multiple transmissions per packet, multiple communication modes, or multiple packet communication. We present a structured unified analytical approach, based on a random walk model and recurrence relation formulation, and give exact effective capacity expressions for persistent hybrid automatic repeat request (HARQ) and for truncated-retransmission schemes. For the latter, effective capacity expressions are given for systems with finite (infinite) time horizon on an algebraic (spectral radius-based) form of a special block companion matrix. In contrast to prior HARQ models, assuming infinite time horizon, the proposed method does not involve a non-trivial per case modeling step. We give effective capacity expressions for several important cases that have not been addressed before, e.g. persistent-HARQ, truncated-HARQ, network-coded ARQ (NC-ARQ), two-mode-ARQ, and multilayer-ARQ. We propose an alternative QoS parameter (instead of the commonly used moment generating function parameter) that represents explicitly the target delay and the delay violation probability. This also enables closed-form expressions for many of the studied systems. Moreover, we use the recently proposed matrix-exponential distributed (MED) modeling of wireless fading channels to provide the basis for numerous new effective capacity results for HARQ.
The ecology of social interactions in online and offline environments
Venue: arXiv cs.SI 2016
Year: 2016

The rise in online social networking has brought about a revolution in social relations. However, its effects on offline interactions and its implications for collective well-being are still not clear and are under-investigated. We study the ecology of online and offline interaction in an evolutionary game framework where individuals can adopt different strategies of socialization. Our main result is that the spreading of self-protective behaviors to cope with hostile social environments can lead the economy to non-socially optimal stationary states.
Computer Science Programs, Goals, Student Learning Outcomes and their Assessment
Venue: arXiv cs.CY 2016
Year: 2016

In this paper we describe the process used by MET Computer Science to identify programs, goals, and student learning outcomes for all our programs and graduate certificates. We illustrate how we started the process of assessing learning outcomes for our programs and present actual assessment results from the data collected for two programs that went through accreditation--it describes sample direct and indirect assessment data from two of our programs.
Hybrid CNN and Dictionary-Based Models for Scene Recognition and Domain Adaptation
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional neural network (CNN) has achieved state-of-the-art performance in many different visual tasks. Learned from a large-scale training dataset, CNN features are much more discriminative and accurate than the hand-crafted features. Moreover, CNN features are also transferable among different domains. On the other hand, traditional dictionarybased features (such as BoW and SPM) contain much more local discriminative and structural information, which is implicitly embedded in the images. To further improve the performance, in this paper, we propose to combine CNN with dictionarybased models for scene recognition and visual domain adaptation. Specifically, based on the well-tuned CNN models (e.g., AlexNet and VGG Net), two dictionary-based representations are further constructed, namely mid-level local representation (MLR) and convolutional Fisher vector representation (CFV). In MLR, an efficient two-stage clustering method, i.e., weighted spatial and feature space spectral clustering on the parts of a single image followed by clustering all representative parts of all images, is used to generate a class-mixture or a classspecific part dictionary. After that, the part dictionary is used to operate with the multi-scale image inputs for generating midlevel representation. In CFV, a multi-scale and scale-proportional GMM training strategy is utilized to generate Fisher vectors based on the last convolutional layer of CNN. By integrating the complementary information of MLR, CFV and the CNN features of the fully connected layer, the state-of-the-art performance can be achieved on scene recognition and domain adaptation problems. An interested finding is that our proposed hybrid representation (from VGG net trained on ImageNet) is also complementary with GoogLeNet and/or VGG-11 (trained on Place205) greatly.
A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5
Venue: arXiv cs.DS 2016
Year: 2016

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.
Measurement-driven Quality Assessment of Nonlinear Systems by Exponential Replacement
Venue: arXiv cs.IT 2016
Year: 2016

We discuss the problem how to determine the quality of a nonlinear system with respect to a measurement task. Due to amplification, filtering, quantization and internal noise sources physical measurement equipment in general exhibits a nonlinear and random input-to-output behaviour. This usually makes it impossible to accurately describe the underlying statistical system model. When the individual operations are all known and deterministic, one can resort to approximations of the input-to-output function. The problem becomes challenging when the processing chain is not exactly known or contains nonlinear random effects. Then one has to approximate the output distribution in an empirical way. Here we show that by measuring the first two sample moments of an arbitrary set of output transformations in a calibrated setup, the output distribution of the actual system can be approximated by an equivalent exponential family distribution. This method has the property that the resulting approximation of the statistical system model is guaranteed to be pessimistic in an estimation theoretic sense. We show this by proving that an equivalent exponential family distribution in general exhibits a lower Fisher information measure than the original system model. With various examples and a model matching step we demonstrate how this estimation theoretic aspect can be exploited in practice in order to obtain a conservative measurement-driven quality assessment method for nonlinear measurement systems.
Space-Time Index Modulation
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present a new multi-antenna modulation scheme, termed as {\em space-time index modulation (STIM)}. In STIM, information bits are conveyed through antenna indexing in the spatial domain, slot indexing in the time domain, and $M$-ary modulation symbols. A time slot in a given frame can be used or unused, and the choice of the slots used for transmission conveys slot index bits. In addition, antenna index bits are conveyed in every used time slot by activating one among the available antennas. $M$-ary symbols are sent on the active antenna in a used time slot. We study STIM in a cyclic-prefixed single-carrier (CPSC) system in frequency-selective fading channels. It is shown that, for the same spectral efficiency, STIM can achieve better performance compared to conventional orthogonal frequency division multiplexing (OFDM). Low-complexity iterative algorithms for the detection of large-dimensional STIM signals are also presented.
The Right Way to Search Evolving Graphs
Venue: arXiv cs.SI 2016
Year: 2016

Evolving graphs arise in problems where interrelations between data change over time. We present a breadth first search (BFS) algorithm for evolving graphs that computes the most direct influences between nodes at two different times. Using simple examples, we show that naive unfoldings of adjacency matrices miscount the number of temporal paths. By mapping an evolving graph to an adjacency matrix of an equivalent static graph, we prove that our generalization of the BFS algorithm correctly accounts for paths that traverse both space and time. Finally, we demonstrate how the BFS over evolving graphs can be applied to mine citation networks.
On MBR codes with replication
Venue: arXiv cs.IT 2016
Year: 2016

An early paper by Rashmi et. al. presented the construction of an $(n,k,d=n-1)$ MBR regenerating code featuring the inherent double replication of all code symbols and repair-by-transfer (RBT), both of which are important in practice. We first show that no MBR code can contain even a single code symbol that is replicated more than twice. We then go on to present two new families of MBR codes which feature double replication of all systematic message symbols. The codes also possess a set of $d$ nodes whose contents include the message symbols and which can be repaired through help-by-transfer (HBT). As a corollary, we obtain systematic RBT codes for the case $d=(n-1)$ that possess inherent double replication of all code symbols and having a field size of $O(n)$ in comparison with the general, $O(n^2)$ field size requirement of the earlier construction by Rashmi et. al. For the cases $(k=d=n-2)$ or $(k+1=d=n-2)$, the field size can be reduced to $q=2$, and hence the codes can be binary. We also give a necessary and sufficient condition for the existence of MBR codes having double replication of all code symbols and also suggest techniques which will enable an arbitrary MBR code to be converted to one with double replication of all code symbols.
Deep convolutional networks for automated detection of posterior-element fractures on spine CT
Venue: arXiv cs.CV 2016
Year: 2016

Injuries of the spine, and its posterior elements in particular, are a common occurrence in trauma patients, with potentially devastating consequences. Computer-aided detection (CADe) could assist in the detection and classification of spine fractures. Furthermore, CAD could help assess the stability and chronicity of fractures, as well as facilitate research into optimization of treatment paradigms. In this work, we apply deep convolutional networks (ConvNets) for the automated detection of posterior element fractures of the spine. First, the vertebra bodies of the spine with its posterior elements are segmented in spine CT using multi-atlas label fusion. Then, edge maps of the posterior elements are computed. These edge maps serve as candidate regions for predicting a set of probabilities for fractures along the image edges using ConvNets in a 2.5D fashion (three orthogonal patches in axial, coronal and sagittal planes). We explore three different methods for training the ConvNet using 2.5D patches along the edge maps of 'positive', i.e. fractured posterior-elements and 'negative', i.e. non-fractured elements. An experienced radiologist retrospectively marked the location of 55 displaced posterior-element fractures in 18 trauma patients. We randomly split the data into training and testing cases. In testing, we achieve an area-under-the-curve of 0.857. This corresponds to 71% or 81% sensitivities at 5 or 10 false-positives per patient, respectively. Analysis of our set of trauma patients demonstrates the feasibility of detecting posterior-element fractures in spine CT images using computer vision techniques such as deep convolutional networks.
Optimal Prefix Free Codes With Partial Sorting
Venue: arXiv cs.DS 2016
Year: 2016

We describe an algorithm computing an optimal prefix free code for $n$ unsorted positive weights in time within $O(n(1+\lg α))\subseteq O(n\lg n)$, where the alternation $α\in[1..n-1]$ measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size $n$ and alternation $α$. Such results refine the state of the art complexity of $Θ(n\lg n)$ in the worst case over instances of size $n$ in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort a multiset depending on the queries on it (known since 1988).
What Can I Do Around Here? Deep Functional Scene Understanding for Cognitive Robots
Venue: arXiv cs.RO 2016
Year: 2016

For robots that have the capability to interact with the physical environment through their end effectors, understanding the surrounding scenes is not merely a task of image classification or object recognition. To perform actual tasks, it is critical for the robot to have a functional understanding of the visual scene. Here, we address the problem of localizing and recognition of functional areas from an arbitrary indoor scene, formulated as a two-stage deep learning based detection pipeline. A new scene functionality testing-bed, which is complied from two publicly available indoor scene datasets, is used for evaluation. Our method is evaluated quantitatively on the new dataset, demonstrating the ability to perform efficient recognition of functional areas from arbitrary indoor scenes. We also demonstrate that our detection model can be generalized onto novel indoor scenes by cross validating it with the images from two different datasets.
On the Symmetries and the Capacity Achieving Input Covariance Matrices of Multiantenna Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we study the capacity achieving input covariance matrices of a single user multiantenna channel based solely on the group of symmetries of its matrix of propagation coefficients. Our main result, which unifies and improves the techniques used in a variety of classical capacity theorems, uses the Haar (uniform) measure on the group of symmetries to establish the existence of a capacity achieving input covariance matrix in a very particular subset of the covariance matrices. This result allows us to provide simple proofs for old and new capacity theorems. Among other results, we show that for channels with two or more standard symmetries, the isotropic input is optimal. Overall, this paper provides a precise explanation of why the capacity achieving input covariance matrices of a channel depend more on the symmetries of the matrix of propagation coefficients than any other distributional assumption.
Skolem Sequence Based Self-adaptive Broadcast Protocol in Cognitive Radio Networks
Venue: arXiv cs.NI 2016
Year: 2016

The base station (BS) in a multi-channel cognitive radio (CR) network has to broadcast to secondary (or unlicensed) receivers/users on more than one broadcast channels via channel hopping (CH), because a single broadcast channel can be reclaimed by the primary (or licensed) user, leading to broadcast failures. Meanwhile, a secondary receiver needs to synchronize its clock with the BS's clock to avoid broadcast failures caused by the possible clock drift between the CH sequences of the secondary receiver and the BS. In this paper, we propose a CH-based broadcast protocol called SASS, which enables a BS to successfully broadcast to secondary receivers over multiple broadcast channels via channel hopping. Specifically, the CH sequences are constructed on basis of a mathematical construct---the Self-Adaptive Skolem sequence. Moreover, each secondary receiver under SASS is able to adaptively synchronize its clock with that of the BS without any information exchanges, regardless of any amount of clock drift.
Identifying a set of influential spreaders in complex networks
Venue: arXiv cs.SI 2016
Year: 2016

Identifying a set of influential spreaders in complex networks plays a crucial role in effective information spreading. A simple strategy is to choose top-$r$ ranked nodes as spreaders according to influence ranking method such as PageRank, ClusterRank and $k$-shell decomposition. Besides, some heuristic methods such as hill-climbing, SPIN, degree discount and independent set based are also proposed. However, these approaches suffer from a possibility that some spreaders are so close together that they overlap sphere of influence or time consuming. In this report, we present a simply yet effectively iterative method named VoteRank to identify a set of decentralized spreaders with the best spreading ability. In this approach, all nodes vote in a spreader in each turn, and the voting ability of neighbors of elected spreader will be decreased in subsequent turn. Experimental results on four real networks show that under Susceptible-Infected-Recovered (SIR) model, VoteRank outperforms the traditional benchmark methods on both spreading speed and final affected scale. What's more, VoteRank is also superior to other group-spreader identifying methods on computational time.
Towards Synthesis from Assume-Guarantee Contracts involving Infinite Theories: A Preliminary Report
Venue: arXiv cs.SE 2016
Year: 2016

In previous work, we have introduced a contract-based real- izability checking algorithm for assume-guarantee contracts involving infinite theories, such as linear integer/real arith- metic and uninterpreted functions over infinite domains. This algorithm can determine whether or not it is possible to con- struct a realization (i.e. an implementation) of an assume- guarantee contract. The algorithm is similar to k-induction model checking, but involves the use of quantifiers to deter- mine implementability. While our work on realizability is inherently useful for vir- tual integration in determining whether it is possible for sup- pliers to build software that meets a contract, it also provides the foundations to solving the more challenging problem of component synthesis. In this paper, we provide an initial synthesis algorithm for assume-guarantee contracts involv- ing infinite theories. To do so, we take advantage of our realizability checking procedure and a skolemization solver for forall-exists formulas, called AE-VAL. We show that it is possible to immediately adapt our existing algorithm towards syn- thesis by using this solver, using a demonstration example. We then discuss challenges towards creating a more robust synthesis algorithm.
A remark on incoherent feedforward circuits as change detectors and feedback controllers
Venue: arXiv cs.SY 2016
Year: 2016

This note analyzes incoherent feedforward loops in signal processing and control. It studies the response properties of IFFL's to exponentially growing inputs, both for a standard version of the IFFL and for a variation in which the output variable has a positive self-feedback term. It also considers a negative feedback configuration, using such a device as a controller. It uncovers a somewhat surprising phenomenon in which stabilization is only possible in disconnected regions of parameter space, as the controlled system's growth rate is varied.
Wireless Caching: Technical Misconceptions and Business Barriers
Venue: arXiv cs.IT 2016
Year: 2016

Caching is a hot research topic and poised to develop into a key technology for the upcoming 5G wireless networks. The successful implementation of caching techniques however, crucially depends on joint research developments in different scientific domains such as networking, information theory, machine learning, and wireless communications. Moreover, there exist business barriers related to the complex interactions between the involved stakeholders, the users, the cellular operators, and the Internet content providers. In this article we discuss several technical misconceptions with the aim to uncover enabling research directions for caching in wireless systems. Ultimately we make a speculative stakeholder analysis for wireless caching in 5G.
Numerical Atrribute Extraction from Clinical Texts
Venue: arXiv cs.AI 2016
Year: 2016

This paper describes about information extraction system, which is an extension of the system developed by team Hitachi for "Disease/Disorder Template filling" task organized by ShARe/CLEF eHealth Evolution Lab 2014. In this extension module we focus on extraction of numerical attributes and values from discharge summary records and associating correct relation between attributes and values. We solve the problem in two steps. First step is extraction of numerical attributes and values, which is developed as a Named Entity Recognition (NER) model using Stanford NLP libraries. Second step is correctly associating the attributes to values, which is developed as a relation extraction module in Apache cTAKES framework. We integrated Stanford NER model as cTAKES pipeline component and used in relation extraction module. Conditional Random Field (CRF) algorithm is used for NER and Support Vector Machines (SVM) for relation extraction. For attribute value relation extraction, we observe 95% accuracy using NER alone and combined accuracy of 87% with NER and SVM.
Lempel-Ziv Decoding in External Memory
Venue: arXiv cs.DS 2016
Year: 2016

Simple and fast decoding is one of the main advantages of LZ77-type text encoding used in many popular file compressors such as gzip and 7zip. With the recent introduction of external memory algorithms for Lempel-Ziv factorization there is a need for external memory LZ77 decoding but the standard algorithm makes random accesses to the text and cannot be trivially modified for external memory computation. We describe the first external memory algorithms for LZ77 decoding, prove that their I/O complexity is optimal, and demonstrate that they are very fast in practice, only about three times slower than in-memory decoding (when reading input and writing output is included in the time).