Emre Neftci, Charles Augustine, Somnath Paul, Georgios Detorakis
Subjects: Neural and Evolutionary Computing (cs.NE); Artificial Intelligence (cs.AI)
An ongoing challenge in neuromorphic computing is to devise general and
computationally efficient models of inference and learning which are compatible
with the spatial and temporal constraints of the brain. The gradient descent
backpropagation rule is a powerful algorithm that is ubiquitous in deep
learning, but it relies on the immediate availability of network-wide
information stored with high-precision memory. However, recent work shows that
exact backpropagated weights are not essential for learning deep
representations. Random backpropagation replaces feedback weights with random
ones and encourages the network to adjust its feed-forward weights to learn
pseudo-inverses of the (random) feedback weights. Here, we demonstrate an
event-driven random backpropagation (eRBP) rule that uses an error-modulated
synaptic plasticity for learning deep representations in neuromorphic computing
hardware. The rule is very suitable for implementation in neuromorphic hardware
using a two-compartment leaky integrate & fire neuron and a membrane-voltage
modulated, spike-driven plasticity rule. Our results show that using eRBP, deep
representations are rapidly learned without using backpropagated gradients,
achieving nearly identical classification accuracies compared to artificial
neural network simulations on GPUs, while being robust to neural and synaptic
state quantizations during learning.
Daniel Neil, Jun Haeng Lee, Tobi Delbruck, Shih-Chii Liu
Subjects: Neural and Evolutionary Computing (cs.NE)
Many neural networks exhibit stability in their activation patterns over time
in response to inputs from sensors operating under real-world conditions. By
capitalizing on this property of natural signals, we propose a Recurrent Neural
Network (RNN) architecture called a delta network in which each neuron
transmits its value only when the change in its activation exceeds a threshold.
The execution of RNNs as delta networks is attractive because their states must
be stored and fetched at every timestep, unlike in convolutional neural
networks (CNNs). We show that a naive run-time delta network implementation
offers modest improvements on the number of memory accesses and computes, but
optimized training techniques confer higher accuracy at higher speedup. With
these optimizations, we demonstrate a 9X reduction in cost with negligible loss
of accuracy for the TIDIGITS audio digit recognition benchmark. Similarly, on
the large Wall Street Journal speech recognition benchmark even existing
networks can be greatly accelerated as delta networks, and a 5.7x improvement
with negligible loss of accuracy can be obtained through training. Finally, on
an end-to-end CNN trained for steering angle prediction in a driving dataset,
the RNN cost can be reduced by a substantial 100X.
Boulif Menouar
Comments: 12 pages, 4 figures, unpublished work
Subjects: Discrete Mathematics (cs.DM); Neural and Evolutionary Computing (cs.NE)
Cell formation is a critical step in the design of cellular manufacturing
systems. Recently, it was tackled using a cut-based-graph-partitioning model.
This model meets real-life production systems requirements as it uses the
actual amount of product flows, it looks for the suitable number of cells, and
it takes into account the natural constraints such as operation sequences,
maximum cell size, cohabitation and non-cohabitation constraints. Based on this
model, we propose an original encoding representation to solve the problem by
using a genetic algorithm. We discuss the performance of this new GA in
comparison to some approaches taken from the literature on a set of medium
sized instances. Given the results we obtained, it is reasonable to assume that
the new GA will provide similar results for large real-life problems. Keywords:
Group Technology, Manufacturing Cell Formation, Graph Partitioning, Graph Cuts,
Genetic Algorithm, Encoding representation.
Christian F. Baumgartner, Konstantinos Kamnitsas, Jacqueline Matthew, Tara P. Fletcher, Sandra Smith, Lisa M. Koch, Bernhard Kainz, Daniel Rueckert
Comments: 10 pages, 6 figures, under review in IEEE Transactions in Medical Imaging
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Identifying and interpreting fetal standard scan planes during 2D ultrasound
mid-pregnancy examinations are highly complex tasks which require years of
training. Apart from guiding the probe to the correct location, it can be
equally difficult for a non-expert to identify relevant structures within the
image. Automatic image processing can provide tools to help experienced as well
as inexperienced operators with these tasks. In this paper, we propose a novel
method based on convolutional neural networks which can automatically detect 13
fetal standard views in freehand 2D ultrasound data as well as provide a
localisation of the fetal structures via a bounding box. An important
contribution is that the network learns to localise the target anatomy using
weak supervision only. The network architecture is designed to operate in
real-time while providing optimal output for the localisation task. We present
results for real-time annotation, retrospective frame retrieval from saved
videos, and localisation on a very large and challenging dataset consisting of
images and video recordings of full clinical anomaly screenings. The proposed
method annotated video frames with an average F1-score of 0.86, and obtained a
90.09% accuracy for retrospective frame retrieval. Moreover, we achieved an
accuracy of 77.8% on the localisation task.
Filippo Arcadu, Marco Stampanoni, Federica Marone
Subjects: Computer Vision and Pattern Recognition (cs.CV)
The performance of an iterative reconstruction algorithm for X-ray tomography
is strongly determined by the features of the used forward and backprojector.
For this reason, a large number of studies has focused on the to design of
projectors with increasingly higher accuracy and speed. To what extent the
accuracy of an iterative algorithm is affected by the mathematical affinity and
the similarity between the actual implementation of the forward and
backprojection, referred here as “coupling projector-backprojector”, has been
an overlooked aspect so far. The experimental study presented here shows that
the reconstruction quality and the convergence of an iterative algorithm
greatly rely on a good matching between the implementation of the tomographic
operators. In comparison, other aspects like the accuracy of the standalone
operators, the usage of physical constraints or the choice of stopping criteria
may even play a less relevant role.
Varun Jampani, Raghudeep Gadde, Peter V. Gehler
Subjects: Computer Vision and Pattern Recognition (cs.CV)
In this paper we propose a technique that propagates information forward
through video data. The method is conceptually simple and can be applied to
tasks that require the propagation of structured information, such as semantic
labels, based on video content. We propose a ‘Video Propagation Network’ that
processes video frames in an adaptive manner. The model is applied online: it
propagates information forward without the need to access future frames other
than the current ones. In particular, we combine two components, a temporal
bilateral network for dense and video adaptive filtering, followed by a spatial
network to refine features and increased flexibility. We present experiments on
video object segmentation and semantic video segmentation and show increased
performance comparing to the best previous task-specific methods, while having
favorable runtime. Additionally we demonstrate our approach on an example
regression task of propagating color in a grayscale video.
Paul Swoboda, Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmueller, Bogdan Savchynskyy
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We study the quadratic assignment problem, in computer vision also known as
graph matching. Two leading solvers for this problem optimize the Lagrange
decomposition duals with sub-gradient and dual ascent (also known as message
passing) updates. We explore s direction further and propose several additional
Lagrangean relaxations of the graph matching problem along with corresponding
algorithms, which are all based on a common dual ascent framework. Our
extensive empirical evaluation gives several theoretical insights and suggests
a new state-of-the-art any-time solver for the considered problem. Our
improvement over state-of-the-art is particularly visible on a new dataset with
large-scale sparse problem instances containing more than 500 graph nodes each.
Konstantinos Bousmalis, Nathan Silberman, David Dohan, Dumitru Erhan, Dilip Krishnan
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Collecting well-annotated image datasets to train modern machine learning
algorithms is prohibitively expensive for many tasks. One appealing alternative
is rendering synthetic data where ground-truth annotations are generated
automatically. Unfortunately, models trained purely on rendered images often
fail to generalize to real images. To address this shortcoming, prior work
introduced unsupervised domain adaptation algorithms that attempt to map
representations between the two domains or learn to extract features that are
domain-invariant. In this work, we present a new approach that learns, in an
unsupervised manner, a transformation in the pixel space from one domain to the
other. Our generative adversarial network (GAN)-based method adapts
source-domain images to appear as if drawn from the target domain. Our approach
not only produces plausible samples, but also outperforms the state-of-the-art
on a number of unsupervised domain adaptation scenarios by large margins.
Finally, we demonstrate that the adaptation process generalizes to object
classes unseen during training.
Sailesh Conjeti, Abhijit Guha Roy, Amin Katouzian, Nassir Navab
Comments: Submitted to Information Processing in Medical Imaging, 2017 (Under review)
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Hashing aims at generating highly compact similarity preserving code words
which are well suited for large-scale image retrieval tasks.
Most existing hashing methods first encode the images as a vector of
hand-crafted features followed by a separate binarization step to generate hash
codes. This two-stage process may produce sub-optimal encoding. In this paper,
for the first time, we propose a deep architecture for supervised hashing
through residual learning, termed Deep Residual Hashing (DRH), for an
end-to-end simultaneous representation learning and hash coding. The DRH model
constitutes four key elements: (1) a sub-network with multiple stacked residual
blocks; (2) hashing layer for binarization; (3) supervised retrieval loss
function based on neighbourhood component analysis for similarity preserving
embedding; and (4) hashing related losses and regularisation to control the
quantization error and improve the quality of hash coding. We present results
of extensive experiments on a large public chest x-ray image database with
co-morbidities and discuss the outcome showing substantial improvements over
the latest state-of-the art methods.
Peng Wang, Qi Wu, Chunhua Shen, Anton van den Hengel
Subjects: Computer Vision and Pattern Recognition (cs.CV)
One of the most intriguing features of the Visual Question Answering (VQA)
challenge is the unpredictability of the questions. Extracting the information
required to answer them demands a variety of image operations from detection
and counting, to segmentation and reconstruction. To train a method to perform
even one of these operations accurately from {image,question,answer} tuples
would be challenging, but to aim to achieve them all with a limited set of such
training data seems ambitious at best. We propose here instead a more general
and scalable approach which exploits the fact that very good methods to achieve
these operations already exist, and thus do not need to be trained. Our method
thus learns how to exploit a set of external off-the-shelf algorithms to
achieve its goal, an approach that has something in common with the Neural
Turing Machine. The core of our proposed method is a new co-attention model. In
addition, the proposed approach generates human-readable reasons for its
decision, and can still be trained end-to-end without ground truth reasons
being given. We demonstrate the effectiveness on two publicly available
datasets, Visual Genome and VQA, and show that it produces the state-of-the-art
results in both cases.
Baochang Zhang, Zhigang Li, Xianbin Cao, Qixiang Ye, Chen Chen, Linlin Shen, Alessandro Perina, Rongrong Ji
Comments: arXiv admin note: text overlap with arXiv:1404.7584 by other authors
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Kernelized Correlation Filter (KCF) is one of the state-of-the-art object
trackers. However, it does not reasonably model the distribution of correlation
response during tracking process, which might cause the drifting problem,
especially when targets undergo significant appearance changes due to
occlusion, camera shaking, and/or deformation. In this paper, we propose an
Output Constraint Transfer (OCT) method that by modeling the distribution of
correlation response in a Bayesian optimization framework is able to mitigate
the drifting problem. OCT builds upon the reasonable assumption that the
correlation response to the target image follows a Gaussian distribution, which
we exploit to select training samples and reduce model uncertainty. OCT is
rooted in a new theory which transfers data distribution to a constraint of the
optimized variable, leading to an efficient framework to calculate correlation
filters. Extensive experiments on a commonly used tracking benchmark show that
the proposed method significantly improves KCF, and achieves better performance
than other state-of-the-art trackers. To encourage further developments, the
source code is made available this https URL
Wei Shen, Rujie Liu
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Face attributes are interesting due to their detailed description of human
faces. Unlike prior research working on attribute prediction, we address an
inverse and more challenging problem called face attribute manipulation which
aims at modifying a face image according to a given attribute value. In order
to obtain an efficient representation for the manipulation, we propose to learn
the corresponding residual image which is defined as the difference between
images after and before the manipulation. Using the residual image, the
manipulation can be operated efficiently with modest pixel modification. The
framework of our approach is based on the Generative Adversarial Network. It
consists of two image transformation networks imitating the attribute
manipulation and its dual operation and a shared discriminative network
distinguishing the generated images from different reference images. We also
apply dual learning to allow the two transformation networks to learn from each
other. Experiments show that the learned residual images successfully simulate
the manipulations and the generated images retain most of the details in
attribute-irrelevant areas.
Dong Nie, Roger Trullo, Caroline Petitjean, Su Ruan, Dinggang Shen
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Computed tomography (CT) is critical for various clinical applications, e.g.,
radiotherapy treatment planning and also PET attenuation correction. However,
CT exposes radiation during acquisition, which may cause side effects to
patients. Compared to CT, magnetic resonance imaging (MRI) is much safer and
does not involve any radiations. Therefore, recently, researchers are greatly
motivated to estimate CT image from its corresponding MR image of the same
subject for the case of radiotherapy planning. In this paper, we propose a
data-driven approach to address this challenging problem. Specifically, we
train a fully convolutional network to generate CT given an MR image. To better
model the nonlinear relationship from MRI to CT and to produce more realistic
images, we propose to use the adversarial training strategy and an image
gradient difference loss function. We further apply AutoContext Model to
implement a context-aware generative adversarial network. Experimental results
show that our method is accurate and robust for predicting CT images from MRI
images, and also outperforms three state-of-the-art methods under comparison.
Tran Minh Quan, David G. C. Hilderbrand, Won-Ki Jeong
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Electron microscopic connectomics is an ambitious research direction with the
goal of studying comprehensive brain connectivity maps by using
high-throughput, nano-scale microscopy. One of the main challenges in
connectomics research is developing scalable image analysis algorithms that
require minimal user intervention. Recently, deep learning has drawn much
attention in computer vision because of its exceptional performance in image
classification tasks. For this reason, its application to connectomic analyses
holds great promise, as well. In this paper, we introduce a novel deep neural
network architecture, FusionNet, for the automatic segmentation of neuronal
structures in connectomics data. FusionNet leverages the latest advances in
machine learning, such as semantic segmentation and residual neural networks,
with the novel introduction of summation-based skip connections to allow a much
deeper network architecture for a more accurate segmentation. We demonstrate
the performance of the proposed method by comparing it with state-of-the-art
electron microscopy (EM) segmentation methods from the ISBI EM segmentation
challenge. We also show the segmentation results on two different tasks
including cell membrane and cell body segmentation and a statistical analysis
of cell morphology.
Ashton Fagg, Simon Lucey, Sridha Sridharan
Subjects: Computer Vision and Pattern Recognition (cs.CV)
In this paper, we present our method for enabling dense SDM to run at over 90
FPS on a mobile device. Our contributions are two-fold. Drawing inspiration
from the FFT, we propose a Sparse Compositional Regression (SCR) framework,
which enables a significant speed up over classical dense regressors. Second,
we propose a binary approximation to SIFT features. Binary Approximated SIFT
(BASIFT) features, which are a computationally efficient approximation to SIFT,
a commonly used feature with SDM. We demonstrate the performance of our
algorithm on an iPhone 7, and show that we achieve similar accuracy to SDM.
Alexis Arnaudon, Darryl D. Holm, Akshay Pai, Stefan Sommer
Subjects: Computer Vision and Pattern Recognition (cs.CV); Numerical Analysis (math.NA)
In the study of shapes of human organs using computational anatomy,
variations are found to arise from inter-subject anatomical differences,
disease-specific effects, and measurement noise. This paper introduces a
stochastic model for incorporating random variations into the Large Deformation
Diffeomorphic Metric Mapping (LDDMM) framework. By accounting for randomness in
a particular setup which is crafted to fit the geometrical properties of LDDMM,
we formulate the template estimation problem for landmarks with noise and give
two methods for efficiently estimating the parameters of the noise fields from
a prescribed data set. One method directly approximates the time evolution of
the variance of each landmark by a finite set of differential equations, and
the other is based on an Expectation-Maximisation algorithm. In the second
method, the evaluation of the data likelihood is achieved without registering
the landmarks, by applying bridge sampling using a stochastically perturbed
version of the large deformation gradient flow algorithm. The method and the
estimation algorithms are experimentally validated on synthetic examples and
shape data of human corpora callosa.
Yutong Zheng, Chenchen Zhu, Khoa Luu, Chandrasekhar Bhagavatula, T. Hoang Ngan Le, Marios Savvides
Comments: arXiv admin note: substantial text overlap with arXiv:1606.05413
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Robust face detection is one of the most important pre-processing steps to
support facial expression analysis, facial landmarking, face recognition, pose
estimation, building of 3D facial models, etc. Although this topic has been
intensely studied for decades, it is still challenging due to numerous variants
of face images in real-world scenarios. In this paper, we present a novel
approach named Multiple Scale Faster Region-based Convolutional Neural Network
(MS-FRCNN) to robustly detect human facial regions from images collected under
various challenging conditions, e.g. large occlusions, extremely low
resolutions, facial expressions, strong illumination variations, etc. The
proposed approach is benchmarked on two challenging face detection databases,
i.e. the Wider Face database and the Face Detection Dataset and Benchmark
(FDDB), and compared against recent other face detection methods, e.g.
Two-stage CNN, Multi-scale Cascade CNN, Faceness, Aggregate Chanel Features,
HeadHunter, Multi-view Face Detection, Cascade CNN, etc. The experimental
results show that our proposed approach consistently achieves highly
competitive results with the state-of-the-art performance against other recent
face detection methods.
Paul Swoboda, Jan Kuske, Bogdan Savchynskyy
Subjects: Data Structures and Algorithms (cs.DS); Computer Vision and Pattern Recognition (cs.CV)
We propose a general dual ascent framework for Lagrangean decomposition of
combinatorial problems. Although methods of this type have shown their
efficiency for a number of problems, so far there was no general algorithm
applicable to multiple problem types. In his work, we propose such a general
algorithm. It depends on several parameters, which can be used to optimize its
performance in each particular setting. We demonstrate efficacy of our method
on graph matching and multicut problems, where it outperforms state-of-the-art
solvers including those based on subgradient optimization and off-the-shelf
linear programming solvers.
Paul Swoboda, Bjoern Andres
Subjects: Data Structures and Algorithms (cs.DS); Computer Vision and Pattern Recognition (cs.CV)
We propose a dual decomposition and linear program relaxation of the NP -hard
minimum cost multicut problem. Unlike other polyhedral relaxations of the
multicut polytope, it is amenable to efficient optimization by message passing.
Like other polyhedral elaxations, it can be tightened efficiently by cutting
planes. We define an algorithm that alternates between message passing and
efficient separation of cycle- and odd-wheel inequalities. This algorithm is
more efficient than state-of-the-art algorithms based on linear programming,
including algorithms written in the framework of leading commercial software,
as we show in experiments with large instances of the problem from applications
in computer vision, biomedical image analysis and data mining.
Dorian Tsai, Donald G. Dansereau, Steve Martin, Peter Corke
Comments: tech report, v0.5, 15 pages, 6 figures
Subjects: Robotics (cs.RO); Computer Vision and Pattern Recognition (cs.CV)
This paper proposes the design of a custom mirror-based light field camera
adapter that is cheap, simple in construction, and accessible. Mirrors of
different shape and orientation reflect the scene into an upwards-facing camera
to create an array of virtual cameras with overlapping field of view at
specified depths, and deliver video frame rate light fields. We describe the
design, construction, decoding and calibration processes of our mirror-based
light field camera adapter in preparation for an open-source release to benefit
the robotic vision community.
Kavosh Asadi, Michael L. Littman
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG); Machine Learning (stat.ML)
A softmax operator applied to a set of values acts somewhat like the
maximization function and somewhat like an average. In sequential decision
making, softmax is often used in settings where it is necessary to maximize
utility but also to hedge against problems that arise from putting all of one’s
weight behind a single maximum utility decision. The Boltzmann softmax operator
is the most commonly used softmax operator in this setting, but we show that
this operator is prone to misbehavior. In this work, we study an alternative
softmax operator that, among other properties, is both a non-expansion
(ensuring convergent behavior in learning and planning) and differentiable
(making it possible to improve decisions via gradient descent methods). We
provide proofs of these properties and present empirical comparisons between
various softmax operators.
Wen Jiang
Comments: 9 pages, 1 figure
Subjects: Artificial Intelligence (cs.AI)
The correlation coefficient is widely used to measure the similarity of
evidence in Dempster-Shafer evidence theory. However, existing correlation
coefficients of belief functions have some shortcomings. In this paper, a new
correlation coefficient is proposed with many desirable properties. One of its
applications is to measure the conflict degree among belief functions. Some
numerical examples and comparisons demonstrate the effectiveness of the
correlation coefficient.
Ndapandula Nakashole, Tom M. Mitchell
Comments: 28 pages
Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
Intelligent systems capable of automatically understanding natural language
text are important for many artificial intelligence applications including
mobile phone voice assistants, computer vision, and robotics. Understanding
language often constitutes fitting new information into a previously acquired
view of the world. However, many machine reading systems rely on the text alone
to infer its meaning. In this paper, we pursue a different approach; machine
reading methods that make use of background knowledge to facilitate language
understanding. To this end, we have developed two methods: The first method
addresses prepositional phrase attachment ambiguity. It uses background
knowledge within a semi-supervised machine learning algorithm that learns from
both labeled and unlabeled data. This approach yields state-of-the-art results
on two datasets against strong baselines; The second method extracts
relationships from compound nouns. Our knowledge-aware method for compound noun
analysis accurately extracts relationships and significantly outperforms a
baseline that does not make use of background knowledge.
Hang Ma, T. K. Satish Kumar, Sven Koenig
Comments: To appear in AAAI 2017
Subjects: Artificial Intelligence (cs.AI); Robotics (cs.RO)
Several recently developed Multi-Agent Path Finding (MAPF) solvers scale to
large MAPF instances by searching for MAPF plans on 2 levels: The high-level
search resolves collisions between agents, and the low-level search plans paths
for single agents under the constraints imposed by the high-level search. We
make the following contributions to solve the MAPF problem with imperfect plan
execution with small average makespans: First, we formalize the MAPF Problem
with Delay Probabilities (MAPF-DP), define valid MAPF-DP plans and propose the
use of robust plan-execution policies for valid MAPF-DP plans to control how
each agent proceeds along its path. Second, we discuss 2 classes of
decentralized robust plan-execution policies (called Fully Synchronized
Policies and Minimal Communication Policies) that prevent collisions during
plan execution for valid MAPF-DP plans. Third, we present a 2-level MAPF-DP
solver (called Approximate Minimization in Expectation) that generates valid
MAPF-DP plans.
Emre Neftci, Charles Augustine, Somnath Paul, Georgios Detorakis
Subjects: Neural and Evolutionary Computing (cs.NE); Artificial Intelligence (cs.AI)
An ongoing challenge in neuromorphic computing is to devise general and
computationally efficient models of inference and learning which are compatible
with the spatial and temporal constraints of the brain. The gradient descent
backpropagation rule is a powerful algorithm that is ubiquitous in deep
learning, but it relies on the immediate availability of network-wide
information stored with high-precision memory. However, recent work shows that
exact backpropagated weights are not essential for learning deep
representations. Random backpropagation replaces feedback weights with random
ones and encourages the network to adjust its feed-forward weights to learn
pseudo-inverses of the (random) feedback weights. Here, we demonstrate an
event-driven random backpropagation (eRBP) rule that uses an error-modulated
synaptic plasticity for learning deep representations in neuromorphic computing
hardware. The rule is very suitable for implementation in neuromorphic hardware
using a two-compartment leaky integrate & fire neuron and a membrane-voltage
modulated, spike-driven plasticity rule. Our results show that using eRBP, deep
representations are rapidly learned without using backpropagated gradients,
achieving nearly identical classification accuracies compared to artificial
neural network simulations on GPUs, while being robust to neural and synaptic
state quantizations during learning.
Jingwei Zhang, Jost Tobias Springenberg, Joschka Boedecker, Wolfram Burgard
Subjects: Robotics (cs.RO); Artificial Intelligence (cs.AI); Learning (cs.LG)
In this paper we consider the problem of robot navigation in simple maze-like
environments where the robot has to rely on its onboard sensors to perform the
navigation task. In particular, we are interested in solutions to this
navigation task that do not require mapping and localization. Additionally, we
require that our solution can quickly adapt to new situations (e.g., changing
navigation goals and new environments). To meet these criteria we frame this
task as a sequence of reinforcement learning problems over related tasks. We
propose a successor feature based deep reinforcement learning algorithm that
can learn to transfer knowledge from previously mastered navigation tasks to
new problem instances. Our algorithm can substantially decrease the required
learning time after the first task instance has been solved, which makes it
easily adaptable to changing environments. We validate our method in both
simulated and real robot experiments with a Robotino and compare it to a set of
baseline methods including classical planning-based navigation.
Neil Seward
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI)
The National Basketball Association(NBA) has expanded their data gathering
and have heavily invested in new technologies to gather advanced performance
metrics on players. This expanded data set allows analysts to use unique
performance metrics in models to estimate and classify player performance.
Instead of grouping players together based on physical attributes and positions
played, analysts can group together players that play similar to each other
based on these tracked metrics. Existing methods for player classification have
typically used offensive metrics for clustering [1]. There have been attempts
to classify players using past defensive metrics, but the lack of quality
metrics has not produced promising results. The classifications presented in
the paper use newly introduced defensive metrics to find different defensive
positions for each player. Without knowing the number of categories that
players can be cast into, Gaussian Mixture Models (GMM) can be applied to find
the optimal number of clusters. In the model presented, five different
defensive player types can be identified.
Karl Ridgeway
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI)
With the resurgence of interest in neural networks, representation learning
has re-emerged as a central focus in artificial intelligence. Representation
learning refers to the discovery of useful encodings of data that make
domain-relevant information explicit. Factorial representations identify
underlying independent causal factors of variation in data. A factorial
representation is compact and faithful, makes the causal factors explicit, and
facilitates human interpretation of data. Factorial representations support a
variety of applications, including the generation of novel examples, indexing
and search, novelty detection, and transfer learning.
This article surveys various constraints that encourage a learning algorithm
to discover factorial representations. I dichotomize the constraints in terms
of unsupervised and supervised inductive bias. Unsupervised inductive biases
exploit assumptions about the environment, such as the statistical distribution
of factor coefficients, assumptions about the perturbations a factor should be
invariant to (e.g. a representation of an object can be invariant to rotation,
translation or scaling), and assumptions about how factors are combined to
synthesize an observation. Supervised inductive biases are constraints on the
representations based on additional information connected to observations.
Supervisory labels come in variety of types, which vary in how strongly they
constrain the representation, how many factors are labeled, how many
observations are labeled, and whether or not we know the associations between
the constraints and the factors they are related to.
This survey brings together a wide variety of models that all touch on the
problem of learning factorial representations and lays out a framework for
comparing these models based on the strengths of the underlying supervised and
unsupervised inductive biases.
Yongqing Liang, Cheng Jin, Yuejie Zhang
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
In this paper, we establish a novel bottom-up cue named Convex Hull Overlap
(CHO), and then propose an effective approach to detect salient regions using
the combination of the CHO cue and global contrast cue. Our scheme
significantly differs from other earlier work in: 1) The hierarchical
segmentation model based on Normalized Graph-Cut fits the splitting and merging
processes in human visual perception; 2) Previous work only focuses on color
and texture cues, while our CHO cue makes up the obvious gap between the
spatial region covering and the region saliency. CHO is a kind of improved and
enhanced Gestalt cue, while other popular figure-ground cues such as convexity
and surroundedness can be regarded as the special cases of CHO. Our experiments
on a large number of public data have obtained very positive results.
Gerhard Gossen, Elena Demidova, Thomas Risse
Comments: Published in the proceedings of the 8th ACM Conference on Web Science 2016
Journal-ref: Proceedings of the 8th ACM Conference on Web Science (2016, pp.
291–295)
Subjects: Digital Libraries (cs.DL); Information Retrieval (cs.IR)
Web archives capture the history of the Web and are therefore an important
source to study how societal developments have been reflected on the Web.
However, the large size of Web archives and their temporal nature pose many
challenges to researchers interested in working with these collections. In this
work, we describe the challenges of working with Web archives and propose the
research methodology of extracting and studying sub-collections of the archive
focused on specific topics and events. We discuss the opportunities and
challenges of this approach and suggest a framework for creating
sub-collections.
Álvaro Peris, Mara Chinea-Rios, Francisco Casacuberta
Subjects: Computation and Language (cs.CL)
We address the data selection problem in statistical machine translation
(SMT) as a classification task. The new data selection method is based on a
neural network classifier. We present a new method description and empirical
results proving that our data selection method provides better translation
quality, compared to a state-of-the-art method (i.e., Cross entropy). Moreover,
the empirical results reported are coherent across different language pairs.
Arkanath Pathak, Pawan Goyal, Plaban Bhowmick
Comments: Presented at NLPTEA 2016, held in conjunction with COLING 2016
Subjects: Computation and Language (cs.CL)
We propose a new approach for extracting argument structure from natural
language texts that contain an underlying argument. Our approach comprises of
two phases: Score Assignment and Structure Prediction. The Score Assignment
phase trains models to classify relations between argument units (Support,
Attack or Neutral). To that end, different training strategies have been
explored. We identify different linguistic and lexical features for training
the classifiers. Through ablation study, we observe that our novel use of
word-embedding features is most effective for this task. The Structure
Prediction phase makes use of the scores from the Score Assignment phase to
arrive at the optimal structure. We perform experiments on three argumentation
datasets, namely, AraucariaDB, Debatepedia and Wikipedia. We also propose two
baselines and observe that the proposed approach outperforms baseline systems
for the final task of Structure Prediction.
Shraey Bhatia, Jey Han Lau, Timothy Baldwin
Comments: 11 pages, 3 figures, published in COLING2016
Journal-ref: Proceedings of the 26th International Conference on Computational
Linguistics (COLING 2016), pp 953–963
Subjects: Computation and Language (cs.CL)
Topics generated by topic models are typically represented as list of terms.
To reduce the cognitive overhead of interpreting these topics for end-users, we
propose labelling a topic with a succinct phrase that summarises its theme or
idea. Using Wikipedia document titles as label candidates, we compute neural
embeddings for documents and words to select the most relevant labels for
topics. Compared to a state-of-the-art topic labelling system, our methodology
is simpler, more efficient, and finds better topic labels.
Luis Gerardo Mojica, Vincent Ng
Subjects: Computation and Language (cs.CL)
Social media websites, electronic newspapers and Internet forums allow
visitors to leave comments for others to read and interact. This exchange is
not free from participants with malicious intentions, who troll others by
positing messages that are intended to be provocative, offensive, or menacing.
With the goal of facilitating the computational modeling of trolling, we
propose a trolling categorization that is novel in the sense that it allows
comment-based analysis from both the trolls’ and the responders’ perspectives,
characterizing these two perspectives using four aspects, namely, the troll’s
intention and his intention disclosure, as well as the responder’s
interpretation of the troll’s intention and her response strategy. Using this
categorization, we annotate and release a dataset containing excerpts of Reddit
conversations involving suspected trolls and their interactions with other
users. Finally, we identify the difficult-to-classify cases in our corpus and
suggest potential solutions for them.
Eric S. Tellez, Sabino Miranda Jiménez, Mario Graff, Daniela Moctezuma, Ranyart R. Suárez, Oscar S. Siordia
Subjects: Computation and Language (cs.CL); Learning (cs.LG); Machine Learning (stat.ML)
Recently, sentiment analysis has received a lot of attention due to the
interest in mining opinions of social media users. Sentiment analysis consists
in determining the polarity of a given text, i.e., its degree of positiveness
or negativeness. Traditionally, Sentiment Analysis algorithms have been
tailored to a specific language given the complexity of having a number of
lexical variations and errors introduced by the people generating content. In
this contribution, our aim is to provide a simple to implement and easy to use
multilingual framework, that can serve as a baseline for sentiment analysis
contests, and as starting point to build new sentiment analysis systems. We
compare our approach in eight different languages, three of them have important
international contests, namely, SemEval (English), TASS (Spanish), and
SENTIPOLC (Italian). Within the competitions our approach reaches from medium
to high positions in the rankings; whereas in the remaining languages our
approach outperforms the reported results.
Ndapandula Nakashole, Tom M. Mitchell
Comments: 28 pages
Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
Intelligent systems capable of automatically understanding natural language
text are important for many artificial intelligence applications including
mobile phone voice assistants, computer vision, and robotics. Understanding
language often constitutes fitting new information into a previously acquired
view of the world. However, many machine reading systems rely on the text alone
to infer its meaning. In this paper, we pursue a different approach; machine
reading methods that make use of background knowledge to facilitate language
understanding. To this end, we have developed two methods: The first method
addresses prepositional phrase attachment ambiguity. It uses background
knowledge within a semi-supervised machine learning algorithm that learns from
both labeled and unlabeled data. This approach yields state-of-the-art results
on two datasets against strong baselines; The second method extracts
relationships from compound nouns. Our knowledge-aware method for compound noun
analysis accurately extracts relationships and significantly outperforms a
baseline that does not make use of background knowledge.
Karan Mitra, Saguna Saguna, Christer Åhlund, Rajiv Ranjan
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Cloud performance diagnosis and prediction is a challenging problem due to
the stochastic nature of the cloud systems. Cloud performance is affected by a
large set of factors including (but not limited to) virtual machine types,
regions, workloads, wide area network delay and bandwidth. Therefore,
necessitating the determination of complex relationships between these factors.
The current research in this area does not address the challenge of building
models that capture the uncertain and complex relationships between these
factors. Further, the challenge of cloud performance prediction under
uncertainty has not garnered sufficient attention. This paper proposes develops
and validates ALPINE, a Bayesian system for cloud performance diagnosis and
prediction. ALPINE incorporates Bayesian networks to model uncertain and
complex relationships between several factors mentioned above. It handles
missing, scarce and sparse data to diagnose and predict stochastic cloud
performance efficiently. We validate our proposed system using extensive real
data and trace-driven analysis and show that it predicts cloud performance with
high accuracy of 91.93%.
Seiichiro Tani
Comments: 26 pages, accepted for publication in Quantum Information and Computation (QIC)
Subjects: Quantum Physics (quant-ph); Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)
Solitude verification is arguably one of the simplest fundamental problems in
distributed computing, where the goal is to verify that there is a unique
contender in a network. This paper devises a quantum algorithm that exactly
solves the problem on an anonymous network, which is known as a network model
with minimal assumptions [Angluin, STOC’80]. The algorithm runs in (O(N))
rounds if every party initially has the common knowledge of an upper bound (N)
on the number of parties. This implies that all solvable problems can be solved
in (O(N)) rounds on average without error (i.e., with zero-sided error) on the
network. As a generalization, a quantum algorithm that works in (O(Nlog_2
(max{k,2}))) rounds is obtained for the problem of exactly computing any
symmetric Boolean function, over (n) distributed input bits, which is constant
over all the (n) bits whose sum is larger than (k) for (kin {0,1,dots,
N-1}). All these algorithms work with the bit complexities bounded by a
polynomial in (N).
Giulio Ruffini
Subjects: Learning (cs.LG)
I aim to show that models, classification or generating functions,
invariances and datasets are algorithmically equivalent concepts once properly
defined, and provide some concrete examples of them. I then show that a) neural
networks (NNs) of different kinds can be seen to implement models, b) that
perturbations of inputs and nodes in NNs trained to optimally implement simple
models propagate strongly, c) that there is a framework in which recurrent,
deep and shallow networks can be seen to fall into a descriptive power
hierarchy in agreement with notions from the theory of recursive functions. The
motivation for these definitions and following analysis lies in the context of
cognitive neuroscience, and in particular in Ruffini (2016), where the concept
of model is used extensively, as is the concept of algorithmic complexity.
Neil Seward
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI)
The National Basketball Association(NBA) has expanded their data gathering
and have heavily invested in new technologies to gather advanced performance
metrics on players. This expanded data set allows analysts to use unique
performance metrics in models to estimate and classify player performance.
Instead of grouping players together based on physical attributes and positions
played, analysts can group together players that play similar to each other
based on these tracked metrics. Existing methods for player classification have
typically used offensive metrics for clustering [1]. There have been attempts
to classify players using past defensive metrics, but the lack of quality
metrics has not produced promising results. The classifications presented in
the paper use newly introduced defensive metrics to find different defensive
positions for each player. Without knowing the number of categories that
players can be cast into, Gaussian Mixture Models (GMM) can be applied to find
the optimal number of clusters. In the model presented, five different
defensive player types can be identified.
Jie Liu, Martin Takac
Subjects: Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)
We propose a projected semi-stochastic gradient descent method with
mini-batch for improving both the theoretical complexity and practical
performance of the general stochastic gradient descent method (SGD). We are
able to prove linear convergence under weak strong convexity assumption. This
requires no strong convexity assumption for minimizing the sum of smooth convex
functions subject to a compact polyhedral set, which remains popular across
machine learning community. Our PS2GD preserves the low-cost per iteration and
high optimization accuracy via stochastic gradient variance-reduced technique,
and admits a simple parallel implementation with mini-batches. Moreover, PS2GD
is also applicable to dual problem of SVM with hinge loss.
Karl Ridgeway
Subjects: Learning (cs.LG); Artificial Intelligence (cs.AI)
With the resurgence of interest in neural networks, representation learning
has re-emerged as a central focus in artificial intelligence. Representation
learning refers to the discovery of useful encodings of data that make
domain-relevant information explicit. Factorial representations identify
underlying independent causal factors of variation in data. A factorial
representation is compact and faithful, makes the causal factors explicit, and
facilitates human interpretation of data. Factorial representations support a
variety of applications, including the generation of novel examples, indexing
and search, novelty detection, and transfer learning.
This article surveys various constraints that encourage a learning algorithm
to discover factorial representations. I dichotomize the constraints in terms
of unsupervised and supervised inductive bias. Unsupervised inductive biases
exploit assumptions about the environment, such as the statistical distribution
of factor coefficients, assumptions about the perturbations a factor should be
invariant to (e.g. a representation of an object can be invariant to rotation,
translation or scaling), and assumptions about how factors are combined to
synthesize an observation. Supervised inductive biases are constraints on the
representations based on additional information connected to observations.
Supervisory labels come in variety of types, which vary in how strongly they
constrain the representation, how many factors are labeled, how many
observations are labeled, and whether or not we know the associations between
the constraints and the factors they are related to.
This survey brings together a wide variety of models that all touch on the
problem of learning factorial representations and lays out a framework for
comparing these models based on the strengths of the underlying supervised and
unsupervised inductive biases.
Ben D Fulcher, Nick S Jones
Subjects: Learning (cs.LG); Data Analysis, Statistics and Probability (physics.data-an); Quantitative Methods (q-bio.QM)
Across a far-reaching diversity of scientific and industrial applications, a
general key problem involves relating the structure of time-series data to a
meaningful outcome, such as detecting anomalous events from sensor recordings,
or diagnosing patients from physiological time-series measurements like heart
rate or brain activity. Currently, researchers must devote considerable effort
manually devising, or searching for, properties of their time series that are
suitable for the particular analysis problem at hand. Addressing this
non-systematic and time-consuming procedure, here we introduce a new tool,
hctsa, that selects interpretable and useful properties of time series
automatically, by comparing implementations over 7700 time-series features
drawn from diverse scientific literatures. Using two exemplar biological
applications, we show how hctsa allows researchers to leverage decades of
time-series research to quantify and understand informative structure in their
time-series data.
Kavosh Asadi, Michael L. Littman
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG); Machine Learning (stat.ML)
A softmax operator applied to a set of values acts somewhat like the
maximization function and somewhat like an average. In sequential decision
making, softmax is often used in settings where it is necessary to maximize
utility but also to hedge against problems that arise from putting all of one’s
weight behind a single maximum utility decision. The Boltzmann softmax operator
is the most commonly used softmax operator in this setting, but we show that
this operator is prone to misbehavior. In this work, we study an alternative
softmax operator that, among other properties, is both a non-expansion
(ensuring convergent behavior in learning and planning) and differentiable
(making it possible to improve decisions via gradient descent methods). We
provide proofs of these properties and present empirical comparisons between
various softmax operators.
Jingwei Zhang, Jost Tobias Springenberg, Joschka Boedecker, Wolfram Burgard
Subjects: Robotics (cs.RO); Artificial Intelligence (cs.AI); Learning (cs.LG)
In this paper we consider the problem of robot navigation in simple maze-like
environments where the robot has to rely on its onboard sensors to perform the
navigation task. In particular, we are interested in solutions to this
navigation task that do not require mapping and localization. Additionally, we
require that our solution can quickly adapt to new situations (e.g., changing
navigation goals and new environments). To meet these criteria we frame this
task as a sequence of reinforcement learning problems over related tasks. We
propose a successor feature based deep reinforcement learning algorithm that
can learn to transfer knowledge from previously mastered navigation tasks to
new problem instances. Our algorithm can substantially decrease the required
learning time after the first task instance has been solved, which makes it
easily adaptable to changing environments. We validate our method in both
simulated and real robot experiments with a Robotino and compare it to a set of
baseline methods including classical planning-based navigation.
Pengfei Sun, Jun Qin
Comments: 14 pages
Subjects: Sound (cs.SD); Learning (cs.LG)
In this paper, we describe three neural network (NN) based EEG-Speech (NES)
models that map the unspoken EEG signals to the corresponding phonemes. Instead
of using conventional feature extraction techniques, the proposed NES models
rely on graphic learning to project both EEG and speech signals into deep
representation feature spaces. This NN based linear projection helps to realize
multimodal data fusion (i.e., EEG and acoustic signals). It is convenient to
construct the mapping between unspoken EEG signals and phonemes. Specifically,
among three NES models, two augmented models (i.e., IANES-B and IANES-G)
include spoken EEG signals as either bias or gate information to strengthen the
feature learning and translation of unspoken EEG signals. A combined
unsupervised and supervised training is implemented stepwise to learn the
mapping for all three NES models. To enhance the computational performance,
three way factored NN training technique is applied to IANES-G model. Unlike
many existing methods, our augmented NES models incorporate spoken-EEG signals
that can efficiently suppress the artifacts in unspoken-EEG signals.
Experimental results reveal that all three proposed NES models outperform the
baseline SVM method, whereas IANES-G demonstrates the best performance on
speech recovery and classification task comparatively.
Eric S. Tellez, Sabino Miranda Jiménez, Mario Graff, Daniela Moctezuma, Ranyart R. Suárez, Oscar S. Siordia
Subjects: Computation and Language (cs.CL); Learning (cs.LG); Machine Learning (stat.ML)
Recently, sentiment analysis has received a lot of attention due to the
interest in mining opinions of social media users. Sentiment analysis consists
in determining the polarity of a given text, i.e., its degree of positiveness
or negativeness. Traditionally, Sentiment Analysis algorithms have been
tailored to a specific language given the complexity of having a number of
lexical variations and errors introduced by the people generating content. In
this contribution, our aim is to provide a simple to implement and easy to use
multilingual framework, that can serve as a baseline for sentiment analysis
contests, and as starting point to build new sentiment analysis systems. We
compare our approach in eight different languages, three of them have important
international contests, namely, SemEval (English), TASS (Spanish), and
SENTIPOLC (Italian). Within the competitions our approach reaches from medium
to high positions in the rankings; whereas in the remaining languages our
approach outperforms the reported results.
Minjia Shi, Yue Guan
Subjects: Information Theory (cs.IT)
We construct a family of two-Lee-weight codes over the ring (R_k,) which is
defined as trace codes with algebraic structure of abelian codes. The Lee
weight distribution of the two-weight codes is given. Taking the Gray map, we
obtain optimal abelian binary two-weight codes by using the Griesmer bound. An
application to secret sharing schemes is also given.
Juan Wen, Kaibin Huang, Sheng Yang, Victor O. K. Li
Comments: 29 pages, 7 figures
Subjects: Information Theory (cs.IT)
Caching popular contents at BSs of a HCN reduces latency and alleviates
traffic congestion in backhaul links. Due to the complexity of
network-performance analysis, the optimal strategies for content placement in
HCNs remain largely unknown. To this end, we adopt the popular random HCN model
where (K) tiers of BS are modelled as independent PPPs. Further, the random
caching scheme is considered. We consider the network-performance metric, hit
probability, defined as the probability that a file requested by the typical
user is delivered successfully to the user. Leveraging existing results on HCN
performance, we maximize the hit probability over content placement
probabilities, which yields the optimal placement policies. For the case of
uniform received signal-to-interference thresholds, the policy is in
closed-form where the placement probability for a particular file is
proportional to the square-root of the corresponding popularity measure with an
offset depending on BS caching capacities. For the general case of non-uniform
SIR threshold, the optimization problem is non-convex and a sub-optimal
placement policy is designed by approximation, which is shown by simulation to
be close-to-optimal.
Cenk Albayrak, Cemaleddin Simsek, Kadir Turk
Comments: Submitted to IET Electronic Letters
Subjects: Information Theory (cs.IT)
In this paper, we propose a new early termination method (ETM) for Luby
transform (LT) belief propagation (BP) decoder. The proposed ETM, which we call
least reliable messages (LRM), observes only sign alterations of a small
cluster in log-likelihood ratio (LLR) messages passing between nodes in BP
decoder. Simulation results and complexity analyzes show that LRM significantly
lower computational complexity of early termination section in decoder without
any performance degradation and decreases the average decoding iteration
amounts compared to conventional ETMs in literature. The method can be easily
applied to code families which can be decoded by BP such as low density parity
check (LDPC) codes, polar codes and Raptor codes.
Krishna Kaipa
Subjects: Information Theory (cs.IT); Combinatorics (math.CO)
We study the problem of classifying deep holes of Reed-Solomon codes. We show
that this problem is equivalent to the problem of classifying MDS extensions of
Reed-Solomon codes by one digit. This equivalence allows us to improve recent
results on the former problem. In particular, we classify deep holes of
Reed-Solomon codes of dimension greater than half the alphabet size.
We also give a complete classification of deep holes of Reed Solomon codes
with redundancy three in all dimensions.
Peng Deng, Mohsen Kavehrad
Comments: 3 pages, 3 figures, accepted by OFC 2017
Subjects: Information Theory (cs.IT)
We experimentally demonstrate a software-defined 2×2 MIMO VLC system
employing link adaptation of spatial multiplexing and diversity. The average
error-free spectral efficiency of 12 b/s/Hz is achieved over 2 meters indoor
transmission after an obstruction.
Kang Gao, Mingming Cai, Ding Nie, Bertrand Hochwald, J. Nicholas Laneman, Huang Huang, Kunpeng Liu
Comments: 6 pages, to be published in Proc. IEEE GLOBECOM 2016, Washington, D.C., USA
Subjects: Information Theory (cs.IT)
We present a tracking algorithm to maintain the communication link between a
base station (BS) and a mobile station (MS) in a millimeter wave (mmWave)
communication system, where antenna arrays are used for beamforming in both the
BS and MS. Downlink transmission is considered, and the tracking is performed
at the MS as it moves relative to the BS. Specifically, we consider the case
that the MS rotates quickly due to hand movement. The algorithm estimates the
angle of arrival (AoA) by using variations in the radiation pattern of the beam
as a function of this angle. Numerical results show that the algorithm achieves
accurate beam alignment when the MS rotates in a wide range of angular speeds.
For example, the algorithm can support angular speeds up to 800 degrees per
second when tracking updates are available every 10 ms.
Marco Mondelli, S. Hamed Hassani, Rüdiger Urbanke
Comments: 9 pages, 2 figures
Subjects: Information Theory (cs.IT)
Consider the problem of constructing a polar code of block length (N) for the
transmission over a given channel (W). Typically this requires to compute the
reliability of all the (N) synthetic channels and then to include those that
are sufficiently reliable. However, we know from [1], [2] that there is a
partial order among the synthetic channels. Hence, it is natural to ask whether
we can exploit it to reduce the computational burden of the construction
problem.
We show that, if we take advantage of the partial order [1], [2], we can
construct a polar code by computing the reliability of roughly a fraction
(1/log^{3/2} N) of the synthetic channels. In particular, we prove that
(N/log^{3/2} N) is a lower bound on the number of synthetic channels to be
considered and such a bound is tight up to a multiplicative factor (loglog
N). This set of roughly (N/log^{3/2} N) synthetic channels is universal, in
the sense that it allows one to construct polar codes for any (W), and it can
be computed by solving a maximum matching problem on a bipartite graph.
Our proof technique consists of reducing the construction problem to the
problem of computing the maximum cardinality of a chain and of an antichain for
a suitable partially ordered set. As such, this method is general and it can be
used to further improve the complexity of the construction problem in case a
new partial order on the synthetic channels of polar codes is discovered.
Donia Ben Amor, Hela Jedda, Josef A. Nossek
Comments: 5 pages, 6 figures, WSA 2017
Subjects: Information Theory (cs.IT)
We present a novel non-linear precoding technique for the transmission of 16
quadrature amplitude modulation (QAM) symbols in a 1-bit massive multi-user
(MU) multipleinput- single-output (MISO) downlink system. We deploy low
resolution digital-to-analog converters (DACs) at the transmitter for the sake
of decreasing the high energy consumption related to the massive MISO system.
To mitigate the multi-user interference (MUI) and the distortions due to the
low resolution DACs, the minimum bit error ratio (MBER) precoder was introduced
in previous work. However, this precoder technique is restricted to quadrature
phase shift keying (QPSK) signaling. Our approach consists in upgrading this
method to the transmission of 16 QAM symbols. Simulation results show that the
performance in terms of uncoded BER is significantly improved for larger
massive MISO gain.
Iharantsoa Vero Raharinirina
Subjects: Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM); Information Theory (cs.IT)
In this paper we consider cryptographic applications of the arithmetic on the
hyperoctahedral group. On an appropriate subgroup of the latter, we
particularly propose to construct public key cryptosystems based on the
discrete logarithm. The fact that the group of signed permutations has rich
properties provides fast and easy implementation and makes these systems
resistant to attacks like the Pohlig-Hellman algorithm. The only negative point
is that storing and transmitting permutations need large memory. Using together
the hyperoctahedral enumeration system and what is called subexceedant
functions, we define a one-to-one correspondance between natural numbers and
signed permutations with which we label the message units.
Carlos Aguilar, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Gilles Zémor
Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT)
We propose a framework for constructing efficient code-based encryption
schemes from codes that do not hide any structure in their public matrix. The
framework is in the spirit of the schemes first proposed by Alekhnovich in 2003
and based on the difficulty of decoding random linear codes from random errors
of low weight. We depart somewhat from Aleknovich’s approach and propose an
encryption scheme based on the difficulty of decoding random quasi-cyclic
codes. We propose two new cryptosystems instantiated within our framework: the
Hamming Quasi-Cyclic cryptosystem (HQC), based on the Hamming metric, and the
Rank Quasi-Cyclic cryptosystem (RQC), based on the rank metric. We give a
security proof, which reduces the IND-CPA security of our systems to a
decisional version of the well known problem of decoding random families of
quasi-cyclic codes for the Hamming and rank metrics (the respective QCSD and
RQCSD problems). We also provide an analysis of the decryption failure
probability of our scheme in the Hamming metric case: for the rank metric there
is no decryption failure. Our schemes benefit from a very fast decryption
algorithm together with small key sizes of only a few thousand bits. The
cryptosystems are very efficient for low encryption rates and are very well
suited to key exchange and authentication. Asymptotically, for lambda the
security parameter, the public key sizes are respectively in (O(lambda^{2}))
for HQC and in (O(lambda^{4/3})) for RQC. Practical parameter compares well to
systems based on ring-LPN or the recent MDPC system.
Moritz Wiese, Tobias J. Oechtering, Karl Henrik Johansson, Panos Papadimitratos, Henrik Sandberg, Mikael Skoglund
Comments: Submitted to IEEE Transactions on Automatic Control
Subjects: Systems and Control (cs.SY); Information Theory (cs.IT)
We study the problem of estimating the states of an unstable dynamical system
subject to nonstochastic disturbances. The estimator obtains all its
information through an uncertain channel which is subject to nonstochastic
disturbances as well and an eavesdropper obtains a disturbed version of the
channel inputs through a second uncertain channel. An encoder observes and
block-encodes the states in such a way that, upon sending the generated
codeword, the estimator’s error is bounded and such that a security criterion
is satisfied ensuring that the eavesdropper obtains as little state information
as possible. Two security criteria are considered. A sufficient condition on
the uncertain wiretap channel, i.e., the pair formed by the uncertain channel
from encoder to estimator and the uncertain channel from encoder to
eavesdropper, is derived which ensures that a bounded estimation error and
security are achieved. This condition is also shown to be necessary for a
subclass of uncertain wiretap channels. To formulate the condition, the
zero-error secrecy capacity of uncertain wiretap channels is introduced, i.e.,
the maximal rate at which data can be transmitted from the encoder to the
estimator in such a way that the eavesdropper is unable to reconstruct the
transmitted data. The zero-error secrecy capacity of uncertain wiretap channels
is studied.