OpenRaiser/Intern-Atlas huggingface dataset:
Finite-Degree Predicates and Two-Variable First-Order Logic
Venue: arXiv cs.LO 2015
Year: 2015

We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the order and finite-degree predicates are also definable with the order predicate only. From this result we derive the separation of the alternation hierarchy of two-variable logic on this signature.
On the Application of Link Analysis Algorithms for Ranking Bipartite Graphs
Venue: arXiv cs.IR 2015
Year: 2015

Recently bipartite graphs have been widely used to represent the relationship two sets of items for information retrieval applications. The Web offers a wide range of data which can be represented by bipartite graphs, such us movies and reviewers in recomender systems, queries and URLs in search engines, users and posts in social networks. The size and the dynamic nature of such graphs generate the need for more efficient ranking methods. In this thesis, at first we present the fundamental mathematical backround that we use subsequently and we describe the basic principles of the Perron-Frobebius theory for non negative matrices as well as the the basic principles of the Markov chain theory. Then, we propose a novel algorithm named BipartiteRank, which is suitable to rank scenarios, that can be represented as a bipartite graph. This algorithm is based on the random surfer model and inherits the basic mathematical characteristics of PageRank. What makes it different, is the fact that it introduces an alternative type of teleportation, based on the block structure of the bipartite graph in order to achieve more efficient ranking. Finally, we support this opinion with mathematical arguments and then we confirm it experimentally through a series of tests on real data.
MetroViz: Visual Analysis of Public Transportation Data
Venue: arXiv cs.HC 2015
Year: 2015

Understanding the quality and usage of public transportation resources is important for schedule optimization and resource allocation. Ridership and adherence are the two main dimensions for evaluating the quality of service. Using Automatic Vehicle Location (AVL), Automatic Passenger Count (APC), and Global Positioning System (GPS) data, ridership data and adherence data of public transportation can be collected. In this paper, we discuss the development of a visualization tool for exploring public transportation data. We introduce "map view" and "route view" to help users locate stops in the context of geography and route information. To visualize ridership and adherence information over several years, we introduce "calendar view" - a miniaturized calendar that provides an overview of data where users can interactively select specific days to explore individual trips and stops ("trip subview" and "stop subview"). MetroViz was evaluated via a series of usability tests that included researchers from the Center for Advanced Transportation Technology (CATT) and students from the University of Maryland - College Park in which test participants used the tool to explore three years of bus transit data from Blacksburg, Virginia.
Diffusion Adaptation over Multi-Agent Networks with Wireless Link Impairments
Venue: arXiv cs.SY 2015
Year: 2015

We study the performance of diffusion least-mean-square algorithms for distributed parameter estimation in multi-agent networks when nodes exchange information over wireless communication links. Wireless channel impairments, such as fading and path-loss, adversely affect the exchanged data and cause instability and performance degradation if left unattended. To mitigate these effects, we incorporate equalization coefficients into the diffusion combination step and update the combination weights dynamically in the face of randomly changing neighborhoods due to fading conditions. When channel state information (CSI) is unavailable, we determine the equalization factors from pilot-aided channel coefficient estimates. The analysis reveals that by properly monitoring the CSI over the network and choosing sufficiently small adaptation step-sizes, the diffusion strategies are able to deliver satisfactory performance in the presence of fading and path loss.
Reinforcement Learning for the Unit Commitment Problem
Venue: arXiv cs.AI 2015
Year: 2015

In this work we solve the day-ahead unit commitment (UC) problem, by formulating it as a Markov decision process (MDP) and finding a low-cost policy for generation scheduling. We present two reinforcement learning algorithms, and devise a third one. We compare our results to previous work that uses simulated annealing (SA), and show a 27% improvement in operation costs, with running time of 2.5 minutes (compared to 2.5 hours of existing state-of-the-art).
2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
Venue: arXiv cs.LG 2015
Year: 2015

The Vapnik-Chervonenkis dimension is a combinatorial parameter that reflects the "complexity" of a set of sets (a.k.a. concept classes). It has been introduced by Vapnik and Chervonenkis in their seminal 1971 paper and has since found many applications, most notably in machine learning theory and in computational geometry. Arguably the most influential consequence of the VC analysis is the fundamental theorem of statistical machine learning, stating that a concept class is learnable (in some precise sense) if and only if its VC-dimension is finite. Furthermore, for such classes a most simple learning rule - empirical risk minimization (ERM) - is guaranteed to succeed. The simplest non-trivial structures, in terms of the VC-dimension, are the classes (i.e., sets of subsets) for which that dimension is 1. In this note we show a couple of curious results concerning such classes. The first result shows that such classes share a very simple structure, and, as a corollary, the labeling information contained in any sample labeled by such a class can be compressed into a single instance. The second result shows that due to some subtle measurability issues, in spite of the above mentioned fundamental theorem, there are classes of dimension 1 for which an ERM learning rule fails miserably.
An algorithm for discrete fractional Hadamard transform
Venue: arXiv cs.DS 2015
Year: 2015

We present a novel algorithm for calculating the discrete fractional Hadamard transform for data vectors whose size N is a power of two. A direct method for calculation of the discrete fractional Hadamard transform requires $N^2$ multiplications, while in proposed algorithm the number of real multiplications is reduced to $N$log$_2N$.
Provenance-Centered Dataset of Drug-Drug Interactions
Venue: arXiv cs.CY 2015
Year: 2015

Over the years several studies have demonstrated the ability to identify potential drug-drug interactions via data mining from the literature (MEDLINE), electronic health records, public databases (Drugbank), etc. While each one of these approaches is properly statistically validated, they do not take into consideration the overlap between them as one of their decision making variables. In this paper we present LInked Drug-Drug Interactions (LIDDI), a public nanopublication-based RDF dataset with trusty URIs that encompasses some of the most cited prediction methods and sources to provide researchers a resource for leveraging the work of others into their prediction methods. As one of the main issues to overcome the usage of external resources is their mappings between drug names and identifiers used, we also provide the set of mappings we curated to be able to compare the multiple sources we aggregate in our dataset.
Encoding toroidal triangulations
Venue: arXiv cs.DM 2015
Year: 2015

Poulalhon and Schaeffer introduced an elegant method to linearly encode a planar triangulation optimally. The method is based on performing a special depth-first search algorithm on a particular orientation of the triangulation: the minimal Schnyder wood. Recent progress toward generalizing Schnyder woods to higher genus enables us to generalize this method to the toroidal case. In the plane, the method leads to a bijection between planar triangulations and some particular trees. For the torus we obtain a similar bijection but with particular unicellular maps (maps with only one face).
Solving Problems on Graphs of High Rank-Width
Venue: arXiv cs.DS 2015
Year: 2015

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various tractable graph classes has long been used as a structural parameter which can be exploited to obtain FPT algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are strictly more general than the cardinality of modulators and rank-width itself. Then, we develop an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for Minimum Vertex Cover and Maximum Clique. Finally, we use well-structured modulators to develop an algorithmic meta-theorem for deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems.
Budget Constrained Execution of Multiple Bag-of-Tasks Applications on the Cloud
Venue: arXiv cs.DC 2015
Year: 2015

Optimising the execution of Bag-of-Tasks (BoT) applications on the cloud is a hard problem due to the trade- offs between performance and monetary cost. The problem can be further complicated when multiple BoT applications need to be executed. In this paper, we propose and implement a heuristic algorithm that schedules tasks of multiple applications onto different cloud virtual machines in order to maximise performance while satisfying a given budget constraint. Current approaches are limited in task scheduling since they place a limit on the number of cloud resources that can be employed by the applications. However, in the proposed algorithm there are no such limits, and in comparison with other approaches, the algorithm on average achieves an improved performance of 10%. The experimental results also highlight that the algorithm yields consistent performance even with low budget constraints which cannot be achieved by competing approaches.
Cyclic codes from the second class two-prime Whiteman's generalized cyclotomic sequence with order 6
Venue: arXiv cs.IT 2015
Year: 2015

Let $n_1=ef+1$ and $n_2=ef'+1$ be two distinct odd primes with positive integers $e,\ f,\ f'.$ In this paper, the two-prime Whiteman's generalized cyclotomic sequence of order $e=6$ is employed to construct several classes of cyclic codes over $\mathrm{GF}(q)$ with length $n_1n_2$. The lower bounds on the minimum distance of these cyclic codes are obtained.
Secure Partial Repair in Wireless Caching Networks with Broadcast Channels
Venue: arXiv cs.IT 2015
Year: 2015

We study security in partial repair in wireless caching networks where parts of the stored packets in the caching nodes are susceptible to be erased. Let us denote a caching node that has lost parts of its stored packets as a sick caching node and a caching node that has not lost any packet as a healthy caching node. In partial repair, a set of caching nodes (among sick and healthy caching nodes) broadcast information to other sick caching nodes to recover the erased packets. The broadcast information from a caching node is assumed to be received without any error by all other caching nodes. All the sick caching nodes then are able to recover their erased packets, while using the broadcast information and the nonerased packets in their storage as side information. In this setting, if an eavesdropper overhears the broadcast channels, it might obtain some information about the stored file. We thus study secure partial repair in the senses of information-theoretically strong and weak security. In both senses, we investigate the secrecy caching capacity, namely, the maximum amount of information which can be stored in the caching network such that there is no leakage of information during a partial repair process. We then deduce the strong and weak secrecy caching capacities, and also derive the sufficient finite field sizes for achieving the capacities. Finally, we propose optimal secure codes for exact partial repair, in which the recovered packets are exactly the same as erased packets.
Subspace Alignment Based Domain Adaptation for RCNN Detector
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose subspace alignment based domain adaptation of the state of the art RCNN based object detector. The aim is to be able to achieve high quality object detection in novel, real world target scenarios without requiring labels from the target domain. While, unsupervised domain adaptation has been studied in the case of object classification, for object detection it has been relatively unexplored. In subspace based domain adaptation for objects, we need access to source and target subspaces for the bounding box features. The absence of supervision (labels and bounding boxes are absent) makes the task challenging. In this paper, we show that we can still adapt sub- spaces that are localized to the object by obtaining detections from the RCNN detector trained on source and applied on target. Then we form localized subspaces from the detections and show that subspace alignment based adaptation between these subspaces yields improved object detection. This evaluation is done by considering challenging real world datasets of PASCAL VOC as source and validation set of Microsoft COCO dataset as target for various categories.
Instructor Perspectives of Mobile Learning Platform: An Empirical Study
Venue: arXiv cs.CY 2015
Year: 2015

Mobile learning (mLearning) is the cutting-edge learning platform to really gain traction, driven mostly by the huge uptake in smartphones and their ever increasing uses within the educational society. Education has long benefitted from the proliferation of technology; however, mLearning adoption has not proceeded at the pace one might expect. There is a disconnect between the rate of adoption of the underlying platform (smartphones) and the use of that technology within learning. The reasons behind this have been the subject of several research studies. However, previous studies have mostly focused on investigating the critical success factors (CSFs) from the student perspectives. In this research, we have carried out an extensive study of the six factors that impact the success of mLearning from instructors perspectives. The results of the research showed that three factors: technical competence of instructors, Instructors autonomy, and blended learning are the most important elements that contribute to mLearning adoption from instructors perspectives.
Energy Efficiency of Distributed Signal Processing in Wireless Networks: A Cross-Layer Analysis
Venue: arXiv cs.IT 2015
Year: 2015

In order to meet the growing mobile data demand, future wireless networks will be equipped with a multitude of access points (APs). Besides the important implications for the energy consumption, the trend towards densification requires the development of decentralized and sustainable radio resource management techniques. It is critically important to understand how the distribution of signal processing operations affects the energy efficiency of wireless networks. In this paper, we provide a cross-layer framework to evaluate and compare the energy efficiency of wireless networks under different levels of distribution of the signal processing load: (i) hybrid, where the signal processing operations are shared between nodes and APs, (ii) centralized, where signal processing is entirely implemented at the APs, and (iii) fully distributed, where all operations are performed by the nodes. We find that in practical wireless networks, hybrid signal processing exhibits a significant energy efficiency gain over both centralized and fully distributed approaches.
On Multi-source Networks: Enumeration, Rate Region Computation, and Hierarchy
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the enumeration, rate region computation, and hierarchy of general multi-source multi-sink hyperedge networks under network coding, which includes multiple network models, such as independent distributed storage systems and index coding problems, as special cases. A notion of minimal networks and a notion of network equivalence under group action are defined. An efficient algorithm capable of directly listing single minimal canonical representatives from each network equivalence class is presented and utilized to list all minimal canonical networks with up to 5 sources and hyperedges. Computational tools are then applied to obtain the rate regions of all of these canonical networks, providing exact expressions for 744,119 newly solved network coding rate regions corresponding to more than 2 trillion isomorphic network coding problems. In order to better understand and analyze the huge repository of rate regions through hierarchy, several embedding and combination operations are defined so that the rate region of the network after operation can be derived from the rate regions of networks involved in the operation. The embedding operations enable the definition and determination of a list of forbidden network minors for the sufficiency of classes of linear codes. The combination operations enable the rate regions of some larger networks to be obtained as the combination of the rate regions of smaller networks. The integration of both the combinations and embedding operators is then shown to enable the calculation of rate regions for many networks not reachable via combination operations alone.
Complete Weight Enumerator of a Family of Linear Codes from Cyclotomy
Venue: arXiv cs.IT 2015
Year: 2015

Linear codes have been an interesting topic in both theory and practice for many years. In this paper, for a prime $p$, we determine the explicit complete weight enumerators of a family of linear codes over $\mathbb{F}_p$ with defining set related to cyclotomy. These codes may have applications in cryptography and secret sharing schemes.
Online Metric-Weighted Linear Representations for Robust Visual Tracking
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a visual tracker based on a metric-weighted linear representation of appearance. In order to capture the interdependence of different feature dimensions, we develop two online distance metric learning methods using proximity comparison information and structured output learning. The learned metric is then incorporated into a linear representation of appearance. We show that online distance metric learning significantly improves the robustness of the tracker, especially on those sequences exhibiting drastic appearance changes. In order to bound growth in the number of training samples, we design a time-weighted reservoir sampling method. Moreover, we enable our tracker to automatically perform object identification during the process of object tracking, by introducing a collection of static template samples belonging to several object classes of interest. Object identification results for an entire video sequence are achieved by systematically combining the tracking information and visual recognition at each frame. Experimental results on challenging video sequences demonstrate the effectiveness of the method for both inter-frame tracking and object identification.
Nonexistence of Generalized Bent Functions From $Z_{2}^{n}$ to $Z_{m}$
Venue: arXiv cs.IT 2015
Year: 2015

Several nonexistence results on generalized bent functions $f:Z_{2}^{n} \rightarrow Z_{m}$ presented by using some knowledge on cyclotomic number fields and their imaginary quadratic subfields.
Optimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure
Venue: arXiv cs.DM 2015
Year: 2015

Wall-clock-time is minimized for a solution to a linear-program with block-diagonal-structure, by decomposing the linear-program into as many small-sized subproblems as possible, each block resulting in a separate subproblem, when the number of available parallel-processing-units is at least equal to the number of blocks. This is not necessarily the case when the parallel processing capability is limited, causing multiple subproblems to be serially solved on the same processing-unit. In such a situation, it might be better to aggregate blocks into larger sized subproblems. The optimal aggregation strategy depends on the computing-platform used, and minimizes the average-case running time for the set of subproblems. We show that optimal aggregation is NP-hard when blocks are of unequal size, and that optimal aggregation can be achieved within polynomial-time when blocks are of equal size.
Compression of Fully-Connected Layer in Neural Network by Kronecker Product
Venue: arXiv cs.NE 2015
Year: 2015

In this paper we propose and study a technique to reduce the number of parameters and computation time in fully-connected layers of neural networks using Kronecker product, at a mild cost of the prediction quality. The technique proceeds by replacing Fully-Connected layers with so-called Kronecker Fully-Connected layers, where the weight matrices of the FC layers are approximated by linear combinations of multiple Kronecker products of smaller matrices. In particular, given a model trained on SVHN dataset, we are able to construct a new KFC model with 73\% reduction in total number of parameters, while the error only rises mildly. In contrast, using low-rank method can only achieve 35\% reduction in total number of parameters given similar quality degradation allowance. If we only compare the KFC layer with its counterpart fully-connected layer, the reduction in the number of parameters exceeds 99\%. The amount of computation is also reduced as we replace matrix product of the large matrices in FC layers with matrix products of a few smaller matrices in KFC layers. Further experiments on MNIST, SVHN and some Chinese Character recognition models also demonstrate effectiveness of our technique.
A System for Sensing Human Sentiments to Augment a Model for Predicting Rare Lake Events
Venue: arXiv cs.SI 2015
Year: 2015

Fish kill events (FKE) in the caldera lake of Taal occur rarely (only 0.5\% in the last 10 years) but each event has a long-term effect on the environmental health of the lake ecosystem, as well as a devastating effect on the financial and emotional aspects of the residents whose livelihood rely on aquaculture farming. Predicting with high accuracy when within seven days and where on the vast expanse of the lake will FKEs strike will be a very important early warning tool for the lake's aquaculture industry. Mathematical models to predict the occurrences of FKEs developed by several studies done in the past use as predictors the physico-chemical characteristics of the lake water, as well as the meteorological parameters above it. Some of the models, however, did not provide acceptable predictive accuracy and enough early warning because they were developed with unbalanced binary data set, i.e., characterized by dense negative examples (no FKE) and highly sparse positive examples (with FKE). Other models require setting up an expensive sensor network to measure the water parameters not only at the surface but also at several depths. Presented in this paper is a system for capturing, measuring, and visualizing the contextual sentiment polarity (CSP) of dated and geolocated social media microposts of residents within 10km radius of the Taal Volcano crater ($14^\circ$N, $121^\circ$E). High frequency negative CSP co-occur with FKE for two occasions making human expressions a viable non-physical sensors for impending FKE to augment existing mathematical models.