OpenRaiser/Intern-Atlas huggingface dataset:
Joint Resource Bidding and Tipping Strategies in Multi-hop Cognitive Networks
Venue: arXiv cs.GT 2016
Year: 2016

In multi-hop secondary networks, bidding strategies for spectrum auction, route selection and relaying incentives should be jointly considered to establish multi-hop communication. In this paper, a framework for joint resource bidding and tipping is developed where users iteratively revise their strategies, which include bidding and incentivizing relays, to achieve their Quality of Service (QoS) requirements. A bidding language is designed to generalize secondary users' heterogeneous demands for multiple resources and willingness to pay. Then, group partitioning-based auction mechanisms are presented to exploit the heterogeneity of SU demands in multi-hop secondary networks. These mechanisms include primary operator (PO) strategies based on static and dynamic partition schemes combined with new payment mechanisms to obtain high revenue and fairly allocate the resources. The proposed auction schemes stimulate the participation of SUs and provide high revenue for the PO while maximizing the social welfare. Besides, they satisfy the properties of truthfulness, individual rationality and computational tractability. Simulation results have shown that for highly demanding users the static group scheme achieves 150% more winners and 3 times higher revenue for the PO compared to a scheme without grouping. For lowly demanding users, the PO may keep similar revenue with the dynamic scheme by lowering 50% the price per channel as the number of winners will increase proportionally.
Content Based Image Retrieval (CBIR) in Remote Clinical Diagnosis and Healthcare
Venue: arXiv cs.CV 2016
Year: 2016

Content-Based Image Retrieval (CBIR) locates, retrieves and displays images alike to one given as a query, using a set of features. It demands accessible data in medical archives and from medical equipment, to infer meaning after some processing. A problem similar in some sense to the target image can aid clinicians. CBIR complements text-based retrieval and improves evidence-based diagnosis, administration, teaching, and research in healthcare. It facilitates visual/automatic diagnosis and decision-making in real-time remote consultation/screening, store-and-forward tests, home care assistance and overall patient surveillance. Metrics help comparing visual data and improve diagnostic. Specially designed architectures can benefit from the application scenario. CBIR use calls for file storage standardization, querying procedures, efficient image transmission, realistic databases, global availability, access simplicity, and Internet-based structures. This chapter recommends important and complex aspects required to handle visual content in healthcare.
Towards an Ontology-Driven Blockchain Design for Supply Chain Provenance
Venue: arXiv cs.CY 2016
Year: 2016

An interesting research problem in our age of Big Data is that of determining provenance. Granular evaluation of provenance of physical goods--e.g. tracking ingredients of a pharmaceutical or demonstrating authenticity of luxury goods--has often not been possible with today's items that are produced and transported in complex, inter-organizational, often internationally-spanning supply chains. Recent adoption of Internet of Things and Blockchain technologies give promise at better supply chain provenance. We are particularly interested in the blockchain as many favoured use cases of blockchain are for provenance tracking. We are also interested in applying ontologies as there has been some work done on knowledge provenance, traceability, and food provenance using ontologies. In this paper, we make a case for why ontologies can contribute to blockchain design. To support this case, we analyze a traceability ontology and translate some of its representations to smart contracts that execute a provenance trace and enforce traceability constraints on the Ethereum blockchain platform.
Batch Coloring of Graphs
Venue: arXiv cs.DS 2016
Year: 2016

In graph coloring problems, the goal is to assign a positive integer color to each vertex of an input graph such that adjacent vertices do not receive the same color assignment. For classic graph coloring, the goal is to minimize the maximum color used, and for the sum coloring problem, the goal is to minimize the sum of colors assigned to all input vertices. In the offline variant, the entire graph is presented at once, and in online problems, one vertex is presented for coloring at each time, and the only information is the identity of its neighbors among previously known vertices. In batched graph coloring, vertices are presented in k batches, for a fixed integer k > 1, such that the vertices of a batch are presented as a set, and must be colored before the vertices of the next batch are presented. This last model is an intermediate model, which bridges between the two extreme scenarios of the online and offline models. We provide several results, including a general result for sum coloring and results for the classic graph coloring problem on restricted graph classes: We show tight bounds for any graph class containing trees as a subclass (e.g., forests, bipartite graphs, planar graphs, and perfect graphs), and a surprising result for interval graphs and k = 2, where the value of the (strict and asymptotic) competitive ratio depends on whether the graph is presented with its interval representation or not.
On the b-continuity of the lexicographic product of graphs
Venue: arXiv cs.DM 2016
Year: 2016

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of $G$ is the maximum integer $χ_b(G)$ for which $G$ has a b-coloring with $χ_b(G)$ colors. A graph $G$ is b-continuous if $G$ has a b-coloring with $k$ colors, for every integer $k$ in the interval $[χ(G),χ_b(G)]$. It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product $G[H]$ of b-continuous graphs $G$ and $H$ is also b-continuous. Using homomorphisms, we provide a new lower bound for $χ_b(G[H])$, namely $χ_b(G[K_t])$, where $t=χ_b(H)$, and prove that if $G[K_\ell]$ is b-continuous for every positive integer $\ell$, then $G[H]$ admits a b-coloring with $k$ colors, for every $k$ in the interval $[χ(G[H]),χ_b(G[K_t])]$. We also prove that $G[K_\ell]$ is b-continuous, for every positive integer $\ell$, whenever $G$ is a $P_4$-sparse graph, and we give further results on the b-spectrum of $G[K_\ell]$, when $G$ is chordal.
Dynamic Metric Learning from Pairwise Comparisons
Venue: arXiv cs.LG 2016
Year: 2016

Recent work in distance metric learning has focused on learning transformations of data that best align with specified pairwise similarity and dissimilarity constraints, often supplied by a human observer. The learned transformations lead to improved retrieval, classification, and clustering algorithms due to the better adapted distance or similarity measures. Here, we address the problem of learning these transformations when the underlying constraint generation process is nonstationary. This nonstationarity can be due to changes in either the ground-truth clustering used to generate constraints or changes in the feature subspaces in which the class structure is apparent. We propose Online Convex Ensemble StrongLy Adaptive Dynamic Learning (OCELAD), a general adaptive, online approach for learning and tracking optimal metrics as they change over time that is highly robust to a variety of nonstationary behaviors in the changing metric. We apply the OCELAD framework to an ensemble of online learners. Specifically, we create a retro-initialized composite objective mirror descent (COMID) ensemble (RICE) consisting of a set of parallel COMID learners with different learning rates, demonstrate RICE-OCELAD on both real and synthetic data sets and show significant performance improvements relative to previously proposed batch and online distance metric learning algorithms.
PCG-Based Game Design Patterns
Venue: arXiv cs.AI 2016
Year: 2016

People enjoy encounters with generative software, but rarely are they encouraged to interact with, understand or engage with it. In this paper we define the term 'PCG-based game', and explain how this concept follows on from the idea of an AI-based game. We look at existing examples of games which foreground their AI, put forward a methodology for designing PCG-based games, describe some example case study designs for PCG-based games, and describe lessons learned during this process of sketching and developing ideas.
Long Short-Term Memory based Convolutional Recurrent Neural Networks for Large Vocabulary Speech Recognition
Venue: arXiv cs.CL 2016
Year: 2016

Long short-term memory (LSTM) recurrent neural networks (RNNs) have been shown to give state-of-the-art performance on many speech recognition tasks, as they are able to provide the learned dynamically changing contextual window of all sequence history. On the other hand, the convolutional neural networks (CNNs) have brought significant improvements to deep feed-forward neural networks (FFNNs), as they are able to better reduce spectral variation in the input signal. In this paper, a network architecture called as convolutional recurrent neural network (CRNN) is proposed by combining the CNN and LSTM RNN. In the proposed CRNNs, each speech frame, without adjacent context frames, is organized as a number of local feature patches along the frequency axis, and then a LSTM network is performed on each feature patch along the time axis. We train and compare FFNNs, LSTM RNNs and the proposed LSTM CRNNs at various number of configurations. Experimental results show that the LSTM CRNNs can exceed state-of-the-art speech recognition performance.
Comparing of switching frequency on vector controlled asynchronous motor
Venue: arXiv cs.SY 2016
Year: 2016

Nowadays, asynchronous motors have wide range use in many industrial applications. Field oriented control (FOC) and direct torque control (DTC) are commonly used methods in high performance vector control for asynchronous motors. Therefore, it is very important to identify clearly advantages and disadvantages of both systems in the selection of appropriate control methods for many industrial applications. This paper aims to present a new and different perspective regarding the comparison of the switching behaviours on the FOC and the DTC drivers. For this purpose, the experimental studies have been carried out to compare the inverter switching frequencies and torque responses of the asynchronous motor in the FOC and the DTC systems under different working conditions. The dSPACE 1103 controller board was programmed with Matlab/Simulink software. As expected, the experimental studies showed that the FOC controlled motors has a lessened torque ripple. On the other hand, the FOC controlled motor switching frequency has about 65-75% more than the DTC controlled under both loaded and unloaded working conditions.
Generating Candidate Busy Beaver Machines (Or How to Build the Zany Zoo)
Venue: arXiv cs.FL 2016
Year: 2016

The busy beaver problem is a well-known example of a non-computable function. In order to determine a particular value of this function, it is necessary to generate and classify a large number of Turing machines. Previous work on this problem has described the processes used for the generation and classification of these machines, but unfortunately has generally not provided details of the machines considered. While there is no reason to doubt the veracity of the results known so far, it is difficult to accept such results as scientifically proven without being able to inspect the appropriate evidence. In addition, a list of machines and their classifications can be used for other results, such as variations on the busy beaver problem and related problems such as the placid platypus problem. In this paper we investigate how to generate classes of machines to be considered for the busy beaver problem. We discuss the relationship between quadruple and quintuple variants of Turing machines, and show that the latter are more general than the former. We give some formal results to justify our strategy for minimising the number of machines generated, and define a process reflecting this strategy for generating machines. We describe our implementation, and the results of generating various classes of machines with up to 5 states or up to 5 symbols, all of which (together with our code) are available on the author's website.
On the Optimality of Tape Merge of Two Lists with Similar Size
Venue: arXiv cs.CC 2016
Year: 2016

The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp \cite{taocp} independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. In the seminal papers, Stockmeyer and Yao\cite{yao}, Murphy and Paull\cite{3k3}, and Christen\cite{christen1978optimality} independently showed when the lists to be merged are of size $m$ and $n$ satisfying $m\leq n\leq\lfloor\frac{3}{2}m\rfloor+1$, the tape merge algorithm is optimal in the worst case. This paper extends this result by showing that the tape merge algorithm is optimal in the worst case whenever the size of one list is no larger than 1.52 times the size of the other. The main tool we used to prove lower bounds is Knuth's adversary methods \cite{taocp}. In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. We also develop a new inequality about Knuth's adversary methods, which might be interesting in its own right. Moreover, we design a simple procedure to achieve constant improvement of the upper bounds for $2m-2\leq n\leq 3m $.
Combining Treewidth and Backdoors for CSP
Venue: arXiv cs.DS 2016
Year: 2016

We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combines the two prominent approaches for achieving tractability for CSP: (i) by structural restrictions on the interaction between the variables and the constraints and (ii) by language restrictions on the relations that can be used inside the constraints. Apart from defining the notion of backdoor-treewidth and showing how backdoors of small treewidth can be used to efficiently solve CSP, our main technical contribution is a fixed-parameter algorithm that finds a backdoor of small treewidth.
Near Optimal Adaptive Shortest Path Routing with Stochastic Links States under Adversarial Attack
Venue: arXiv cs.NI 2016
Year: 2016

We consider the shortest path routing (SPR) of a network with stochastically time varying link metrics under potential adversarial attacks. Due to potential denial of service attacks, the distributions of link states could be stochastic (benign) or adversarial at different temporal and spatial locations. Without any \emph{a priori}, designing an adaptive SPR protocol to cope with all possible situations in practice optimally is a very challenging issue. In this paper, we present the first solution by formulating it as a multi-armed bandit (MAB) problem. By introducing a novel control parameter into the exploration phase for each link, a martingale inequality is applied in the our combinatorial adversarial MAB framework. As such, our proposed algorithms could automatically detect features of the environment within a unified framework and find the optimal SPR strategies with almost optimal learning performance in all possible cases over time. Moreover, we study important issues related to the practical implementation, such as decoupling route selection with multi-path route probing, cooperative learning among multiple sources, the "cold-start" issue and delayed feedback of our algorithm. Nonetheless, the proposed SPR algorithms can be implemented with low complexity and they are proved to scale very well with the network size. Comparing to existing approaches in a typical network scenario under jamming attacks, our algorithm has a 65.3\% improvement of network delay given a learning period and a 81.5\% improvement of learning duration under a specified network delay.
Modulation Classification via Subspace Detection in MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

The problem of efficient modulation classification (MC) in multiple-input multiple-output (MIMO) systems is considered. Per-layer likelihood-based MC is proposed by employing subspace decomposition to partially decouple the transmitted streams. When detecting the modulation type of the stream of interest, a dense constellation is assumed on all remaining streams. The proposed classifier outperforms existing MC schemes at a lower complexity cost, and can be efficiently implemented in the context of joint MC and subspace data detection.
Crossing the Road Without Traffic Lights: An Android-based Safety Device
Venue: arXiv cs.CV 2016
Year: 2016

In the absence of pedestrian crossing lights, finding a safe moment to cross the road is often hazardous and challenging, especially for people with visual impairments. We present a reliable low-cost solution, an Android device attached to a traffic sign or lighting pole near the crossing, indicating whether it is safe to cross the road. The indication can be by sound, display, vibration, and various communication modalities provided by the Android device. The integral system camera is aimed at approaching traffic. Optical flow is computed from the incoming video stream, and projected onto an influx map, automatically acquired during a brief training period. The crossing safety is determined based on a 1-dimensional temporal signal derived from the projection. We implemented the complete system on a Samsung Galaxy K-Zoom Android smartphone, and obtained real-time operation. The system achieves promising experimental results, providing pedestrians with sufficiently early warning of approaching vehicles. The system can serve as a stand-alone safety device, that can be installed where pedestrian crossing lights are ruled out. Requiring no dedicated infrastructure, it can be powered by a solar panel and remotely maintained via the cellular network.
On break-away forces in actuated motion systems with nonlinear friction
Venue: arXiv cs.SY 2016
Year: 2016

The phenomenon of so-called break-away forces, as maximal actuation forces at which a sticking system begins to slide and thus passes over to a steady (macro) motion, is well known from engineering practice but still less understood in its cause-effect relationship. This note analyzes the break-away behavior of systems with nonlinear friction, which is analytically well-described by combining the Coulomb friction law with rate-independent presliding transitions and, when necessary, Stribeck effect of the velocity-weakening steady-state curve. The break-away conditions are harmonized with analytic form of the system description and shown to be in accord with a relationship between the varying break-away force and actuation force rate -- well known from the experiments reported in several independently published works.
Deep Learning Assessment of Tumor Proliferation in Breast Cancer Histological Images
Venue: arXiv cs.CV 2016
Year: 2016

Current analysis of tumor proliferation, the most salient prognostic biomarker for invasive breast cancer, is limited to subjective mitosis counting by pathologists in localized regions of tissue images. This study presents the first data-driven integrative approach to characterize the severity of tumor growth and spread on a categorical and molecular level, utilizing multiple biologically salient deep learning classifiers to develop a comprehensive prognostic model. Our approach achieves pathologist-level performance on three-class categorical tumor severity prediction. It additionally pioneers prediction of molecular expression data from a tissue image, obtaining a Spearman's rank correlation coefficient of 0.60 with ex vivo mean calculated RNA expression. Furthermore, our framework is applied to identify over two hundred unprecedented biomarkers critical to the accurate assessment of tumor proliferation, validating our proposed integrative pipeline as the first to holistically and objectively analyze histopathological images.
The Core of the Participatory Budgeting Problem
Venue: arXiv cs.GT 2016
Year: 2016

In participatory budgeting, communities collectively decide on the allocation of public tax dollars for local public projects. In this work, we consider the question of fairly aggregating the preferences of community members to determine an allocation of funds to projects. This problem is different from standard fair resource allocation because of public goods: The allocated goods benefit all users simultaneously. Fairness is crucial in participatory decision making, since generating equitable outcomes is an important goal of these processes. We argue that the classic game theoretic notion of core captures fairness in the setting. To compute the core, we first develop a novel characterization of a public goods market equilibrium called the Lindahl equilibrium, which is always a core solution. We then provide the first (to our knowledge) polynomial time algorithm for computing such an equilibrium for a broad set of utility functions; our algorithm also generalizes (in a non-trivial way) the well-known concept of proportional fairness. We use our theoretical insights to perform experiments on real participatory budgeting voting data. We empirically show that the core can be efficiently computed for utility functions that naturally model our practical setting, and examine the relation of the core with the familiar welfare objective. Finally, we address concerns of incentives and mechanism design by developing a randomized approximately dominant-strategy truthful mechanism building on the exponential mechanism from differential privacy.
Sparse Channel Estimation for Massive MIMO with 1-bit Feedback per Dimension
Venue: arXiv cs.NI 2016
Year: 2016

In massive multiple-input multiple-output (MIMO) systems, acquisition of the channel state information at the transmitter side (CSIT) is crucial. In this paper, a practical CSIT estimation scheme is proposed for frequency division duplexing (FDD) massive MIMO systems. Specifically, each received pilot symbol is first quantized to one bit per dimension at the receiver side and then the quantized bits are fed back to the transmitter. A joint one-bit compressed sensing algorithm is implemented at the transmitter to recover the channel matrices. The algorithm leverages the hidden joint sparsity structure in the user channel matrices to minimize the training and feedback overhead, which is considered to be a major challenge for FDD systems. Moreover, the one-bit compressed sensing algorithm accurately recovers the channel directions for beamforming. The one-bit feedback mechanism can be implemented in practical systems using the uplink control channel. Simulation results show that the proposed scheme nearly achieves the maximum output signal-to-noise-ratio for beamforming based on the estimated CSIT.
The Virtual Electromagnetic Interaction between Digital Images for Image Matching with Shifting Transformation
Venue: arXiv cs.CV 2016
Year: 2016

A novel way of matching two images with shifting transformation is studied. The approach is based on the presentation of the virtual edge current in images, and also the study of virtual electromagnetic interaction between two related images inspired by electromagnetism. The edge current in images is proposed as a discrete simulation of the physical current, which is based on the significant edge line extracted by Canny-like edge detection. Then the virtual interaction of the edge currents between related images is studied by imitating the electro-magnetic interaction between current-carrying wires. Based on the virtual interaction force between two related images, a novel method is presented and applied in image matching for shifting transformation. The preliminary experimental results indicate the effectiveness of the proposed method.