Krzysztof J. Cios
Comments: 14 pages, 14 figures
Subjects: Neural and Evolutionary Computing (cs.NE); Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG)
Introduction to deep neural networks and their history.
Casey Kneale, Dominic Poerio, Karl S. Booksh
Comments: To be submitted to the Journal of Technometrics
Subjects: Methodology (stat.ME); Neural and Evolutionary Computing (cs.NE)
Optimized spatial partitioning algorithms are the corner stone of many
successful experimental designs and statistical methods. Of these algorithms,
the Centroidal Voronoi Tessellation (CVT) is the most widely utilized. CVT
based methods require global knowledge of spatial boundaries, do not readily
allow for weighted regions, have challenging implementations, and are
inefficiently extended to high dimensional spaces. We describe two simple
partitioning schemes based on nearest and next nearest neighbor locations which
easily incorporate these features at the slight expense of optimal placement.
Several novel qualitative techniques which assess these partitioning schemes
are also included. The feasibility of autonomous uninformed sensor networks
utilizing these algorithms are considered. Some improvements in particle swarm
optimizer results on multimodal test functions from partitioned initial
positions in two space are also illustrated. Pseudo code for all of the novel
algorithms depicted here-in is available in the supplementary information of
this manuscript.
I. Theodorakopoulos, V. Pothos, D. Kastaniotis, N. Fragoulis
Comments: 17 pages, 10 figures, 5 tables
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
A new, radical CNN design approach is presented in this paper, considering
the reduction of the total computational load during inference. This is
achieved by a new holistic intervention on both the CNN architecture and the
training procedure, which targets to the parsimonious inference by learning to
exploit or remove the redundant capacity of a CNN architecture. This is
accomplished, by the introduction of a new structural element that can be
inserted as an add-on to any contemporary CNN architecture, whilst preserving
or even improving its recognition accuracy. Our approach formulates a
systematic and data-driven method for developing CNNs that are trained to
eventually change size and form in real-time during inference, targeting to the
smaller possible computational footprint. Results are provided for the optimal
implementation on a few modern, high-end mobile computing platforms indicating
a significant speed-up of up to x3 times.
Xingchao Peng, Kate Saenko
Comments: 13 pages, 8 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Synthetic images rendered from 3D CAD models have been used in the past to
augment training data for object recognition algorithms. However, the generated
images are non-photorealistic and do not match real image statistics. This
leads to a large domain discrepancy, causing models trained on synthetic data
to perform poorly on real domains. Recent work has shown the great potential of
deep convolutional neural networks to generate realistic images, but has not
addressed synthetic-to-real domain adaptation. Inspired by these ideas, we
propose the Deep Generative Correlation Alignment Network (DGCAN) to synthesize
training images using a novel domain adaption algorithm. DGCAN leverages the L2
and the correlation alignment (CORAL) losses to minimize the domain discrepancy
between generated and real images in deep feature space. The rendered results
demonstrate that DGCAN can synthesize the object shape from 3D CAD models
together with structured texture from a small amount of real background images.
Experimentally, we show that training classifiers on the generated data can
significantly boost performance when testing on the real image domain,
improving upon several existing methods.
Tomas Hodan, Pavel Haluza, Stepan Obdrzalek, Jiri Matas, Manolis Lourakis, Xenophon Zabulis
Comments: WACV 2017
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Robotics (cs.RO)
We introduce T-LESS, a new public dataset for estimating the 6D pose, i.e.
translation and rotation, of texture-less rigid objects. The dataset features
thirty industry-relevant objects with no significant texture and no
discriminative color or reflectance properties. The objects exhibit symmetries
and mutual similarities in shape and/or size. Compared to other datasets, a
unique property is that some of the objects are parts of others. The dataset
includes training and test images that were captured with three synchronized
sensors, specifically a structured-light and a time-of-flight RGB-D sensor and
a high-resolution RGB camera. There are approximately 39K training and 10K test
images from each sensor. Additionally, two types of 3D models are provided for
each object, i.e. a manually created CAD model and a semi-automatically
reconstructed one. Training images depict individual objects against a black
background. Test images originate from twenty test scenes having varying
complexity, which increases from simple scenes with several isolated objects to
very challenging ones with multiple instances of several objects and with a
high amount of clutter and occlusion. The images were captured from a
systematically sampled view sphere around the object/scene, and are annotated
with accurate ground truth 6D poses of all modeled objects. Initial evaluation
results indicate that the state of the art in 6D object pose estimation has
ample room for improvement, especially in difficult cases with significant
occlusion. The T-LESS dataset is available online at cmp.felk.cvut.cz/t-less.
Anoop Cherian, Piotr Koniusz, Stephen Gould
Comments: 9 pages
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Most successful deep learning algorithms for action recognition extend models
designed for image-based tasks such as object recognition to video. Such
extensions are typically trained for actions on single video frames or very
short clips, and then their predictions from sliding-windows over the video
sequence are pooled for recognizing the action at the sequence level. Usually
this pooling step uses the first-order statistics of frame-level action
predictions. In this paper, we explore the advantages of using higher-order
correlations; specifically, we introduce Higher-order Kernel (HOK) descriptors
generated from the late fusion of CNN classifier scores from all the frames in
a sequence. To generate these descriptors, we use the idea of kernel
linearization. Specifically, a similarity kernel matrix, which captures the
temporal evolution of deep classifier scores, is first linearized into kernel
feature maps. The HOK descriptors are then generated from the higher-order
co-occurrences of these feature maps, and are then used as input to a
video-level classifier. We provide experiments on two fine-grained action
recognition datasets and show that our scheme leads to state-of-the-art
results.
Mario Corsolini, Andrea Carta
Comments: 20 pages, 14 figures. Accepted for publication in the “Journal of Baduk Studies”, datasets available from this http URL
Subjects: Computer Vision and Pattern Recognition (cs.CV)
In a previous paper [ arXiv:1508.03269 ] we described the techniques we
successfully employed for automatically reconstructing the whole move sequence
of a Go game by means of a set of pictures. Now we describe how it is possible
to reconstruct the move sequence by means of a video stream (which may be
provided by an unattended webcam), possibly in real-time. Although the basic
algorithms remain the same, we will discuss the new problems that arise when
dealing with videos, with special care for the ones that could block a
real-time analysis and require an improvement of our previous techniques or
even a completely brand new approach. Eventually we present a number of
preliminary but positive experimental results supporting the effectiveness of
the software we are developing, built on the ideas here outlined.
Xin Yuan, Gang Huang, Hong Jiang, Paul Wilford
Comments: 5 pages, 10 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)
The existing lensless compressive camera
(( ext{L}^2 ext{C}^2))~cite{Huang13ICIP} suffers from low capture rates,
resulting in low resolution images when acquired over a short time. In this
work, we propose a new regime to mitigate these drawbacks. We replace the
global-based compressive sensing used in the existing ( ext{L}^2 ext{C}^2) by
the local block (patch) based compressive sensing. We use a single sensor for
each block, rather than for the entire image, thus forming a multiple but
spatially parallel sensor ( ext{L}^2 ext{C}^2). This new camera retains the
advantages of existing ( ext{L}^2 ext{C}^2) while leading to the following
additional benefits: 1) Since each block can be very small, {em e.g.}(~8 imes
8) pixels, we only need to capture (sim 10) measurements to achieve reasonable
reconstruction. Therefore the capture time can be reduced significantly. 2) The
coding patterns used in each block can be the same, therefore the sensing
matrix is only of the block size compared to the entire image size in existing
( ext{L}^2 ext{C}^2). This saves the memory requirement of the sensing matrix
as well as speeds up the reconstruction. 3) Patch based image reconstruction is
fast and since real time stitching algorithms exist, we can perform real time
reconstruction. 4) These small blocks can be integrated to any desirable
number, leading to ultra high resolution images while retaining fast capture
rate and fast reconstruction. We develop multiple geometries of this block-wise
( ext{L}^2 ext{C}^2) in this paper. We have built prototypes of the proposed
block-wise ( ext{L}^2 ext{C}^2) and demonstrated excellent results of real
data.
Suyog Dutt Jain, Bo Xiong, Kristen Grauman
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We propose an end-to-end learning framework for segmenting generic objects in
videos. Our method learns to combine appearance and motion information to
produce pixel level segmentation masks for all prominent objects in videos. We
formulate this task as a structured prediction problem and design a two-stream
fully convolutional neural network which fuses together motion and appearance
in a unified framework. Since large-scale video datasets with pixel level
segmentations are problematic, we show how to bootstrap weakly annotated videos
together with existing image recognition datasets for training. Through
experiments on three challenging video segmentation benchmarks, our method
substantially improves the state-of-the-art for segmenting generic (unseen)
objects.
Florian Fink, Klaus-U. Schulz, Uwe Springmann
Subjects: Computer Vision and Pattern Recognition (cs.CV); Digital Libraries (cs.DL)
In the absence of ground truth it is not possible to automatically determine
the exact spectrum and occurrences of OCR errors in an OCR’ed text. Yet, for
interactive postcorrection of OCR’ed historical printings it is extremely
useful to have a statistical profile available that provides an estimate of
error classes with associated frequencies, and that points to conjectured
errors and suspicious tokens. The method introduced in Reffle (2013) computes
such a profile, combining lexica, pattern sets and advanced matching techniques
in a specialized Expectation Maximization (EM) procedure. Here we improve this
method in three respects: First, the method in Reffle (2013) is not adaptive:
user feedback obtained by actual postcorrection steps cannot be used to compute
refined profiles. We introduce a variant of the method that is open for
adaptivity, taking correction steps of the user into account. This leads to
higher precision with respect to recognition of erroneous OCR tokens. Second,
during postcorrection often new historical patterns are found. We show that
adding new historical patterns to the linguistic background resources leads to
a second kind of improvement, enabling even higher precision by telling
historical spellings apart from OCR errors. Third, the method in Reffle (2013)
does not make any active use of tokens that cannot be interpreted in the
underlying channel model. We show that adding these uninterpretable tokens to
the set of conjectured errors leads to a significant improvement of the recall
for error detection, at the same time improving precision.
James Booth, Epameinondas Antonakos, Stylianos Ploumpis, George Trigeorgis, Yannis Panagakis, Stefanos Zafeiriou
Subjects: Computer Vision and Pattern Recognition (cs.CV)
3D Morphable Models (3DMMs) are powerful statistical models of 3D facial
shape and texture, and among the state-of-the-art methods for reconstructing
facial shape from single images. With the advent of new 3D sensors, many 3D
facial datasets have been collected containing both neutral as well as
expressive faces. However, all datasets are captured under controlled
conditions. Thus, even though powerful 3D facial shape models can be learnt
from such data, it is difficult to build statistical texture models that are
sufficient to reconstruct faces captured in unconstrained conditions
(“in-the-wild”). In this paper, we propose the first, to the best of our
knowledge, “in-the-wild” 3DMM by combining a powerful statistical model of
facial shape, which describes both identity and expression, with an
“in-the-wild” texture model. We show that the employment of such an
“in-the-wild” texture model greatly simplifies the fitting procedure, because
there is no need to optimize with regards to the illumination parameters.
Furthermore, we propose a new fast algorithm for fitting the 3DMM in arbitrary
images. Finally, we have captured the first 3D facial database with relatively
unconstrained conditions and report quantitative evaluations with
state-of-the-art performance. Complementary qualitative reconstruction results
are demonstrated on standard “in-the-wild” facial databases. An open source
implementation of our technique is released as part of the Menpo Project.
Suyog Dutt Jain, Bo Xiong, Kristen Grauman
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We propose an end-to-end learning framework for generating foreground object
segmentations. Given a single novel image, our approach produces pixel-level
masks for all “object-like” regions—even for object categories never seen
during training. We formulate the task as a structured prediction problem of
assigning foreground/background labels to all pixels, implemented using a deep
fully convolutional network. Key to our idea is training with a mix of
image-level object category examples together with relatively few images with
boundary-level annotations. Our method substantially improves the
state-of-the-art for foreground segmentation accuracy on the ImageNet and MIT
Object Discovery datasets—with 19% improvements in some cases. Furthermore,
with extensive evaluation on over 1 million images, we show it generalizes well
to segment even object categories unseen in the foreground maps used for
training. Finally, we demonstrate how our approach benefits image retrieval and
image retargeting, both of which flourish when given our high-quality
foreground maps.
Martin Rais, Gabriele Facciolo, Enric Meinhardt-Llopis, Jean-Michel Morel, Antoni Buades, Bartomeu Coll
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We reconsider the classic problem of estimating accurately a 2D
transformation from point matches between images containing outliers. RANSAC
discriminates outliers by randomly generating minimalistic sampled hypotheses
and verifying their consensus over the input data. Its response is based on the
single hypothesis that obtained the largest inlier support. In this article we
show that the resulting accuracy can be improved by aggregating all generated
hypotheses. This yields RANSAAC, a framework that improves systematically over
RANSAC and its state-of-the-art variants by statistically aggregating
hypotheses. To this end, we introduce a simple strategy that allows to rapidly
average 2D transformations, leading to an almost negligible extra computational
cost. We give practical applications on projective transforms and
homography+distortion models and demonstrate a significant performance gain in
both cases.
I. Theodorakopoulos, V. Pothos, D. Kastaniotis, N. Fragoulis
Comments: 17 pages, 10 figures, 5 tables
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
A new, radical CNN design approach is presented in this paper, considering
the reduction of the total computational load during inference. This is
achieved by a new holistic intervention on both the CNN architecture and the
training procedure, which targets to the parsimonious inference by learning to
exploit or remove the redundant capacity of a CNN architecture. This is
accomplished, by the introduction of a new structural element that can be
inserted as an add-on to any contemporary CNN architecture, whilst preserving
or even improving its recognition accuracy. Our approach formulates a
systematic and data-driven method for developing CNNs that are trained to
eventually change size and form in real-time during inference, targeting to the
smaller possible computational footprint. Results are provided for the optimal
implementation on a few modern, high-end mobile computing platforms indicating
a significant speed-up of up to x3 times.
Krzysztof J. Cios
Comments: 14 pages, 14 figures
Subjects: Neural and Evolutionary Computing (cs.NE); Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG)
Introduction to deep neural networks and their history.
Farman Ali, D. Kwak, Pervez Khan, S.M. Riazul Islam, K.H. Kim, K.S. Kwak
Comments: 24 pages, 7 figures, Transportation Research Part C
Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
Traffic congestion is rapidly increasing in urban areas, particularly in mega
cities. To date, there exist a few sensor network based systems to address this
problem. However, these techniques are not suitable enough in terms of
monitoring an entire transportation system and delivering emergency services
when needed. These techniques require real-time data and intelligent ways to
quickly determine traffic activity from useful information. In addition, these
existing systems and websites on city transportation and travel rely on rating
scores for different factors (e.g., safety, low crime rate, cleanliness, etc.).
These rating scores are not efficient enough to deliver precise information,
whereas reviews or tweets are significant, because they help travelers and
transportation administrators to know about each aspect of the city. However,
it is difficult for travelers to read, and for transportation systems to
process, all reviews and tweets to obtain expressive sentiments regarding the
needs of the city. The optimum solution for this kind of problem is analyzing
the information available on social network platforms and performing sentiment
analysis. On the other hand, crisp ontology-based frameworks cannot extract
blurred information from tweets and reviews; therefore, they produce inadequate
results. In this regard, this paper proposes fuzzy ontology-based sentiment
analysis and SWRL rule-based decision-making to monitor transportation
activities and to make a city- feature polarity map for travelers. This system
retrieves reviews and tweets related to city features and transportation
activities. The feature opinions are extracted from these retrieved data, and
then fuzzy ontology is used to determine the transportation and city-feature
polarity. A fuzzy ontology and an intelligent system prototype are developed by
using Prot’eg’e OWL and Java, respectively.
Zhipeng Huang, Nikos Mamoulis
Subjects: Artificial Intelligence (cs.AI)
A network embedding is a representation of a large graph in a low-dimensional
space, where vertices are modeled as vectors. The objective of a good embedding
is to preserve the proximity between vertices in the original graph. This way,
typical search and mining methods can be applied in the embedded space with the
help of off-the-shelf multidimensional indexing approaches. Existing network
embedding techniques focus on homogeneous networks, where all vertices are
considered to belong to a single class.
Tarek R. Besold, Artur d'Avila Garcez, Keith Stenning, Leendert van der Torre, Michiel van Lambalgen
Comments: Submitted to the Special Issue “Reasoning with Imperfect Information and Knowledge” of Minds and Machines (2017)
Subjects: Artificial Intelligence (cs.AI)
This article aims to achieve two goals: to show that probability is not the
only way of dealing with uncertainty (and even more, that there are kinds of
uncertainty which are for principled reasons not addressable with probabilistic
means); and to provide evidence that logic-based methods can well support
reasoning with uncertainty. For the latter claim, two paradigmatic examples are
presented: Logic Programming with Kleene semantics for modelling reasoning from
information in a discourse, to an interpretation of the state of affairs of the
intended model, and a neural-symbolic implementation of Input/Output logic for
dealing with uncertainty in dynamic normative contexts.
Tomas Hodan, Pavel Haluza, Stepan Obdrzalek, Jiri Matas, Manolis Lourakis, Xenophon Zabulis
Comments: WACV 2017
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Robotics (cs.RO)
We introduce T-LESS, a new public dataset for estimating the 6D pose, i.e.
translation and rotation, of texture-less rigid objects. The dataset features
thirty industry-relevant objects with no significant texture and no
discriminative color or reflectance properties. The objects exhibit symmetries
and mutual similarities in shape and/or size. Compared to other datasets, a
unique property is that some of the objects are parts of others. The dataset
includes training and test images that were captured with three synchronized
sensors, specifically a structured-light and a time-of-flight RGB-D sensor and
a high-resolution RGB camera. There are approximately 39K training and 10K test
images from each sensor. Additionally, two types of 3D models are provided for
each object, i.e. a manually created CAD model and a semi-automatically
reconstructed one. Training images depict individual objects against a black
background. Test images originate from twenty test scenes having varying
complexity, which increases from simple scenes with several isolated objects to
very challenging ones with multiple instances of several objects and with a
high amount of clutter and occlusion. The images were captured from a
systematically sampled view sphere around the object/scene, and are annotated
with accurate ground truth 6D poses of all modeled objects. Initial evaluation
results indicate that the state of the art in 6D object pose estimation has
ample room for improvement, especially in difficult cases with significant
occlusion. The T-LESS dataset is available online at cmp.felk.cvut.cz/t-less.
Valentina Franzoni, Yuanxi Li, Clement H.C.Leung, Alfredo Milani
Comments: author’s copy of publication in NLCS ICCSA 2013 proceedings: Collective Evolutionary Concept Distance Based Query Expansion for Effective Web Document Retrieval
Journal-ref: Chapter Computational Science and Its Applications, ICCSA 2013,
Volume 7974 of the series Lecture Notes in Computer Science, pp 657-672
Subjects: Information Retrieval (cs.IR); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Probability (math.PR)
In this work several semantic approaches to concept-based query expansion and
reranking schemes are studied and compared with different ontology-based
expansion methods in web document search and retrieval. In particular, we focus
on concept-based query expansion schemes, where, in order to effectively
increase the precision of web document retrieval and to decrease the users
browsing time, the main goal is to quickly provide users with the most suitable
query expansion. Two key tasks for query expansion in web document retrieval
are to find the expansion candidates, as the closest concepts in web document
domain, and to rank the expanded queries properly. The approach we propose aims
at improving the expansion phase for better web document retrieval and
precision. The basic idea is to measure the distance between candidate concepts
using the PMING distance, a collaborative semantic proximity measure, i.e. a
measure which can be computed by using statistical results from web search
engine. Experiments show that the proposed technique can provide users with
more satisfying expansion results and improve the quality of web document
retrieval.
I. Theodorakopoulos, V. Pothos, D. Kastaniotis, N. Fragoulis
Comments: 17 pages, 10 figures, 5 tables
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
A new, radical CNN design approach is presented in this paper, considering
the reduction of the total computational load during inference. This is
achieved by a new holistic intervention on both the CNN architecture and the
training procedure, which targets to the parsimonious inference by learning to
exploit or remove the redundant capacity of a CNN architecture. This is
accomplished, by the introduction of a new structural element that can be
inserted as an add-on to any contemporary CNN architecture, whilst preserving
or even improving its recognition accuracy. Our approach formulates a
systematic and data-driven method for developing CNNs that are trained to
eventually change size and form in real-time during inference, targeting to the
smaller possible computational footprint. Results are provided for the optimal
implementation on a few modern, high-end mobile computing platforms indicating
a significant speed-up of up to x3 times.
Valentina Franzoni, Yuanxi Li, Clement H.C.Leung, Alfredo Milani
Comments: author’s copy of publication in NLCS ICCSA 2013 proceedings: Collective Evolutionary Concept Distance Based Query Expansion for Effective Web Document Retrieval
Journal-ref: Chapter Computational Science and Its Applications, ICCSA 2013,
Volume 7974 of the series Lecture Notes in Computer Science, pp 657-672
Subjects: Information Retrieval (cs.IR); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Probability (math.PR)
In this work several semantic approaches to concept-based query expansion and
reranking schemes are studied and compared with different ontology-based
expansion methods in web document search and retrieval. In particular, we focus
on concept-based query expansion schemes, where, in order to effectively
increase the precision of web document retrieval and to decrease the users
browsing time, the main goal is to quickly provide users with the most suitable
query expansion. Two key tasks for query expansion in web document retrieval
are to find the expansion candidates, as the closest concepts in web document
domain, and to rank the expanded queries properly. The approach we propose aims
at improving the expansion phase for better web document retrieval and
precision. The basic idea is to measure the distance between candidate concepts
using the PMING distance, a collaborative semantic proximity measure, i.e. a
measure which can be computed by using statistical results from web search
engine. Experiments show that the proposed technique can provide users with
more satisfying expansion results and improve the quality of web document
retrieval.
Konstantina Christakopoulou, Jaya Kawale, Arindam Banerjee
Subjects: Machine Learning (stat.ML); Information Retrieval (cs.IR); Learning (cs.LG)
In this paper, we investigate the common scenario where every candidate item
for recommendation is characterized by a maximum capacity, i.e., number of
seats in a Point-of-Interest or size of an item’s inventory. Despite the
prevalence of the task of recommending items under capacity constraints in a
variety of settings, to the best of our knowledge, none of the known
recommender methods is designed to respect capacity constraints. To close this
gap, we extend two state-of-the art latent factor recommendation approaches:
probabilistic matrix factorization (PMF) and geographical matrix factorization
(GeoMF), to optimize for both prediction accuracy and expected item usage that
respects the capacity constraints. We introduce the useful concepts of user
propensity to listen and item capacity. Our experimental results in public
datasets, both for the domain of item recommendation and Point-of-Interest
recommendation, highlight the benefit of our method for the setting of
recommendation under capacity constraints.
Zhongyu Wei, Chen Li, Yang Liu
Comments: 12 pages
Subjects: Computation and Language (cs.CL)
For argumentation mining, there are several sub-tasks such as argumentation
component type classification, relation classification. Existing research tends
to solve such sub-tasks separately, but ignore the close relation between them.
In this paper, we present a joint framework incorporating logical relation
between sub-tasks to improve the performance of argumentation structure
generation. We design an objective function to combine the predictions from
individual models for each sub-task and solve the problem with some constraints
constructed from background knowledge. We evaluate our proposed model on two
public corpora and the experiment results show that our model can outperform
the baseline that uses a separate model significantly for each sub-task. Our
model also shows advantages on component-related sub-tasks compared to a
state-of-the-art joint model based on the evidence graph.
Farman Ali, D. Kwak, Pervez Khan, S.M. Riazul Islam, K.H. Kim, K.S. Kwak
Comments: 24 pages, 7 figures, Transportation Research Part C
Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL)
Traffic congestion is rapidly increasing in urban areas, particularly in mega
cities. To date, there exist a few sensor network based systems to address this
problem. However, these techniques are not suitable enough in terms of
monitoring an entire transportation system and delivering emergency services
when needed. These techniques require real-time data and intelligent ways to
quickly determine traffic activity from useful information. In addition, these
existing systems and websites on city transportation and travel rely on rating
scores for different factors (e.g., safety, low crime rate, cleanliness, etc.).
These rating scores are not efficient enough to deliver precise information,
whereas reviews or tweets are significant, because they help travelers and
transportation administrators to know about each aspect of the city. However,
it is difficult for travelers to read, and for transportation systems to
process, all reviews and tweets to obtain expressive sentiments regarding the
needs of the city. The optimum solution for this kind of problem is analyzing
the information available on social network platforms and performing sentiment
analysis. On the other hand, crisp ontology-based frameworks cannot extract
blurred information from tweets and reviews; therefore, they produce inadequate
results. In this regard, this paper proposes fuzzy ontology-based sentiment
analysis and SWRL rule-based decision-making to monitor transportation
activities and to make a city- feature polarity map for travelers. This system
retrieves reviews and tweets related to city features and transportation
activities. The feature opinions are extracted from these retrieved data, and
then fuzzy ontology is used to determine the transportation and city-feature
polarity. A fuzzy ontology and an intelligent system prototype are developed by
using Prot’eg’e OWL and Java, respectively.
Valentina Franzoni, Yuanxi Li, Clement H.C.Leung, Alfredo Milani
Comments: author’s copy of publication in NLCS ICCSA 2013 proceedings: Collective Evolutionary Concept Distance Based Query Expansion for Effective Web Document Retrieval
Journal-ref: Chapter Computational Science and Its Applications, ICCSA 2013,
Volume 7974 of the series Lecture Notes in Computer Science, pp 657-672
Subjects: Information Retrieval (cs.IR); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Probability (math.PR)
In this work several semantic approaches to concept-based query expansion and
reranking schemes are studied and compared with different ontology-based
expansion methods in web document search and retrieval. In particular, we focus
on concept-based query expansion schemes, where, in order to effectively
increase the precision of web document retrieval and to decrease the users
browsing time, the main goal is to quickly provide users with the most suitable
query expansion. Two key tasks for query expansion in web document retrieval
are to find the expansion candidates, as the closest concepts in web document
domain, and to rank the expanded queries properly. The approach we propose aims
at improving the expansion phase for better web document retrieval and
precision. The basic idea is to measure the distance between candidate concepts
using the PMING distance, a collaborative semantic proximity measure, i.e. a
measure which can be computed by using statistical results from web search
engine. Experiments show that the proposed technique can provide users with
more satisfying expansion results and improve the quality of web document
retrieval.
Anton Weber, Kim-Anh Tran, Stefanos Kaxiras, Alexandra Jimborean
Comments: Presented at HIP3ES, 2017
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Energy-efficiency plays a significant role given the battery lifetime
constraints in embedded systems and hand-held devices. In this work we target
the ARM big.LITTLE, a heterogeneous platform that is dominant in the mobile and
embedded market, which allows code to run transparently on different
microarchitectures with individual energy and performance characteristics. It
allows to se more energy efficient cores to conserve power during simple tasks
and idle times and switch over to faster, more power hungry cores when
performance is needed. This proposal explores the power-savings and the
performance gains that can be achieved by utilizing the ARM big.LITTLE core in
combination with Decoupled Access-Execute (DAE). DAE is a compiler technique
that splits code regions into two distinct phases: a memory-bound Access phase
and a compute-bound Execute phase. By scheduling the memory-bound phase on the
LITTLE core, and the compute-bound phase on the big core, we conserve energy
while caching data from main memory and perform computations at maximum
performance. Our preliminary findings show that applying DAE on ARM big.LITTLE
has potential. By prefetching data in Access we can achieve an IPC improvement
of up to 37% in the Execute phase, and manage to shift more than half of the
program runtime to the LITTLE core. We also provide insight into advantages and
disadvantages of our approach, present preliminary results and discuss
potential solutions to overcome locking overhead.
Blesson Varghese, Nan Wang, Dimitrios S. Nikolopoulos, Rajkumar Buyya
Comments: 8 pages
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
As billions of devices get connected to the Internet, it will not be
sustainable to use the cloud as a centralised server. The way forward is to
decentralise computations away from the cloud towards the edge of the network
closer to the user. This reduces the latency of communication between a user
device and the cloud, and is the premise of ‘fog computing’ defined in this
paper. The aim of this paper is to highlight the feasibility and the benefits
in improving the Quality-of-Service and Experience by using fog computing. For
an online game use-case, we found that the average response time for a user is
improved by 20% when using the edge of the network in comparison to using a
cloud-only model. It was also observed that the volume of traffic between the
edge and the cloud server is reduced by over 90% for the use-case. The
preliminary results highlight the potential of fog computing in achieving a
sustainable computing model and highlights the benefits of integrating the edge
of the network into the computing ecosystem.
Mohamed Essadki (IFPEN, FR3487, EM2C), Jonathan Jung (LMAP), Adam Larat (FR3487, EM2C), Milan Pelletier (EM2C), Vincent Perrier (LMAP)
Journal-ref: ESAIM: Proceedings and Surveys, EDP Sciences, pp.1 – 10 (2017)
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Numerical Analysis (cs.NA); Numerical Analysis (math.NA)
This article describes the implementation of an all-in-one numerical
procedure within the runtime StarPU. In order to limit the complexity of the
method, for the sake of clarity of the presentation of the non-classical
task-driven programming environnement, we have limited the numerics to first
order in space and time. Results show that the task distribution is efficient
if the tasks are numerous and individually large enough so that the task heap
can be saturated by tasks which computational time covers the task management
overhead. Next, we also see that even though they are mostly faster on graphic
cards, not all the tasks are suitable for GPUs, which brings forward the
importance of the task scheduler. Finally, we look at a more realistic system
of conservation laws with an expensive source term, what allows us to conclude
and open on future works involving higher local arithmetic intensity, by
increasing the order of the numerical method or by enriching the model
(increased number of parameters and therefore equations).
Do Le Quoc, Martin Beck, Pramod Bhatotia, Ruichuan Chen, Christof Fetzer, Thorsten Strufe
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Cryptography and Security (cs.CR)
How to preserve users’ privacy while supporting high-utility analytics for
low-latency stream processing? To answer this question: we describe the design,
implementation and evaluation of PRIVAPPROX, a data analytics system for
privacy-preserving stream processing. PRIVAPPROX provides three properties: (i)
Privacy: zero-knowledge privacy guarantees for users, a privacy bound tighter
than the state-of-the-art differential privacy; (ii) Utility: an interface for
data analysts to systematically explore the trade-offs between the output
accuracy (with error-estimation) and query execution budget; (iii) Latency:
near real-time stream processing based on a scalable “synchronization-free”
distributed architecture. The key idea behind our approach is to marry two
existing techniques together: namely, sampling (used in the context of
approximate computing) and randomized response (used in the context of
privacy-preserving analytics). The resulting marriage is complementary – It
achieves stronger privacy guarantees and also improved performance, a necessary
ingredient
Artem Khyzha, Mike Dodds, Alexey Gotsman, Matthew Parkinson
Subjects: Programming Languages (cs.PL); Distributed, Parallel, and Cluster Computing (cs.DC); Logic in Computer Science (cs.LO)
Linearizability is the commonly accepted notion of correctness for concurrent
data structures. It requires that any execution of the data structure is
justified by a linearization — a linear order on operations satisfying the
data structure’s sequential specification. Proving linearizability is often
challenging because an operation’s position in the linearization order may
depend on future operations. This makes it very difficult to incrementally
construct the linearization in a proof.
We propose a new proof method that can handle data structures with such
future-dependent linearizations. Our key idea is to incrementally construct not
a single linear order of operations, but a partial order that describes
multiple linearizations satisfying the sequential specification. This allows
decisions about the ordering of operations to be delayed, mirroring the
behaviour of data structure implementations. We formalise our method as a
program logic based on rely-guarantee reasoning, and demonstrate its
effectiveness by verifying several challenging data structures: the
Herlihy-Wing queue, the TS queue and the Optimistic set.
Tim Salimans, Andrej Karpathy, Xi Chen, Diederik P. Kingma
Subjects: Learning (cs.LG)
PixelCNNs are a recently proposed class of powerful generative models with
tractable likelihood. Here we discuss our implementation of PixelCNNs which we
make available at this https URL Our implementation
contains a number of modifications to the original model that both simplify its
structure and improve its performance. 1) We use a discretized logistic mixture
likelihood on the pixels, rather than a 256-way softmax, which we find to speed
up training. 2) We condition on whole pixels, rather than R/G/B sub-pixels,
simplifying the model structure. 3) We use downsampling to efficiently capture
structure at multiple resolutions. 4) We introduce additional short-cut
connections to further speed up optimization. 5) We regularize the model using
dropout. Finally, we present state-of-the-art log likelihood results on
CIFAR-10 to demonstrate the usefulness of these modifications.
Martin Grohe, Martin Ritzert
Subjects: Learning (cs.LG); Logic in Computer Science (cs.LO)
We consider a declarative framework for machine learning where concepts and
hypotheses are defined by formulas of a logic over some background structure.
We show that within this framework, concepts defined by first-order formulas
over a background structure of at most polylogarithmic degree can be learned in
polylogarithmic time in the “probably approximately correct” learning sense.
Mieczysław A. Kłopotek
Comments: 10 pages
Subjects: Learning (cs.LG); Machine Learning (stat.ML)
This paper corrects the proof of the Theorem 2 from the Gower’s paper
cite[page 5]{Gower:1982}. The correction is needed in order to establish the
existence of the kernel function used commonly in the kernel trick e.g. for
(k)-means clustering algorithm, on the grounds of distance matrix. The scope of
correction is explained in section 2.
Radu Balan, Maneesh Singh, Dongmian Zou
Comments: 25 pages, 10 figures
Subjects: Learning (cs.LG); Functional Analysis (math.FA)
In this paper we discuss the stability properties of convolutional neural
networks. Convolutional neural networks are widely used in machine learning. In
classification they are mainly used as feature extractors. Ideally, we expect
similar features when the inputs are from the same class. That is, we hope to
see a small change in the feature vector with respect to a deformation on the
input signal. This can be established mathematically, and the key step is to
derive the Lipschitz properties. Further, we establish that the stability
results can be extended for more general networks. We give a formula for
computing the Lipschitz bound, and compare it with other methods to show it is
closer to the optimal value.
Krzysztof J. Cios
Comments: 14 pages, 14 figures
Subjects: Neural and Evolutionary Computing (cs.NE); Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG)
Introduction to deep neural networks and their history.
Dirk Tasche
Comments: 26 pages, 2 figures, 8 tables
Subjects: Machine Learning (stat.ML); Learning (cs.LG); Computation (stat.CO)
We introduce Fisher consistency in the sense of unbiasedness as a criterion
to distinguish potentially suitable and unsuitable estimators of prior class
probabilities in test datasets under prior probability and more general dataset
shift. The usefulness of this unbiasedness concept is demonstrated with three
examples of classifiers used for quantification: Adjusted Classify & Count,
EM-algorithm and CDE-Iterate. We find that Adjusted Classify & Count and
EM-algorithm are Fisher consistent. A counter-example shows that CDE-Iterate is
not Fisher consistent and, therefore, cannot be trusted to deliver reliable
estimates of class probabilities.
Dmitry Molchanov, Arsenii Ashukha, Dmitry Vetrov
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
We explore recently proposed variational dropout technique which provided an
elegant Bayesian interpretation to dropout. We extend variational dropout to
the case when dropout rate is unknown and show that it can be found by
optimizing evidence variational lower bound. We show that it is possible to
assign and find individual dropout rates to each connection in DNN.
Interestingly such assignment leads to extremely sparse solutions both in
fully-connected and convolutional layers. This effect is similar to automatic
relevance determination (ARD) effect in empirical Bayes but has a number of
advantages. We report up to 128 fold compression of popular architectures
without a large loss of accuracy providing additional evidence to the fact that
modern deep architectures are very redundant.
Wilson Hsu, Agastya Kalra, Pascal Poupart
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
Sum-product networks have recently emerged as an attractive representation
due to their dual view as a special type of deep neural network with clear
semantics and a special type of probabilistic graphical model for which
inference is always tractable. Those properties follow from some conditions
(i.e., completeness and decomposability) that must be respected by the
structure of the network. As a result, it is not easy to specify a valid
sum-product network by hand and therefore structure learning techniques are
typically used in practice. This paper describes the first online structure
learning technique for continuous SPNs with Gaussian leaves. We also introduce
an accompanying new parameter learning technique.
Konstantina Christakopoulou, Jaya Kawale, Arindam Banerjee
Subjects: Machine Learning (stat.ML); Information Retrieval (cs.IR); Learning (cs.LG)
In this paper, we investigate the common scenario where every candidate item
for recommendation is characterized by a maximum capacity, i.e., number of
seats in a Point-of-Interest or size of an item’s inventory. Despite the
prevalence of the task of recommending items under capacity constraints in a
variety of settings, to the best of our knowledge, none of the known
recommender methods is designed to respect capacity constraints. To close this
gap, we extend two state-of-the art latent factor recommendation approaches:
probabilistic matrix factorization (PMF) and geographical matrix factorization
(GeoMF), to optimize for both prediction accuracy and expected item usage that
respects the capacity constraints. We introduce the useful concepts of user
propensity to listen and item capacity. Our experimental results in public
datasets, both for the domain of item recommendation and Point-of-Interest
recommendation, highlight the benefit of our method for the setting of
recommendation under capacity constraints.
I. Theodorakopoulos, V. Pothos, D. Kastaniotis, N. Fragoulis
Comments: 17 pages, 10 figures, 5 tables
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Neural and Evolutionary Computing (cs.NE)
A new, radical CNN design approach is presented in this paper, considering
the reduction of the total computational load during inference. This is
achieved by a new holistic intervention on both the CNN architecture and the
training procedure, which targets to the parsimonious inference by learning to
exploit or remove the redundant capacity of a CNN architecture. This is
accomplished, by the introduction of a new structural element that can be
inserted as an add-on to any contemporary CNN architecture, whilst preserving
or even improving its recognition accuracy. Our approach formulates a
systematic and data-driven method for developing CNNs that are trained to
eventually change size and form in real-time during inference, targeting to the
smaller possible computational footprint. Results are provided for the optimal
implementation on a few modern, high-end mobile computing platforms indicating
a significant speed-up of up to x3 times.
Ilya Soloveychik, Yu Xiang, Vahid Tarokh
Subjects: Information Theory (cs.IT)
In this article we consider the problem of generating pseudo-random matrices
based on the similarity of their spectra to Wigner’s semicircular law. We
introduce (r)-independent pseudo-Wigner ensembles and prove closeness of their
spectra to the semicircular density in Kolmogorov metric. We give an explicit
construction of a family of pseudo-Wigner ensembles using dual BCH codes and
show that the Kolmogorov complexity of the constructed matrices is
comparatively low. We compare our construction to the quasi-random graphs
introduced by Chung, Graham and Wilson and show that the pseudo-Wigner matrices
pass more tests for randomness. Finally, we support our theoretical results by
numerical simulations.
Linqi Song, Christina Fragouli
Subjects: Information Theory (cs.IT)
A promising research area that has recently emerged, is on how to use index
coding to improve the communication efficiency in distributed computing
systems, especially for data shuffling in iterative computations. In this
paper, we posit that pliable index coding can offer a more efficient framework
for data shuffling, as it can better leverage the many possible shuffling
choices to reduce the number of transmissions. We theoretically analyze pliable
index coding under data shuffling constraints, and design an hierarchical
data-shuffling scheme that uses pliable coding as a component. We find benefits
up to (O(ns/m)) over index coding, where (ns/m) is the average number of
workers caching a message, and (m), (n), and (s) are the numbers of messages,
workers, and cache size, respectively.
Edwin Hammerich
Comments: 6 pages, 3 figures; extended version of submission to ISIT 2017
Subjects: Information Theory (cs.IT)
For vector Gaussian channels, a precise differential connection between
channel capacity and a quantity termed normalized optimal detection error
(NODE) is presented. Then, this C-NODE relationship is extended to
continuous-time Gaussian channels drawing on a waterfilling characterization
recently found for the capacity of continuous-time linear time-varying
channels. In the latter case, the C-NODE relationship becomes asymptotic in
nature. In either case, the C-NODE relationship is compared with the I-MMSE
relationship due to Guo et al. connecting mutual information in Gaussian
channels with the minimum mean-square error (MMSE) of estimation theory.
Jack Pfister, Marco A. C. Gomes, Joao P. Vilela, Willie K. Harrison
Comments: Submitted to ICC 2017
Subjects: Information Theory (cs.IT)
This paper presents a new technique for providing the analysis and comparison
of wiretap codes in the small blocklength regime over the binary erasure
wiretap channel. A major result is the development of Monte Carlo strategies
for quantifying a code’s equivocation, which mirrors techniques used to analyze
normal error correcting codes. For this paper, we limit our analysis to
coset-based wiretap codes, and make several comparisons of different code
families at small and medium blocklengths. Our results indicate that there are
security advantages to using specific codes when using small to medium
blocklengths.
Fatima Salahdine (UND), Naima Kaabouch (UND), Hassan Ghazi (UND)
Comments: in IEEE CCWC 2017 The 7th IEEE Annual Computing and Communication Workshop and Conference , Jan 2017, Las Vegas, United States
Subjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI)
A cognitive radio system has the ability to observe and learn from the
environment, adapt to the environmental conditions, and use the radio spectrum
more efficiently. However, due to multipath fading, shadowing, or varying
channel conditions, uncertainty affects the cognitive cycle processes,
measurements, decisions, and actions. In the observing step, measurements
(i.e., information) taken by the secondary users (SUs) are uncertain. In the
next step, the SUs make decisions based on what has already been observed using
their knowledge bases, which may have been impacted by the uncertainty, leading
to wrong decisions. In the last step, uncertainty can affect the decision of
the cognitive radio system, which sometimes can lead to the wrong action. Thus,
the uncertainty propagation influences the cognitive radio performance.
Therefore, mitigating the uncertainty in the cognitive cycle is a necessity.
This paper provides a deep overview of techniques that handle uncertainty in
cognitive radio networks.
Milad Rezaee, Mahtab Mirmohseni, Mohammad Reza Aref
Comments: This paper has been submitted to IEEE Wireless Communications Letters
Subjects: Information Theory (cs.IT)
Energy harvesting (EH) has been developed to extend the lifetimes of
energy-limited communication systems. In this letter, we consider a single-user
EH communication system, in which both of the arrival data and the harvested
energy curves are modeled as general functions. Unlike most of the works in the
field, we investigate the online algorithms which only acquire the causal
information of the arrival data and the harvested energy processes. We study
how well the optimal online algorithm works compared with the optimal offline
algorithm, and thus our goal is to find the lower and upper bounds for the
ratio of the completion time in the optimal online algorithm to the optimal
offline algorithm. We propose two online algorithms which achieve the upper
bound of 2 on this ratio. Also, we show that this ratio is 2 for the optimal
online algorithm.
M. Fauß, K. G. Nagananda, A. M. Zoubir, H. V. Poor
Comments: 5 pages, Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2017
Subjects: Information Theory (cs.IT)
The sequential analysis of the problem of joint signal detection and
signal-to-noise ratio (SNR) estimation for a linear Gaussian observation model
is considered. The problem is posed as an optimization setup where the goal is
to minimize the number of samples required to achieve the desired (i) type I
and type II error probabilities and (ii) mean squared error performance. This
optimization problem is reduced to a more tractable formulation by transforming
the observed signal and noise sequences to a single sequence of Bernoulli
random variables; joint detection and estimation is then performed on the
Bernoulli sequence. This transformation renders the problem easily solvable,
and results in a computationally simpler sufficient statistic compared to the
one based on the (untransformed) observation sequences. Experimental results
demonstrate the advantages of the proposed method, making it feasible for
applications having strict constraints on data storage and computation.
Keigo Takeuchi
Comments: Submitted to IEEE Trans. Inf. Theory. A short version of this paper was submitted to ISIT2017
Subjects: Information Theory (cs.IT)
Signal recovery from unitarily invariant measurements is investigated in this
paper. A message-passing algorithm is formulated on the basis of expectation
propagation (EP). A rigorous analysis is presented for the dynamics of the
algorithm in the large system limit, where both input and output dimensions
tend to infinity while the compression rate is kept constant. The main result
is the justification of state evolution (SE) equations conjectured by Ma and
Ping in 2016. This result implies that the EP-based algorithm achieves the
Bayes-optimal performance derived by Takeda et al. in 2006 via a non-rigorous
tool in statistical physics, when the compression rate is larger than a
threshold. The proof is based on an extension of a conventional conditioning
technique for the standard Gaussian matrix to the case of the Haar matrix.
Mohsen Mohammadkhani Razlighi, Nikola Zlatanov
Comments: 30 pages, 5 figures, submitted to IEEE Transactions on Wireless Communications
Subjects: Information Theory (cs.IT)
In this paper, we propose a novel reception/transmission scheme for
half-duplex base stations (BSs). In particular, we propose a half-duplex BS
that employes in-band uplink-receptions from user 1 and downlink-transmissions
to user 2, which occur in different time slots. Furthermore, we propose optimal
adaptive scheduling of the in-band uplink-receptions and downlink-transmissions
of the BS such that the uplink-downlink rate/throughput region is maximized and
the outage probabilities of the uplink and downlink channels are minimized.
Practically, this results in selecting whether in a given time slot the BS
should receive from user 1 or transmit to user 2 based on the qualities of the
in-band uplink-reception and downlink-transmission channels. Compared to the
performance achieved with a conventional full-duplex division (FDD) base
station, two main gains can be highlighted: 1) Increased uplink-downlink
rate/throughput region; 2) Doubling of the diversity gain of both the uplink
and downlink channels.
Xiaoyi Liu, Hamid Jafarkhani
Comments: 33 pages
Subjects: Information Theory (cs.IT)
In this paper, we analyze downlink non-orthogonal multiple access (NOMA)
networks with limited feedback. Our goal is to derive appropriate transmission
rates for rate adaptation and minimize outage probability of minimum rate for
the constant-rate data service, based on distributed channel feedback
information from receivers. We propose an efficient quantizer with
variable-length encoding that approaches the best performance of the case where
perfect channel state information is available anywhere. We prove that in the
typical application with two receivers, the losses in the minimum rate and
outage probability decay at least exponentially with the minimum feedback rate.
We analyze the diversity gain and provide a sufficient condition for the
quantizer to achieve the maximum diversity order. For NOMA with (K) receivers
where (K > 2), we find the maximum minimum rate within an accuracy of
(epsilon) in time complexity of (Oleft(Klogfrac{1}{epsilon}
ight)), then,
we apply the previously proposed quantizers for (K = 2) to (K > 2). Numerical
simulations are presented to demonstrate the efficiency of our proposed
quantizers and the accuracy of the analytical results.
Ferdinando Cicalese, Luisa Gargano, Ugo Vaccaro
Comments: A short version will be submitted to ISIT 2017
Subjects: Information Theory (cs.IT); Data Structures and Algorithms (cs.DS)
Given two discrete random variables (X) and (Y), with probability
distributions ({f p} =(p_1, ldots , p_n)) and ({f q}=(q_1, ldots , q_m)),
respectively, denote by ({cal C}({f p}, {f q})) the set of all couplings
of ({f p}) and ({f q}), that is, the set of all bivariate probability
distributions that have ({f p}) and ({f q}) as marginals. In this paper, we
study the problem of finding the joint probability distribution in ({cal
C}({f p}, {f q})) of minimum entropy (equivalently, the joint probability
distribution that maximizes the mutual information between (X) and (Y)), and we
discuss several situations where the need for this kind of optimization
naturally arises. Since the optimization problem is known to be NP-hard, we
give an efficient algorithm to find a joint probability distribution in ({cal
C}({f p}, {f q})) with entropy exceeding the minimum possible by at most 1,
thus providing an approximation algorithm with additive approximation factor of
1. We also discuss some related applications of our findings.
Alexander Barg, Kathryn Haymaker, Everett W. Howe, Gretchen L. Matthews, Anthony Várilly-Alvarado
Comments: 27 pages
Subjects: Information Theory (cs.IT); Algebraic Geometry (math.AG)
A locally recoverable code is a code over a finite alphabet such that the
value of any single coordinate of a codeword can be recovered from the values
of a small subset of other coordinates. Building on work of Barg, Tamo, and
Vlu{a}duc{t}, we present several constructions of locally recoverable codes
from algebraic curves and surfaces.
Ahmad Adib Shaar, Lenny Fukshansky
Comments: 8 pages, 5 tables
Subjects: Information Theory (cs.IT); Combinatorics (math.CO)
We present a new family of one-coincidence sequence sets suitable for
frequency hopping code division multiple access (FH-CDMA) systems with
dispersed (low density) sequence elements. These sets are derived from
one-coincidence prime sequence sets, such that for each one-coincidence prime
sequence set there is a new one-coincidence set comprised of sequences with
dispersed sequence elements, required in some circumstances, for FH-CDMA
systems. Getting rid of crowdedness of sequence elements is achieved by
doubling the size of the sequence element alphabet. In addition, this doubling
process eases control over the distance between adjacent sequence elements.
Properties of the new sets are discussed.