Sadique Sheik, Somnath Paul, Charles Augustine, Gert Cauwenberghs
Comments: Published in IEEE BioCAS 2016 Proceedings, BioMedical Circuits and Systems Conference, 2016
Subjects: Neural and Evolutionary Computing (cs.NE)
Several learning rules for synaptic plasticity, that depend on either spike
timing or internal state variables, have been proposed in the past imparting
varying computational capabilities to Spiking Neural Networks. Due to design
complications these learning rules are typically not implemented on
neuromorphic devices leaving the devices to be only capable of inference. In
this work we propose a unidirectional post-synaptic potential dependent
learning rule that is only triggered by pre-synaptic spikes, and easy to
implement on hardware. We demonstrate that such a learning rule is functionally
capable of replicating computational capabilities of pairwise STDP. Further
more, we demonstrate that this learning rule can be used to learn and classify
spatio-temporal spike patterns in an unsupervised manner using individual
neurons. We argue that this learning rule is computationally powerful and also
ideal for hardware implementations due to its unidirectional memory access.
Weishan Dong, Ting Yuan, Kai Yang, Changsheng Li, Shilei Zhang
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Neural and Evolutionary Computing (cs.NE)
In this paper, we study learning generalized driving style representations
from automobile GPS trip data. We propose a novel Autoencoder Regularized deep
neural Network (ARNet) and a trip encoding framework trip2vec to learn drivers’
driving styles directly from GPS records, by combining supervised and
unsupervised feature learning in a unified architecture. Experiments on a
challenging driver number estimation problem and the driver identification
problem show that ARNet can learn a good generalized driving style
representation: It significantly outperforms existing methods and alternative
architectures by reaching the least estimation error on average (0.68, less
than one driver) and the highest identification accuracy (by at least 3%
improvement) compared with traditional supervised learning methods.
Tal Remez, Or Litany, Raja Giryes, Alex M. Bronstein
Subjects: Computer Vision and Pattern Recognition (cs.CV)
The increasing demand for high image quality in mobile devices brings forth
the need for better computational enhancement techniques, and image denoising
in particular. At the same time, the images captured by these devices can be
categorized into a small set of semantic classes. However simple, this
observation has not been exploited in image denoising until now. In this paper,
we demonstrate how the reconstruction quality improves when a denoiser is aware
of the type of content in the image. To this end, we first propose a new fully
convolutional deep neural network architecture which is simple yet powerful as
it achieves state-of-the-art performance even without being class-aware. We
further show that a significant boost in performance of up to (0.4) dB PSNR can
be achieved by making our network class-aware, namely, by fine-tuning it for
images belonging to a specific semantic class. Relying on the hugely successful
existing image classifiers, this research advocates for using a class-aware
approach in all image enhancement tasks.
Eshed Ohn-Bar, Mohan M. Trivedi
Comments: ICPR, December 2016. Added WIDER FACE test results (Fig. 5)
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We aim to study the modeling limitations of the commonly employed boosted
decision trees classifier. Inspired by the success of large, data-hungry visual
recognition models (e.g. deep convolutional neural networks), this paper
focuses on the relationship between modeling capacity of the weak learners,
dataset size, and dataset properties. A set of novel experiments on the Caltech
Pedestrian Detection benchmark results in the best known performance among
non-CNN techniques while operating at fast run-time speed. Furthermore, the
performance is on par with deep architectures (9.71% log-average miss rate),
while using only HOG+LUV channels as features. The conclusions from this study
are shown to generalize over different object detection domains as demonstrated
on the FDDB face detection benchmark (93.37% accuracy). Despite the impressive
performance, this study reveals the limited modeling capacity of the common
boosted trees model, motivating a need for architectural changes in order to
compete with multi-level and very deep architectures.
Tal Remez, Or Litany, Raja Giryes, Alex M. Bronstein
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Poisson distribution is used for modeling noise in photon-limited imaging.
While canonical examples include relatively exotic types of sensing like
spectral imaging or astronomy, the problem is relevant to regular photography
now more than ever due to the booming market for mobile cameras. Restricted
form factor limits the amount of absorbed light, thus computational
post-processing is called for. In this paper, we make use of the powerful
framework of deep convolutional neural networks for Poisson denoising. We
demonstrate how by training the same network with images having a specific peak
value, our denoiser outperforms previous state-of-the-art by a large margin
both visually and quantitatively. Being flexible and data-driven, our solution
resolves the heavy ad hoc engineering used in previous methods and is an order
of magnitude faster. We further show that by adding a reasonable prior on the
class of the image being processed, another significant boost in performance is
achieved.
Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, Serge Belongie
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We present an approach to effectively use millions of images with noisy
annotations in conjunction with a small subset of cleanly-annotated images to
learn powerful image representations. One common approach to combine clean and
noisy data is to first pre-train a network using the large noisy dataset and
then fine-tune with the clean dataset. We show this approach does not fully
leverage the information contained in the clean set. Thus, we demonstrate how
to use the clean annotations to reduce the noise in the large dataset before
fine-tuning the network using both the clean set and the full set with reduced
noise. The approach comprises a multi-task network that jointly learns to clean
noisy annotations and to accurately classify images. We evaluate our approach
on the recently released Open Images dataset, containing ~9 million images,
multiple annotations per image and over 6000 unique classes. For the small
clean set of annotations we use a quarter of the validation set with ~40k
images. Our results demonstrate that the proposed approach clearly outperforms
direct fine-tuning across all major categories of classes in the Open Image
dataset. Further, our approach is particularly effective for a large number of
classes with medium level of noise in annotations (20-80% false positive
annotations).
Bappaditya Mandal, David Lee, Nizar Ouarti
Comments: 16 pages, 8 figures, ACCV 2016, Second Workshop on Spontaneous Facial Behavior Analysis
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Smile is one of the key elements in identifying emotions and present state of
mind of an individual. In this work, we propose a cluster of approaches to
classify posed and spontaneous smiles using deep convolutional neural network
(CNN) face features, local phase quantization (LPQ), dense optical flow and
histogram of gradient (HOG). Eulerian Video Magnification (EVM) is used for
micro-expression smile amplification along with three normalization procedures
for distinguishing posed and spontaneous smiles. Although the deep CNN face
model is trained with large number of face images, HOG features outperforms
this model for overall face smile classification task. Using EVM to amplify
micro-expressions did not have a significant impact on classification accuracy,
while the normalizing facial features improved classification accuracy. Unlike
many manual or semi-automatic methodologies, our approach aims to automatically
classify all smiles into either `spontaneous’ or `posed’ categories, by using
support vector machines (SVM). Experimental results on large UvA-NEMO smile
database show promising results as compared to other relevant methods.
Yong Shean Chong, Yong Haur Tay
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We present an efficient method for detecting anomalies in videos. Recent
applications of convolutional neural networks have shown promises of
convolutional layers for object detection and recognition, especially in
images. However, convolutional neural networks are supervised and require
labels as learning signals. We propose a spatiotemporal architecture for
anomaly detection in videos including crowded scenes. Our architecture includes
two main components, one for spatial feature representation, and one for
learning the temporal evolution of the spatial features. Experimental results
on Avenue, Subway and UCSD benchmarks confirm that the detection accuracy of
our method is comparable to state-of-the-art methods at a considerable speed of
up to 140 fps.
Mehdi Noroozi, Paramanand Chandramouli, Paolo Favaro
Subjects: Computer Vision and Pattern Recognition (cs.CV)
The task of image deblurring is a very ill-posed problem as both the image
and the blur are unknown. Moreover, when pictures are taken in the wild, this
task becomes even more challenging due to the blur varying spatially and the
occlusions between the object. Due to the complexity of the general image model
we propose a novel convolutional network architecture which directly generates
the sharp image.This network is built in three stages, and exploits the
benefits of pyramid schemes often used in blind deconvolution. One of the main
difficulties in training such a network is to design a suitable dataset. While
useful data can be obtained by synthetically blurring a collection of images,
more realistic data must be collected in the wild. To obtain such data we use a
high frame rate video camera and keep one frame as the sharp image and frame
average as the corresponding blurred image. We show that this realistic dataset
is key in achieving state-of-the-art performance and dealing with occlusions.
Yi-Ling Chen, Tzu-Wei Huang, Kai-Han Chang, Yu-Chen Tsai, Hwann-Tzong Chen, Bing-Yu Chen
Comments: The dataset presented in this article can be found on <a href=”this https URL“>Github</a>
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Automatic photo cropping is an important tool for improving visual quality of
digital photos without resorting to tedious manual selection. Traditionally,
photo cropping is accomplished by determining the best proposal window through
visual quality assessment or saliency detection. In essence, the performance of
an image cropper highly depends on the ability to correctly rank a number of
visually similar proposal windows. Despite the ranking nature of automatic
photo cropping, little attention has been paid to learning-to-rank algorithms
in tackling such a problem. In this work, we conduct an extensive study on
traditional approaches as well as ranking-based croppers trained on various
image features. In addition, a new dataset consisting of high quality cropping
and pairwise ranking annotations is presented to evaluate the performance of
various baselines. The experimental results on the new dataset provide useful
insights into the design of better photo cropping algorithms.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, Michael Bowling
Subjects: Artificial Intelligence (cs.AI)
Artificial intelligence has seen a number of breakthroughs in recent years,
with games often serving as significant milestones. A common feature of games
with these successes is that they involve information symmetry among the
players, where all players have identical information. This property of perfect
information, though, is far more common in games than in real-world problems.
Poker is the quintessential game of imperfect information, and it has been a
longstanding challenge problem in artificial intelligence. In this paper we
introduce DeepStack, a new algorithm for imperfect information settings such as
poker. It combines recursive reasoning to handle information asymmetry,
decomposition to focus computation on the relevant decision, and a form of
intuition about arbitrary poker situations that is automatically learned from
self-play games using deep learning. In a study involving dozens of
participants and 44,000 hands of poker, DeepStack becomes the first computer
program to beat professional poker players in heads-up no-limit Texas hold’em.
Furthermore, we show this approach dramatically reduces worst-case
exploitability compared to the abstraction paradigm that has been favored for
over a decade.
Joris Guerin, Olivier Gibaru, Eric Nyiri, Stephane Thiery
Comments: 6 pages, double column, 6 figures and one table. Published in: Industrial Electronics Society , IECON 2016 – 42nd Annual Conference of the IEEE
Journal-ref: Industrial Electronics Society, IECON 2016-42nd Annual Conference
of the IEEE Pages 5316–5321
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG); Robotics (cs.RO)
To ease the development of robot learning in industry, two conditions need to
be fulfilled. Manipulators must be able to learn high accuracy and precision
tasks while being safe for workers in the factory. In this paper, we extend
previously submitted work which consists in rapid learning of local high
accuracy behaviors. By exploration and regression, linear and quadratic models
are learnt for respectively the dynamics and cost function. Iterative Linear
Quadratic Gaussian Regulator combined with cost quadratic regression can
converge rapidly in the final stages towards high accuracy behavior as the cost
function is modelled quite precisely. In this paper, both a different cost
function and a second order improvement method are implemented within this
framework. We also propose an analysis of the algorithm parameters through
simulation for a positioning task. Finally, an experimental validation on a
KUKA LBR iiwa robot is carried out. This collaborative robot manipulator can be
easily programmed into safety mode, which makes it qualified for the second
industry constraint stated above.
Mark Muraven
Comments: 17 pages
Subjects: Artificial Intelligence (cs.AI); Systems and Control (cs.SY)
There is a growing focus on how to design safe artificial intelligent (AI)
agents. As systems become more complex, poorly specified goals or control
mechanisms may cause AI agents to engage in unwanted and harmful outcomes. Thus
it is necessary to design AI agents that follow initial programming intentions
as the program grows in complexity. How to specify these initial intentions has
also been an obstacle to designing safe AI agents. Finally, there is a need for
the AI agent to have redundant safety mechanisms to ensure that any programming
errors do not cascade into major problems. Humans are autonomous intelligent
agents that have avoided these problems and the present manuscript argues that
by understanding human self-regulation and goal setting, we may be better able
to design safe AI agents. Some general principles of human self-regulation are
outlined and specific guidance for AI design is given.
Mohammad Azzeh, Ali Bou Nassif, Shadi Banitaan, Fadi Almasalha
Subjects: Software Engineering (cs.SE); Artificial Intelligence (cs.AI)
Analogy Based Effort Estimation (ABE) is one of the prominent methods for
software effort estimation. The fundamental concept of ABE is closer to the
mentality of expert estimation but with an automated procedure in which the
final estimate is generated by reusing similar historical projects. The main
key issue when using ABE is how to adapt the effort of the retrieved nearest
neighbors. The adaptation process is an essential part of ABE to generate more
successful accurate estimation based on tuning the selected raw solutions,
using some adaptation strategy. In this study we show that there are three
interrelated decision variables that have great impact on the success of
adaptation method: (1) number of nearest analogies (k), (2) optimum feature set
needed for adaptation, and (3) adaptation weights. To find the right decision
regarding these variables, one need to study all possible combinations and
evaluate them individually to select the one that can improve all prediction
evaluation measures. The existing evaluation measures usually behave
differently, presenting sometimes opposite trends in evaluating prediction
methods. This means that changing one decision variable could improve one
evaluation measure while it is decreasing the others. Therefore, the main theme
of this research is how to come up with best decision variables that improve
adaptation strategy and thus, the overall evaluation measures without degrading
the others. The impact of these decisions together has not been investigated
before, therefore we propose to view the building of adaptation procedure as a
multi-objective optimization problem. The Particle Swarm Optimization Algorithm
(PSO) is utilized to find the optimum solutions for such decision variables
based on optimizing multiple evaluation measures
Rao Farhat Masood
Subjects: Systems and Control (cs.SY); Artificial Intelligence (cs.AI)
This paper gives complete guidelines for authors submitting papers for the
AIRCC Journals. Washing machine is of great domestic necessity as it frees us
from the burden of washing our clothes and saves ample of our time. This paper
will cover the aspect of designing and developing of Fuzzy Logic based, Smart
Washing Machine. The regular washing machine (timer based) makes use of
multi-turned timer based start-stop mechanism which is mechanical as is prone
to breakage. In addition to its starting and stopping issues, the mechanical
timers are not efficient with respect of maintenance and electricity usage.
Recent developments have shown that merger of digital electronics in optimal
functionality of this machine is possible and nowadays in practice. A number of
international renowned companies have developed the machine with the
introduction of smart artificial intelligence. Such a machine makes use of
sensors and smartly calculates the amount of run-time (washing time) for the
main machine motor. Realtime calculations and processes are also catered in
optimizing the run-time of the machine. The obvious result is smart time
management, better economy of electricity and efficiency of work. This paper
deals with the indigenization of FLC (Fuzzy Logic Controller) based Washing
Machine, which is capable of automating the inputs and getting the desired
output (wash-time).
Florent Capelli
Subjects: Computational Complexity (cs.CC); Artificial Intelligence (cs.AI)
Two main techniques have been used so far to solve the #P-hard problem #SAT.
The first one, used in practice, is based on an extension of DPLL for model
counting called exhaustive DPLL. The second approach, more theoretical,
exploits the structure of the input to compute the number of satisfying
assignments by usually using a dynamic programming scheme on a decomposition of
the formula. In this paper, we make a first step toward the separation of these
two techniques by exhibiting a family of formulas that can be solved in
polynomial time with the first technique but needs an exponential time with the
second one. We show this by observing that both techniques implicitely
construct a very specific boolean circuit equivalent to the input formula. We
then show that every beta-acyclic formula can be represented by a polynomial
size circuit corresponding to the first method and exhibit a family of
beta-acyclic formulas which cannot be represented by polynomial size circuits
corresponding to the second method. This result shed a new light on the
complexity of #SAT and related problems on beta-acyclic formulas. As a
byproduct, we give new handy tools to design algorithms on beta-acyclic
hypergraphs.
Weishan Dong, Ting Yuan, Kai Yang, Changsheng Li, Shilei Zhang
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Neural and Evolutionary Computing (cs.NE)
In this paper, we study learning generalized driving style representations
from automobile GPS trip data. We propose a novel Autoencoder Regularized deep
neural Network (ARNet) and a trip encoding framework trip2vec to learn drivers’
driving styles directly from GPS records, by combining supervised and
unsupervised feature learning in a unified architecture. Experiments on a
challenging driver number estimation problem and the driver identification
problem show that ARNet can learn a good generalized driving style
representation: It significantly outperforms existing methods and alternative
architectures by reaching the least estimation error on average (0.68, less
than one driver) and the highest identification accuracy (by at least 3%
improvement) compared with traditional supervised learning methods.
Michael Sejr Schlichtkrull, Anders Søgaard
Comments: To be published at EACL 2017
Subjects: Computation and Language (cs.CL)
In cross-lingual dependency annotation projection, information is often lost
during transfer because of early decoding. We present an end-to-end graph-based
neural network dependency parser that can be trained to reproduce matrices of
edge scores, which can be directly projected across word alignments. We show
that our approach to cross-lingual dependency parsing is not only simpler, but
also achieves an absolute improvement of 2.25% averaged across 10 languages
compared to the previous state of the art.
Tsutomu Hirao, Masaaki Nishino, Jun Suzuki, Masaaki Nagata
Comments: 12 pages
Subjects: Computation and Language (cs.CL)
To analyze the limitations and the future directions of the extractive
summarization paradigm, this paper proposes an Integer Linear Programming (ILP)
formulation to obtain extractive oracle summaries in terms of ROUGE-N. We also
propose an algorithm that enumerates all of the oracle summaries for a set of
reference summaries to exploit F-measures that evaluate which system summaries
contain how many sentences that are extracted as an oracle summary. Our
experimental results obtained from Document Understanding Conference (DUC)
corpora demonstrated the following: (1) room still exists to improve the
performance of extractive summarization; (2) the F-measures derived from the
enumerated oracle summaries have significantly stronger correlations with human
judgment than those derived from single oracle summaries.
Haoyue Shi, Caihua Li, Junfeng Hu
Comments: 11 pages in CL4LC 2016
Subjects: Computation and Language (cs.CL)
Previous researches have shown that learning multiple representations for
polysemous words can improve the performance of word embeddings on many tasks.
However, this leads to another problem. Several vectors of a word may actually
point to the same meaning, namely pseudo multi-sense. In this paper, we
introduce the concept of pseudo multi-sense, and then propose an algorithm to
detect such cases. With the consideration of the detected pseudo multi-sense
cases, we try to refine the existing word embeddings to eliminate the influence
of pseudo multi-sense. Moreover, we apply our algorithm on previous released
multi-sense word embeddings and tested it on artificial word similarity tasks
and the analogy task. The result of the experiments shows that diminishing
pseudo multi-sense can improve the quality of word representations. Thus, our
method is actually an efficient way to reduce linguistic complexity.
Edison Marrese-Taylor, Yutaka Matsuo
Comments: Accepted in the EACL 2017 SRW
Subjects: Computation and Language (cs.CL)
Reproducing experiments is an important instrument to validate previous work
and build upon existing approaches. It has been tackled numerous times in
different areas of science. In this paper, we introduce an empirical
replicability study of three well-known algorithms for syntactic centric
aspect-based opinion mining. We show that reproducing results continues to be a
difficult endeavor, mainly due to the lack of details regarding preprocessing
and parameter setting, as well as due to the absence of available
implementations that clarify these details. We consider these are important
threats to validity of the research on the field, specifically when compared to
other problems in NLP where public datasets and code availability are critical
validity components. We conclude by encouraging code-based research, which we
think has a key role in helping researchers to understand the meaning of the
state-of-the-art better and to generate continuous advances.
Da Kuang, P. Jeffrey Brantingham, Andrea L. Bertozzi
Comments: 47 pages, 4 tables, 7 figures
Subjects: Computation and Language (cs.CL)
The classification of crime into discrete categories entails a massive loss
of information. Crimes emerge out of a complex mix of behaviors and situations,
yet most of these details cannot be captured by singular crime type labels.
This information loss impacts our ability to not only understand the causes of
crime, but also how to develop optimal crime prevention strategies. We apply
machine learning methods to short narrative text descriptions accompanying
crime records with the goal of discovering ecologically more meaningful latent
crime classes. We term these latent classes “crime topics” in reference to
text-based topic modeling methods that produce them. We use topic distributions
to measure clustering among formally recognized crime types. Crime topics
replicate broad distinctions between violent and property crime, but also
reveal nuances linked to target characteristics, situational conditions and the
tools and methods of attack. Formal crime types are not discrete in topic
space. Rather, crime types are distributed across a range of crime topics.
Similarly, individual crime topics are distributed across a range of formal
crime types. Key ecological groups include identity theft, shoplifting,
burglary and theft, car crimes and vandalism, criminal threats and confidence
crimes, and violent crimes. Crime topic modeling positions behavioral
situations as the focal unit of analysis for crime events. Though unlikely to
replace formal legal crime classifications, crime topics provide a unique
window into the heterogeneous causal processes underlying crime. We discuss
whether automated procedures could be used to cross-check the quality of
official crime classifications.
Ahmed H.Abase, Mohamed H. Khafagy, Fatma A. Omara
Comments: 15 Pages, 10 Figures
Journal-ref: International Journal on Cloud Computing: Services and
Architecture (IJCCSA) Vol. 6, No. 6, December 2016
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Cloud Computing (CC) is a model for enabling on-demand access to a shared
pool of configurable computing resources. Testing and evaluating the
performance of the cloud environment for allocating, provisioning, scheduling,
and data allocation policy have great attention to be achieved. Therefore,
using cloud simulator would save time and money, and provide a flexible
environment to evaluate new research work. Unfortunately, the current
simulators (e.g., CloudSim, NetworkCloudSim, GreenCloud, etc..) deal with the
data as for size only without any consideration about the data allocation
policy and locality. On the other hand, the NetworkCloudSim simulator is
considered one of the most common used simulators because it includes different
modules which support needed functions to a simulated cloud environment, and it
could be extended to include new extra modules. According to work in this
paper, the NetworkCloudSim simulator has been extended and modified to support
data locality. The modified simulator is called LocalitySim. The accuracy of
the proposed LocalitySim simulator has been proved by building a mathematical
model. Also, the proposed simulator has been used to test the performance of
the three-tire data center as a case study with considering the data locality
feature.
Ny Aina Andriambolamalala (MISA — Antananarivo), Vlady Ravelomanana (IRIF — Paris)
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
We present a randomized distributed algorithm that in radio networks with
collision detection broadcasts a single message in (O(D+log^2 n)) time slots,
with high probability. In view of the lower-bound (Omega(D+log^2 n)), our
algorithm is optimal in the considered model answering the decades-old question
of Alon, Bar-Noy, Linial and Peleg [JCSS 1991].
Bo Xu, Changlong Li, Hang Zhuang, Jiali Wang, Qingfeng Wang, Jinhong Zhou, Xuehai Zhou
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Sequence alignment algorithms are a basic and critical component of many
bioinformatics fields. With rapid development of sequencing technology, the
fast growing reference database volumes and longer length of query sequence
become new challenges for sequence alignment. However, the algorithm is
prohibitively high in terms of time and space complexity. In this paper, we
present DSA, a scalable distributed sequence alignment system that employs
Spark to process sequences data in a horizontally scalable distributed
environment, and leverages data parallel strategy based on Single Instruction
Multiple Data (SIMD) instruction to parallelize the algorithm in each core of
worker node. The experimental results demonstrate that 1) DSA has outstanding
performance and achieves up to 201x speedup over SparkSW. 2) DSA has excellent
scalability and achieves near linear speedup when increasing the number of
nodes in cluster.
Pradeeban Kathiravelu, Luís Veiga
Comments: Pre-print submitted to SDS’17
Subjects: Networking and Internet Architecture (cs.NI); Distributed, Parallel, and Cluster Computing (cs.DC)
Cyber-Physical Systems (CPS) revolutionize various application domains with
integration and interoperability of networking, computing systems, and
mechanical devices. Due to its scale and variety, CPS faces a number of
challenges and opens up a few research questions in terms of management,
fault-tolerance, and scalability. We propose a software-defined approach
inspired by Software-Defined Networking (SDN), to address the challenges for a
wider CPS adoption. We thus design a middleware architecture for the correct
and resilient operation of CPS, to manage and coordinate the interacting
devices centrally in the cyberspace whilst not sacrificing the functionality
and performance benefits inherent to a distributed execution.
K. Alex Mills, R. Chandrasekaran, Neeraj Mittal
Comments: 64 pages, 9 figures. Preprint submission to Theoretical Computer Science
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC); Discrete Mathematics (cs.DM)
In data centers, data replication is the primary method used to ensure
availability of customer data. To avoid correlated failure, cloud storage
infrastructure providers model hierarchical failure domains using a tree, and
avoid placing a large number of data replicas within the same failure domain
(i.e. on the same branch of the tree). Typical best practices ensure that
replicas are distributed across failure domains, but relatively little is known
concerning optimization algorithms for distributing data replicas. Using a
hierarchical model, we answer how to distribute replicas across failure domains
optimally. We formulate a novel optimization problem for replica placement in
data centers. As part of our problem, we formalize and explain a new criterion
for optimizing a replica placement. Our overall goal is to choose placements in
which emph{correlated} failures disable as few replicas as possible. We
provide two optimization algorithms for dependency models represented by trees.
We first present an (O(n +
ho log
ho)) time dynamic programming algorithm
for placing (
ho) replicas of a single file on the leaves (representing
servers) of a tree with (n) vertices. We next consider the problem of placing
replicas of (m) blocks of data, where each block may have different replication
factors. For this problem, we give an exact algorithm which runs in polynomial
time when the emph{skew}, the difference in the number of replicas between the
largest and smallest blocks of data, is constant.
Zeyuan Allen-Zhu, Yuanzhi Li
Subjects: Learning (cs.LG); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC); Machine Learning (stat.ML)
Matrix multiplicative weight update (MMWU) is an extremely powerful
algorithmic tool for computer science and related fields. However, it comes
with a slow running time due to the matrix exponential and eigendecomposition
computations. For this reason, many researchers studied the
followed-the-perturbed-leader (FTPL) framework which is faster, but a factor
(sqrt{d}) worse than the optimal regret of MMWU for dimension-(d) matrices.
In this paper, we propose a ( extit{followed-the-compressed-leader})
framework which, not only matches the optimal regret of MMWU (up to polylog
factors), but runs ( extit{even faster}) than FTPL.
Our main idea is to “compress” the matrix exponential computation to
dimension 3 in the adversarial setting, or dimension 1 in the stochastic
setting. This result resolves an open question regarding how to obtain both
(nearly) optimal and efficient algorithms for the online eigenvector problem.
Joris Guerin, Olivier Gibaru, Eric Nyiri, Stephane Thiery
Comments: 6 pages, double column, 6 figures and one table. Published in: Industrial Electronics Society , IECON 2016 – 42nd Annual Conference of the IEEE
Journal-ref: Industrial Electronics Society, IECON 2016-42nd Annual Conference
of the IEEE Pages 5316–5321
Subjects: Artificial Intelligence (cs.AI); Learning (cs.LG); Robotics (cs.RO)
To ease the development of robot learning in industry, two conditions need to
be fulfilled. Manipulators must be able to learn high accuracy and precision
tasks while being safe for workers in the factory. In this paper, we extend
previously submitted work which consists in rapid learning of local high
accuracy behaviors. By exploration and regression, linear and quadratic models
are learnt for respectively the dynamics and cost function. Iterative Linear
Quadratic Gaussian Regulator combined with cost quadratic regression can
converge rapidly in the final stages towards high accuracy behavior as the cost
function is modelled quite precisely. In this paper, both a different cost
function and a second order improvement method are implemented within this
framework. We also propose an analysis of the algorithm parameters through
simulation for a positioning task. Finally, an experimental validation on a
KUKA LBR iiwa robot is carried out. This collaborative robot manipulator can be
easily programmed into safety mode, which makes it qualified for the second
industry constraint stated above.
Cícero Carvalho, Victor G.L. Neumann
Comments: 9 pages
Subjects: Information Theory (cs.IT); Algebraic Geometry (math.AG)
In this paper we present several values for the next-to-minimal weights of
projective Reed-Muller codes. We work over (mathbb{F}_q) with (q geq 3) since
in IEEE-IT 62(11) p. 6300-6303 (2016) we have determined the complete values
for the next-to-minimal weights of binary projective Reed-Muller codes. As in
loc. cit. here we also find examples of codewords with next-to-minimal weight
whose set of zeros is not in a hyperplane arrangement.
Cícero Carvalho, Victor G.L. Neumann
Comments: 10 pages, Published in IEEE Transactions on Information Theory, vol. 62, issue 11, Nov. 2016
Subjects: Information Theory (cs.IT); Algebraic Geometry (math.AG)
Projective Reed-Muller codes were introduced by Lachaud, in 1988 and their
dimension and minimum distance were determined by Serre and S{o}rensen in
1991. In coding theory one is also interested in the higher Hamming weights, to
study the code performance. Yet, not many values of the higher Hamming weights
are known for these codes, not even the second lowest weight (also known as
next-to-minimal weight) is completely determined. In this paper we determine
all the values of the next-to-minimal weight for the binary projective
Reed-Muller codes, which we show to be equal to the next-to-minimal weight of
Reed-Muller codes in most, but not all, cases.
Boaz Shuval, Ido Tal
Comments: 21 pages, 5 figures
Subjects: Information Theory (cs.IT)
Polar codes are a family of capacity-achieving codes that have explicit and
low-complexity construction, encoding, and decoding algorithms. Decoding of
polar codes is based on the successive-cancellation decoder, which decodes in a
bit-wise manner. A decoding error occurs when at least one bit is erroneously
decoded. The various codeword bits are correlated, yet performance analysis of
polar codes ignores this dependence: the upper bound is based on the union
bound, and the lower bound is based on the worst-performing bit.
Improvement of the lower bound is afforded by considering error probabilities
of two bits simultaneously. These are difficult to compute explicitly due to
the large alphabet size inherent to polar codes. In this research we propose a
method to lower-bound the error probabilities of bit pairs. We develop several
transformations on pairs of synthetic channels that make the resultant
synthetic channels amenable to alphabet reduction. Our method improves upon
currently known lower bounds for polar codes under successive-cancellation
decoding.
Hyun Jong Yang, Won-Yong Shin, Bang Chul Jung, Changho Suh, Arogyaswami Paulraj
Comments: 28 pages, 6 figures, To appear in IEEE Transactions on Wireless Communications. arXiv admin note: text overlap with arXiv:1312.7198
Subjects: Information Theory (cs.IT)
In this paper, we propose an opportunistic downlink interference alignment
(ODIA) for interference-limited cellular downlink, which intelligently combines
user scheduling and downlink IA techniques. The proposed ODIA not only
efficiently reduces the effect of inter-cell interference from other-cell base
stations (BSs) but also eliminates intra-cell interference among spatial
streams in the same cell. We show that the minimum number of users required to
achieve a target degrees-of-freedom (DoF) can be fundamentally reduced, i.e.,
the fundamental user scaling law can be improved by using the ODIA, compared
with the existing downlink IA schemes. In addition, we adopt a limited feedback
strategy in the ODIA framework, and then analyze the number of feedback bits
required for the system with limited feedback to achieve the same user scaling
law of the ODIA as the system with perfect CSI. We also modify the original
ODIA in order to further improve sum-rate, which achieves the optimal multiuser
diversity gain, i.e., (loglog N), per spatial stream even in the presence of
downlink inter-cell interference, where (N) denotes the number of users in a
cell. Simulation results show that the ODIA significantly outperforms existing
interference management techniques in terms of sum-rate in realistic cellular
environments. Note that the ODIA operates in a non-collaborative and decoupled
manner, i.e., it requires no information exchange among BSs and no iterative
beamformer optimization between BSs and users, thus leading to an easier
implementation.
Xianghao Yu, Jun Zhang, Khaled B. Letaief
Comments: 5 pages, 3 figures, in Proc. Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, Nov. 2016
Subjects: Information Theory (cs.IT)
Hybrid precoding is a cost-effective approach to support directional
transmissions for millimeter wave (mmWave) communications. While existing works
on hybrid precoding mainly focus on single-user single-carrier transmission, in
practice multicarrier transmission is needed to combat the much increased
bandwidth, and multiuser MIMO can provide additional spatial multiplexing
gains. In this paper, we propose a new hybrid precoding structure for multiuser
OFDM mmWave systems, which greatly simplifies the hybrid precoder design and is
able to approach the performance of the fully digital precoder. In particular,
two groups of phase shifters are combined to map the signals from radio
frequency (RF) chains to antennas. Then an effective hybrid precoding algorithm
based on alternating minimization (AltMin) is proposed, which will alternately
optimize the digital and analog precoders. A major algorithmic innovation is a
LASSO formulation for the analog precoder, which yields computationally
efficient algorithms. Simulation results will show the performance gain of the
proposed algorithm. Moreover, it will reveal that canceling the interuser
interference is critical in multiuser OFDM hybrid precoding systems.
Zilong Liu, Yong Liang Guan, Wai Ho Mow
Subjects: Information Theory (cs.IT)
A quasi-complementary sequence set (QCSS) refers to a set of two-dimensional
matrices with low non-trivial aperiodic auto- and cross- correlation sums. For
multicarrier code-division multiple-access applications, the availability of
large QCSSs with low correlation sums is desirable. The generalized Levenshtein
bound (GLB) is a lower bound on the maximum aperiodic correlation sum of QCSSs.
The bounding expression of GLB is a fractional quadratic function of a weight
vector (mathbf{w}) and is expressed in terms of three additional parameters
associated with QCSS: the set size (K), the number of channels (M), and the
sequence length (N). It is known that a tighter GLB (compared to the Welch
bound) is possible only if the condition (Mgeq2) and (Kgeq overline{K}+1),
where (overline{K}) is a certain function of (M) and (N), is satisfied. A
challenging research problem is to determine if there exists a weight vector
which gives rise to a tighter GLB for extit{all} (not just extit{some})
(Kgeq overline{K}+1) and (Mgeq2), especially for large (N), i.e., the
condition is {asymptotically} both necessary and sufficient. To achieve this,
we extit{analytically} optimize the GLB which is (in general) non-convex as
the numerator term is an indefinite quadratic function of the weight vector.
Our key idea is to apply the frequency domain decomposition of the circulant
matrix (in the numerator term) to convert the non-convex problem into a convex
one. Following this optimization approach, we derive a new weight vector
meeting the aforementioned objective and prove that it is a local minimizer of
the GLB under certain conditions.
Wei Yi (Member, IEEE), Tao Zhou, Mingchi Xie (Member, IEEE), Yue Ai, Rick S. Blum (Fellow, IEEE)
Subjects: Information Theory (cs.IT)
In this paper, the problems of simultaneously detecting and localizing
multiple targets are considered for noncoherent multiple-input multiple-output
(MIMO) radar with widely separated antennas. By assuming a prior knowledge of
target number, an optimal solution to this problem is presented first. It is
essentially a maximum-likelihood (ML) estimator searching parameters of
interest in a high dimensional space. However, the complexity of this method
increases exponentially with the number G of targets.Besides, without the prior
information of the number of targets, a multi-hypothesis testing strategy to
determine the number of targets is required, which further complicates this
method. Therefore, we split the joint maximization into G disjoint optimization
problems by clearing the interference from previously declared targets. In this
way, we derive two fast and robust suboptimal solutions which allow trading
performance for a much lower implementation complexity which is almost
independent of the number of targets. In addition, the multi-hypothesis testing
is no longer required when target number is unknown. Simulation results show
the proposed algorithms can correctly detect and accurately localize multiple
targets even when targets share common range bins in some paths.
Lan V. Truong, Vincent Y. F. Tan
Comments: 20 pages
Subjects: Information Theory (cs.IT)
We derive upper and lower bounds on the reliability function for the
common-message discrete memoryless broadcast channel with variable-length
feedback. We show that the bounds are tight when the broadcast channel is
stochastically degraded. For the achievability part, we adapt Yamamoto and
Itoh’s coding scheme by controlling the expectation of the maximum of a set of
stopping times. For the converse part, we adapt Burnashev’s proof techniques
for establishing the reliability functions for (point-to-point) discrete
memoryless channels with variable-length feedback and sequential hypothesis
testing.
Amina Piemontese, Alexandre Graell i Amat
Comments: submitted to IEEE Transactions on Communications. arXiv admin note: text overlap with arXiv:1607.00880
Subjects: Information Theory (cs.IT)
We investigate the use of maximum distance separable (MDS) codes to cache
popular content to reduce the download delay of wireless content delivery. In
particular, we consider a cellular system where devices roam in an out of a
cell according to a Poisson random process. Popular content is cached in a
limited number of the mobile devices using an MDS code and can be downloaded
from the mobile devices using device-to-device communication. We derive an
analytical expression for the delay incurred in downloading content from the
wireless network and show that distributed caching using MDS codes can
dramatically reduce the download delay with respect to the scenario where
content is always downloaded from the base station and to the case of uncoded
distributed caching.
Ting-Yi Wu, Lav R. Varshney, Vincent Y. F. Tan
Comments: 5 pages, 1 table, 4 figures, submitted to International Symposium on Information Theory 2017
Subjects: Information Theory (cs.IT)
This work investigates the limits of communication over a noisy channel that
wears out, in the sense of signal-dependent catastrophic failure. In
particular, we consider a channel that starts as a memoryless binary-input
channel and when the number of transmitted ones causes a sufficient amount of
damage, the channel ceases to convey signals. We restrict attention to constant
composition codes. Since infinite blocklength codes will always wear out the
channel for any finite threshold of failure and therefore convey no
information, we make use of finite blocklength codes to determine the maximum
expected transmission volume at a given level of average error probability. We
show that this maximization problem has a recursive form and can be solved by
dynamic programming. A discussion of damage state feedback in channels that
wear out is also provided. Numerical results show that a sequence of block
codes is preferred to a single block code for streaming sources.
Anindya De, Elchanan Mossel, Joe Neeman
Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT); Probability (math.PR)
A basic problem in information theory is the following: Let (mathbf{P} =
(mathbf{X}, mathbf{Y})) be an arbitrary distribution where the marginals
(mathbf{X}) and (mathbf{Y}) are (potentially) correlated. Let Alice and Bob
be two players where Alice gets samples ({x_i}_{i ge 1}) and Bob gets
samples ({y_i}_{i ge 1}) and for all (i), ((x_i, y_i) sim mathbf{P}). What
joint distributions (mathbf{Q}) can be simulated by Alice and Bob without any
interaction?
Classical works in information theory by G{‘a}cs-K{“o}rner and Wyner answer
this question when at least one of (mathbf{P}) or (mathbf{Q}) is the
distribution on ({0,1} imes {0,1}) where each marginal is unbiased and
identical. However, outside of this degenerate setting, the answer to this
question is understood in very few cases. Recently, Ghazi, Kamath and Sudan
showed that this problem is decidable for (mathbf{Q}) supported on ({0,1}
imes {0,1}). We extend their result to (mathbf{Q}) supported on any finite
alphabet.
We rely on recent results in Gaussian geometry (by the authors) as well as a
new emph{smoothing argument} inspired by the method of emph{boosting} from
learning theory and potential function arguments from complexity theory and
additive combinatorics.