Jin-Hwa Kim, Kyoung Woon On, Jeonghee Kim, Jung-Woo Ha, Byoung-Tak Zhang
Comments: 13 pages, 1 figure, & appendix included
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Neural and Evolutionary Computing (cs.NE)
Bilinear models provide rich representations compared to linear models. They
have been applied in various visual tasks, such as object recognition,
segmentation, and visual question-answering, to get state-of-the-art
performances taking advantage of the expanded representations. However,
bilinear representations tend to be high-dimensional, limiting the
applicability to computationally complex tasks. We propose low-rank bilinear
neural networks using Hadamard product (element-wise multiplication), commonly
implemented in many scientific computing frameworks. We show that our model
outperforms compact bilinear pooling in visual question-answering tasks, having
a better parsimonious property.
Shuai Zheng, Chris Ding
Comments: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD, 2014
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
Kernel alignment measures the degree of similarity between two kernels. In
this paper, inspired from kernel alignment, we propose a new Linear
Discriminant Analysis (LDA) formulation, kernel alignment LDA (kaLDA). We first
define two kernels, data kernel and class indicator kernel. The problem is to
find a subspace to maximize the alignment between subspace-transformed data
kernel and class indicator kernel. Surprisingly, the kernel alignment induced
kaLDA objective function is very similar to classical LDA and can be expressed
using between-class and total scatter matrices. This can be extended to
multi-label data. We use a Stiefel-manifold gradient descent algorithm to solve
this problem. We perform experiments on 8 single-label and 6 multi-label data
sets. Results show that kaLDA has very good performance on many single-label
and multi-label problems.
Jyothi Korra
Subjects: Computer Vision and Pattern Recognition (cs.CV)
This paper implements and compares different techniques for face detection
and recognition. One is find where the face is located in the images that is
face detection and second is face recognition that is identifying the person.
We study three techniques in this paper: Face detection using self organizing
map (SOM), Face recognition by projection and nearest neighbor and Face
recognition using SVM.
Andras Rozsa, Manuel Günther, Terrance E. Boult
Comments: Submitted for review at ICMLA 2016
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Machine learning models are vulnerable to adversarial examples formed by
applying small carefully chosen perturbations to inputs that cause unexpected
classification errors. In this paper, we perform experiments on various
adversarial example generation approaches with multiple deep convolutional
neural networks including Residual Networks, the best performing models on
ImageNet Large-Scale Visual Recognition Challenge 2015. We compare the
adversarial example generation techniques with respect to the quality of the
produced images, and measure the robustness of the tested machine learning
models to adversarial examples. Finally, we conduct large-scale experiments on
cross-model adversarial portability. We find that adversarial examples are
mostly transferable across similar network topologies, and we demonstrate that
better machine learning models are less vulnerable to adversarial examples.
Yicong Tian, Mubarak Shah
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Traditionally, object tracking and segmentation are treated as two separate
problems and solved independently. However, in this paper, we argue that
tracking and segmentation are actually closely related and solving one should
help the other. On one hand, the object track, which is a set of bounding boxes
with one bounding box in every frame, would provide strong high-level guidance
for the target/background segmentation task. On the other hand, the object
segmentation would separate object from other objects and background, which
will be useful for determining track locations in every frame. We propose a
novel framework which combines online multiple target tracking and segmentation
in a video. In our approach, the tracking and segmentation problems are coupled
by Lagrange dual decomposition, which leads to more accurate segmentation
results and also emph{helps resolve typical difficulties in multiple target
tracking, such as occlusion handling, ID-switch and track drifting}. To track
targets, an individual appearance model is learned for each target via
structured learning and network flow is employed to generate tracks from
densely sampled candidates. For segmentation, multi-label Conditional Random
Field (CRF) is applied to a superpixel based spatio-temporal graph in a segment
of video to assign background or target labels to every superpixel. The
experiments on diverse sequences show that our method outperforms
state-of-the-art approaches for multiple target tracking as well as
segmentation.
Casper Kaae Sønderby, Jose Caballero, Lucas Theis, Wenzhe Shi, Ferenc Huszár
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Machine Learning (stat.ML)
Image Super-resolution (SR) is an underdetermined inverse problem, where a
large number of plausible high-resolution images can explain the same
downsampled image. Most current single image SR methods use empirical risk
minimisation, often with a pixel-wise mean squared error (MSE) loss. However,
the outputs from such methods tend to be blurry, over-smoothed and generally
appear implausible. A more desirable approach would employ Maximum a Posteriori
(MAP) inference, preferring solutions that always have a high probability under
the image prior, and thus appear more plausible. Direct MAP estimation for SR
is non-trivial, as it requires us to build a model for the image prior from
samples. Furthermore, MAP inference is often performed via optimisation-based
iterative algorithms which don’t compare well with the efficiency of
neural-network-based alternatives. Here we introduce new methods for amortised
MAP inference whereby we calculate the MAP estimate directly using a
convolutional neural network. We first introduce a novel neural network
architecture that performs a projection to the affine subspace of valid SR
solutions ensuring that the high resolution output of the network is always
consistent with the low resolution input. We show that, using this
architecture, the amortised MAP inference problem reduces to minimising the
cross-entropy between two distributions, similar to training generative models.
We propose three methods to solve this optimisation problem: (1) Generative
Adversarial Networks (GAN) (2) denoiser-guided SR which backpropagates
gradient-estimates from denoising to train the network, and (3) a baseline
method using a maximum-likelihood-trained image prior. Our experiments show
that the GAN based approach performs best on real image data, achieving
particularly good results in photo-realistic texture SR.
Brijnesh J. Jain, David Schultz
Subjects: Computer Vision and Pattern Recognition (cs.CV); Optimization and Control (math.OC); Machine Learning (stat.ML)
Though the concept of sample mean in dynamic time warping (DTW) spaces is
used in pattern recognition applications, its existence has neither been proved
nor called into question. This article shows that a sample mean exists under
general conditions that cover common variations of different DTW-spaces
mentioned in the literature. The existence proofs are based on a Reduction
Theorem that bounds the length of the candidate solutions we need to consider.
The proposed results place the concept of sample mean in DTW-spaces on a sound
mathematical foundation and serves as a first step towards a statistical theory
of DTW-spaces.
Jin-Hwa Kim, Kyoung Woon On, Jeonghee Kim, Jung-Woo Ha, Byoung-Tak Zhang
Comments: 13 pages, 1 figure, & appendix included
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Neural and Evolutionary Computing (cs.NE)
Bilinear models provide rich representations compared to linear models. They
have been applied in various visual tasks, such as object recognition,
segmentation, and visual question-answering, to get state-of-the-art
performances taking advantage of the expanded representations. However,
bilinear representations tend to be high-dimensional, limiting the
applicability to computationally complex tasks. We propose low-rank bilinear
neural networks using Hadamard product (element-wise multiplication), commonly
implemented in many scientific computing frameworks. We show that our model
outperforms compact bilinear pooling in visual question-answering tasks, having
a better parsimonious property.
Wei Li, Zhigang Zhu
Comments: An experiment to feature fusion in deep learning
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We propose a deep learning-based feature fusion approach for facial computing
including face recognition as well as gender, race and age detection. Instead
of training a single classifier on face images to classify them based on the
features of the person whose face appears in the image, we first train four
different classifiers for classifying face images based on race, age, gender
and identification (ID). Multi-task features are then extracted from the
trained models and cross-task-feature training is conducted which shows the
value of fusing multimodal features extracted from multi-tasks. We have found
that features trained for one task can be used for other related tasks. More
interestingly, the features trained for a task with more classes (e.g. ID) and
then used in another task with fewer classes (e.g. race) outperforms the
features trained for the other task itself. The final feature fusion is
performed by combining the four types of features extracted from the images by
the four classifiers. The feature fusion approach improves the classifications
accuracy by a 7.2%, 20.1%, 22.2%, 21.8% margin, respectively, for ID, age, race
and gender recognition, over the results of single classifiers trained only on
their individual features. The proposed method can be applied to applications
in which different types of data or features can be extracted.
Min Liu, Yifei Shi, Lintao Zheng, Kai Xu
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Active vision is inherently attention-driven: The agent selects views of
observation to best approach the vision task while improving its internal
representation of the scene being observed. Inspired by the recent success of
attention-based models in 2D vision tasks based on single RGB images, we
propose to address the multi-view depth-based active object recognition using
attention mechanism, through developing an end-to-end recurrent 3D attentional
network. The architecture comprises of a recurrent neural network (RNN),
storing and updating an internal representation, and two levels of spatial
transformer units, guiding two-level attentions. Our model, trained with a 3D
shape database, is able to iteratively attend to the best views targeting an
object of interest for recognizing it, and focus on the object in each view for
removing the background clutter. To realize 3D view selection, we derive a 3D
spatial transformer network which is differentiable for training with
back-propagation, achieving must faster convergence than the reinforcement
learning employed by most existing attention-based models. Experiments show
that our method outperforms state-of-the-art methods in cluttered scenes.
Guangliang Du, Minmin Wang, Canlin Zhou, Shuchun Si, Hui Li, Zhenkun Lei, Yanjie Li
Comments: 15 pages, 11 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Conventional dual-frequency fringe projection algorithm often suffers from
phase unwrapping failure when the frequency ratio between the high frequency
and the low one is too large. Zhang et.al. proposed an enhanced two-frequency
phase-shifting method to use geometric constraints of digital fringe
projection(DFP) to reduce the noise impact due to the large frequency ratio.
However, this method needs to calibrate the DFP system and calculate the
minimum phase map at the nearest position from the camera perspective, these
procedures are are relatively complex and more time-cosuming. In this paper, we
proposed an improved method, which eliminates the system calibration and
determination in Zhang’s method,meanwhile does not need to use the low
frequency fringe pattern. In the proposed method,we only need a set of high
frequency fringe patterns to measure the object after the high frequency is
directly estimated by the experiment. Thus the proposed method can simplify the
procedure and improve the speed. Finally, the experimental evaluation is
conducted to prove the validity of the proposed method.The results demonstrate
that the proposed method can overcome the main disadvantages encountered by
Zhang’s method.
Abigail Graese, Andras Rozsa, Terrance E. Boult
Comments: This is a pre-print version to appear in IEEE ICMLA 2016
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Deep neural networks are facing a potential security threat from adversarial
examples, inputs that look normal but cause an incorrect classification by the
deep neural network. For example, the proposed threat could result in
hand-written digits on a scanned check being incorrectly classified but looking
normal when humans see them. This research assesses the extent to which
adversarial examples pose a security threat, when one considers the normal
image acquisition process. This process is mimicked by simulating the
transformations that normally occur in acquiring the image in a real world
application, such as using a scanner to acquire digits for a check amount or
using a camera in an autonomous car. These small transformations negate the
effect of the carefully crafted perturbations of adversarial examples,
resulting in a correct classification by the deep neural network. Thus just
acquiring the image decreases the potential impact of the proposed security
threat. We also show that the already widely used process of averaging over
multiple crops neutralizes most adversarial examples. Normal preprocessing,
such as text binarization, almost completely neutralizes adversarial examples.
This is the first paper to show that for text driven classification,
adversarial examples are an academic curiosity, not a security threat.
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Comments: 35 pages, 11 figures
Subjects: Information Theory (cs.IT); Computer Vision and Pattern Recognition (cs.CV); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC); Machine Learning (stat.ML)
Various alignment problems arising in cryo-electron microscopy, community
detection, time synchronization, computer vision, and other fields fall into a
common framework of synchronization problems over compact groups such as Z/L,
U(1), or SO(3). The goal of such problems is to estimate an unknown vector of
group elements given noisy relative observations. We present an efficient
iterative algorithm to solve a large class of these problems, allowing for any
compact group, with measurements on multiple ‘frequency channels’ (Fourier
modes, or more generally, irreducible representations of the group). Our
algorithm is a highly efficient iterative method following the blueprint of
approximate message passing (AMP), which has recently arisen as a central
technique for inference problems such as structured low-rank estimation and
compressed sensing. We augment the standard ideas of AMP with ideas from
representation theory so that the algorithm can work with distributions over
compact groups. Using standard but non-rigorous methods from statistical
physics we analyze the behavior of our algorithm on a Gaussian noise model,
identifying phases where the problem is easy, (computationally) hard, and
(statistically) impossible. In particular, such evidence predicts that our
algorithm is information-theoretically optimal in many cases, and that the
remaining cases show evidence of statistical-to-computational gaps.
Jeffrey P. Nguyen, Ashley N. Linder, George S. Plummer, Joshua W. Shaevitz, Andrew M. Leifer
Comments: 33 pages, 7 figures, code available
Subjects: Neurons and Cognition (q-bio.NC); Computer Vision and Pattern Recognition (cs.CV); Biological Physics (physics.bio-ph)
Advances in optical neuroimaging techniques now allow neural activity to be
recorded with cellular resolution in awake and behaving animals. Brain motion
in these recordings pose a unique challenge. The location of individual neurons
must be tracked in 3D over time to accurately extract single neuron activity
traces. Recordings from small invertebrates like C. elegans are especially
challenging because they undergo very large brain motion and deformation during
animal movement. Here we present an automated computer vision pipeline to
reliably track populations of neurons with single neuron resolution in the
brain of a freely moving C. elegans undergoing large motion and deformation. 3D
volumetric fluorescent images of the animal’s brain are straightened, aligned
and registered, and the locations of neurons in the images are found via
segmentation. Each neuron is then assigned an identity using a new
time-independent machine-learning approach we call Neuron Registration Vector
Encoding. In this approach, non-rigid point-set registration is used to match
each segmented neuron in each volume with a set of reference volumes taken from
throughout the recording. The way each neuron matches with the references
defines a feature vector which is clustered to assign an identity to each
neuron in each volume. Finally, thin-plate spline interpolation is used to
correct errors in segmentation and check consistency of assigned identities.
The Neuron Registration Vector Encoding approach proposed here is uniquely well
suited for tracking neurons in brains undergoing large deformations. When
applied to whole-brain calcium imaging recordings in freely moving C. elegans,
this analysis pipeline located 150 neurons for the duration of an 8 minute
recording and consistently found more neurons more quickly than manual or
semi-automated approaches.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, Miguel R. D. Rodrigues
Comments: 9 pages, 3 figures
Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG)
This paper studies the generalization error of invariant classifiers. In
particular, we consider the common scenario where the classification task is
invariant to certain transformations of the input, and that the classifier is
constructed (or learned) to be invariant to these transformations. Our approach
relies on factoring the input space into a product of a base space and a set of
transformations. We show that whereas the generalization error of a
non-invariant classifier is proportional to the complexity of the input space,
the generalization error of an invariant classifier is proportional to the
complexity of the base space. We also derive a set of sufficient conditions on
the geometry of the base space and the set of transformations that ensure that
the complexity of the base space is much smaller than the complexity of the
input space. Our analysis applies to general classifiers such as convolutional
neural networks. We demonstrate the implications of the developed theory for
such classifiers with experiments on the MNIST and CIFAR-10 datasets.
Hamid Laga, Qian Xie, Ian H. Jermyn, Anuj Srivastava
Subjects: Graphics (cs.GR); Computational Geometry (cs.CG); Computer Vision and Pattern Recognition (cs.CV)
Recent developments in elastic shape analysis (ESA) are motivated by the fact
that it provides comprehensive frameworks for simultaneous registration,
deformation, and comparison of shapes. These methods achieve computational
efficiency using certain square-root representations that transform invariant
elastic metrics into Euclidean metrics, allowing for applications of standard
algorithms and statistical tools. For analyzing shapes of embeddings of
$mathbb{S}^2$ in $mathbb{R}^3$, Jermyn et al. introduced square-root normal
fields (SRNFs) that transformed an elastic metric, with desirable invariant
properties, into the $mathbb{L}^2$ metric. These SRNFs are essentially surface
normals scaled by square-roots of infinitesimal area elements. A critical need
in shape analysis is to invert solutions (deformations, averages, modes of
variations, etc) computed in the SRNF space, back to the original surface space
for visualizations and inferences. Due to the lack of theory for understanding
SRNFs maps and their inverses, we take a numerical approach and derive an
efficient multiresolution algorithm, based on solving an optimization problem
in the surface space, that estimates surfaces corresponding to given SRNFs.
This solution is found effective, even for complex shapes, e.g. human bodies
and animals, that undergo significant deformations including bending and
stretching. Specifically, we use this inversion for computing elastic shape
deformations, transferring deformations, summarizing shapes, and for finding
modes of variability in a given collection, while simultaneously registering
the surfaces. We demonstrate the proposed algorithms using a statistical
analysis of human body shapes, classification of generic surfaces and analysis
of brain structures.
Shuai Zheng, Chris Ding
Comments: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD, 2014
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
Kernel alignment measures the degree of similarity between two kernels. In
this paper, inspired from kernel alignment, we propose a new Linear
Discriminant Analysis (LDA) formulation, kernel alignment LDA (kaLDA). We first
define two kernels, data kernel and class indicator kernel. The problem is to
find a subspace to maximize the alignment between subspace-transformed data
kernel and class indicator kernel. Surprisingly, the kernel alignment induced
kaLDA objective function is very similar to classical LDA and can be expressed
using between-class and total scatter matrices. This can be extended to
multi-label data. We use a Stiefel-manifold gradient descent algorithm to solve
this problem. We perform experiments on 8 single-label and 6 multi-label data
sets. Results show that kaLDA has very good performance on many single-label
and multi-label problems.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, Miguel R. D. Rodrigues
Comments: 9 pages, 3 figures
Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG)
This paper studies the generalization error of invariant classifiers. In
particular, we consider the common scenario where the classification task is
invariant to certain transformations of the input, and that the classifier is
constructed (or learned) to be invariant to these transformations. Our approach
relies on factoring the input space into a product of a base space and a set of
transformations. We show that whereas the generalization error of a
non-invariant classifier is proportional to the complexity of the input space,
the generalization error of an invariant classifier is proportional to the
complexity of the base space. We also derive a set of sufficient conditions on
the geometry of the base space and the set of transformations that ensure that
the complexity of the base space is much smaller than the complexity of the
input space. Our analysis applies to general classifiers such as convolutional
neural networks. We demonstrate the implications of the developed theory for
such classifiers with experiments on the MNIST and CIFAR-10 datasets.
Shiu Kumar, Ronesh Sharma, Edwin Vans
Comments: 11 pages, 7 figures, 1 table, IJCNC
Journal-ref: International Journal of Computer Networks & Communications
(IJCNC), vol. 8, pp. 61-71, January 2016
Subjects: Networking and Internet Architecture (cs.NI); Artificial Intelligence (cs.AI)
As Wireless Sensor Networks are penetrating into the industrial domain, many
research opportunities are emerging. One such essential and challenging
application is that of node localization. A feed-forward neural network based
methodology is adopted in this paper. The Received Signal Strength Indicator
(RSSI) values of the anchor node beacons are used. The number of anchor nodes
and their configurations has an impact on the accuracy of the localization
system, which is also addressed in this paper. Five different training
algorithms are evaluated to find the training algorithm that gives the best
result. The multi-layer Perceptron (MLP) neural network model was trained using
Matlab. In order to evaluate the performance of the proposed method in real
time, the model obtained was then implemented on the Arduino microcontroller.
With four anchor nodes, an average 2D localization error of 0.2953 m has been
achieved with a 12-12-2 neural network structure. The proposed method can also
be implemented on any other embedded microcontroller system.
Casper Kaae Sønderby, Jose Caballero, Lucas Theis, Wenzhe Shi, Ferenc Huszár
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Machine Learning (stat.ML)
Image Super-resolution (SR) is an underdetermined inverse problem, where a
large number of plausible high-resolution images can explain the same
downsampled image. Most current single image SR methods use empirical risk
minimisation, often with a pixel-wise mean squared error (MSE) loss. However,
the outputs from such methods tend to be blurry, over-smoothed and generally
appear implausible. A more desirable approach would employ Maximum a Posteriori
(MAP) inference, preferring solutions that always have a high probability under
the image prior, and thus appear more plausible. Direct MAP estimation for SR
is non-trivial, as it requires us to build a model for the image prior from
samples. Furthermore, MAP inference is often performed via optimisation-based
iterative algorithms which don’t compare well with the efficiency of
neural-network-based alternatives. Here we introduce new methods for amortised
MAP inference whereby we calculate the MAP estimate directly using a
convolutional neural network. We first introduce a novel neural network
architecture that performs a projection to the affine subspace of valid SR
solutions ensuring that the high resolution output of the network is always
consistent with the low resolution input. We show that, using this
architecture, the amortised MAP inference problem reduces to minimising the
cross-entropy between two distributions, similar to training generative models.
We propose three methods to solve this optimisation problem: (1) Generative
Adversarial Networks (GAN) (2) denoiser-guided SR which backpropagates
gradient-estimates from denoising to train the network, and (3) a baseline
method using a maximum-likelihood-trained image prior. Our experiments show
that the GAN based approach performs best on real image data, achieving
particularly good results in photo-realistic texture SR.
Dimitri Kartsaklis, Mehrnoosh Sadrzadeh
Comments: To appear in COLING 2016
Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI)
According to the distributional inclusion hypothesis, entailment between
words can be measured via the feature inclusions of their distributional
vectors. In recent work, we showed how this hypothesis can be extended from
words to phrases and sentences in the setting of compositional distributional
semantics. This paper focuses on inclusion properties of tensors; its main
contribution is a theoretical and experimental analysis of how feature
inclusion works in different concrete models of verb tensors. We present
results for relational, Frobenius, projective, and holistic methods and compare
them to the simple vector addition, multiplication, min, and max models. The
degrees of entailment thus obtained are evaluated via a variety of existing
word-based measures, such as Weed’s and Clarke’s, KL-divergence, APinc,
balAPinc, and two of our previously proposed metrics at the phrase/sentence
level. We perform experiments on three entailment datasets, investigating which
version of tensor-based composition achieves the highest performance when
combined with the sentence-level measures.
Jin-Hwa Kim, Kyoung Woon On, Jeonghee Kim, Jung-Woo Ha, Byoung-Tak Zhang
Comments: 13 pages, 1 figure, & appendix included
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Neural and Evolutionary Computing (cs.NE)
Bilinear models provide rich representations compared to linear models. They
have been applied in various visual tasks, such as object recognition,
segmentation, and visual question-answering, to get state-of-the-art
performances taking advantage of the expanded representations. However,
bilinear representations tend to be high-dimensional, limiting the
applicability to computationally complex tasks. We propose low-rank bilinear
neural networks using Hadamard product (element-wise multiplication), commonly
implemented in many scientific computing frameworks. We show that our model
outperforms compact bilinear pooling in visual question-answering tasks, having
a better parsimonious property.
Issa Atoum, Ahmed Otoom, Narayanan Kulathuramaiyer
Comments: 7 pages,4 figures
Journal-ref: International Journal of Computer Applications,2016,135(1),
Foundation of Computer Science (FCS), NY, USA
Subjects: Information Retrieval (cs.IR); Computation and Language (cs.CL)
Sentence similarity is considered the basis of many natural language tasks
such as information retrieval, question answering and text summarization. The
semantic meaning between compared text fragments is based on the words semantic
features and their relationships. This article reviews a set of word and
sentence similarity measures and compares them on benchmark datasets. On the
studied datasets, results showed that hybrid semantic measures perform better
than both knowledge and corpus based measures.
Qiwen Wang, Mikael Skoglund
Subjects: Information Theory (cs.IT); Cryptography and Security (cs.CR); Information Retrieval (cs.IR)
A user wants to retrieve a file from a database without revealing the
identity of the file retrieved at the database, which is known as the problem
of private information retrieval (PIR). If it is further required that the user
obtains no information about the database other than the desired file, the
concept of symmetric private information retrieval (SPIR) is introduced to
guarantee privacy for both parties. In this paper, the problem of SPIR is
studied for a database stored among $N$ nodes in a distributed way, by using an
$(N,M)$-MDS storage code. The information-theoretic capacity of SPIR, defined
as the maximum number of symbols of the desired file retrieved per downloaded
symbol, for the coded database is derived. It is shown that the SPIR capacity
for coded database is $1-frac{M}{N}$, when the amount of the shared common
randomness of distributed nodes (unavailable at the user) is at least
$frac{M}{N-M}$ times the file size. Otherwise, the SPIR capacity for the coded
database equals zero.
Dimitri Kartsaklis, Mehrnoosh Sadrzadeh
Comments: To appear in COLING 2016
Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI)
According to the distributional inclusion hypothesis, entailment between
words can be measured via the feature inclusions of their distributional
vectors. In recent work, we showed how this hypothesis can be extended from
words to phrases and sentences in the setting of compositional distributional
semantics. This paper focuses on inclusion properties of tensors; its main
contribution is a theoretical and experimental analysis of how feature
inclusion works in different concrete models of verb tensors. We present
results for relational, Frobenius, projective, and holistic methods and compare
them to the simple vector addition, multiplication, min, and max models. The
degrees of entailment thus obtained are evaluated via a variety of existing
word-based measures, such as Weed’s and Clarke’s, KL-divergence, APinc,
balAPinc, and two of our previously proposed metrics at the phrase/sentence
level. We perform experiments on three entailment datasets, investigating which
version of tensor-based composition achieves the highest performance when
combined with the sentence-level measures.
Diptesh Kanojia, Vishwajeet Kumar, Krithi Ramamritham
Comments: This paper was presented at Workshop on Social Data Analytics and Management (SoDAM 2016), at Very Large Databases (VLDB 2016), in September 2016
Subjects: Computation and Language (cs.CL); Computers and Society (cs.CY); Social and Information Networks (cs.SI)
We present the Civique system for emergency detection in urban areas by
monitoring micro blogs like Tweets. The system detects emergency related
events, and classifies them into appropriate categories like “fire”,
“accident”, “earthquake”, etc. We demonstrate our ideas by classifying Twitter
posts in real time, visualizing the ongoing event on a map interface and
alerting users with options to contact relevant authorities, both online and
offline. We evaluate our classifiers for both the steps, i.e., emergency
detection and categorization, and obtain F-scores exceeding 70% and 90%,
respectively. We demonstrate Civique using a web interface and on an Android
application, in realtime, and show its use for both tweet detection and
visualization.
Fei Liu, Julien Perez, Scott Nowson
Comments: 10 pages, 2 figures, 2 tables
Subjects: Computation and Language (cs.CL); Machine Learning (stat.ML)
Many methods have been used to recognize author personality traits from text,
typically combining linguistic feature engineering with shallow learning
models, e.g. linear regression or Support Vector Machines. This work uses
deep-learning-based models and atomic features of text, the characters, to
build hierarchical, vectorial word and sentence representations for trait
inference. This method, applied to a corpus of tweets, shows state-of-the-art
performance across five traits and three languages (English, Spanish and
Italian) compared with prior work in author profiling. The results, supported
by preliminary visualisation work, are encouraging for the ability to detect
complex human traits.
Hieu Hoang, Nicolay Bogoychev, Lane Schwartz, Marcin Junczys-Dowmunt
Subjects: Computation and Language (cs.CL)
The utilization of statistical machine translation (SMT) has grown enormously
over the last decade, many using open-source software developed by the NLP
community. As commercial use has increased, there is need for software that is
optimized for commercial requirements, in particular, fast phrase-based
decoding and more efficient utilization of modern multicore servers.
In this paper we re-examine the major components of phrase-based decoding and
decoder implementation with particular emphasis on speed and scalability on
multicore machines. The result is a drop-in replacement for the Moses decoder
which is up to fifteen times faster and scales monotonically with the number of
cores.
Issa Atoum, Ahmed Otoom, Narayanan Kulathuramaiyer
Comments: 7 pages,4 figures
Journal-ref: International Journal of Computer Applications,2016,135(1),
Foundation of Computer Science (FCS), NY, USA
Subjects: Information Retrieval (cs.IR); Computation and Language (cs.CL)
Sentence similarity is considered the basis of many natural language tasks
such as information retrieval, question answering and text summarization. The
semantic meaning between compared text fragments is based on the words semantic
features and their relationships. This article reviews a set of word and
sentence similarity measures and compares them on benchmark datasets. On the
studied datasets, results showed that hybrid semantic measures perform better
than both knowledge and corpus based measures.
Mansaf Alam, Kashish Ara Shakil
Comments: conference paper ICMPAS-2016
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
The Big Data management is a problem right now. The Big Data growth is very
high. It is very difficult to manage due to various characteristics. This
manuscript focuses on Big Data analytics in cloud environment using Hadoop. We
have classified the Big Data according to its characteristics like Volume,
Value, Variety and Velocity. We have made various nodes to process the data
based on their volume, velocity, value and variety. In this work we have
classify the input data and routed to various processing node. At the last
after processing from each node, we can combine the output of all nodes to get
the final result. We have used Hadoop to partition the data as well as process
it.
Shelan Perera, Ashansa Perera, Kamal Hakimzadeh
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Big data processing is a hot topic in today’s computer science world. There
is a significant demand for analysing big data to satisfy many requirements of
many industries. Emergence of the Kappa architecture created a strong
requirement for a highly capable and efficient data processing engine.
Therefore data processing engines such as Apache Flink and Apache Spark emerged
in open source world to fulfil that efficient and high performing data
processing requirement. There are many available benchmarks to evaluate those
two data processing engines. But complex deployment patterns and dependencies
make those benchmarks very difficult to reproduce by our own. This project has
two main goals. They are making few of community accepted benchmarks easily
reproducible on cloud and validate the performance claimed by those studies.
Maicon Melo Alves, Lúcia Maria de Assumpção Drummond
Comments: 14 pages, 6 figures, 6 tables
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
Cross-application interference can affect drastically performance of HPC
applications when running in clouds. This problem is caused by concurrent
access performed by co-located applications to shared and non-sliceable
resources such as cache and memory. In order to address this issue, some works
adopted a qualitative approach that does not take into account the amount of
access to shared resources. In addition, a few works, even considering the
amount of access, evaluated just the SLLC access contention as the root of this
problem. However, our experiments revealed that interference is intrinsically
related to the amount of simultaneous access to shared resources, besides
showing that another shared resources, apart from SLLC, can also influence the
interference suffered by co-located applications. In this paper, we present a
quantitative model for predicting cross-application interference in virtual
environments. Our proposed model takes into account the amount of simultaneous
access to SLLC, DRAM and virtual network, and the similarity of application’s
access burden to predict the level of interference suffered by applications
when co-located in a same physical machine. Experiments considering a real
petroleum reservoir simulator and applications from HPCC benchmark showed that
our model reached an average and maximum prediction errors around 4\% and 12\%,
besides achieving an error less than 10\% in approximately 96\% of all tested
cases.
Shuang Li, Yao Xie, Le Song
Comments: Submitted to conference
Subjects: Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)
We present a novel distribution-free approach, the data-driven threshold
machine (DTM), for a fundamental problem at the core of many learning tasks:
choose a threshold for a given pre-specified level that bounds the tail
probability of the maximum of a (possibly dependent but stationary) random
sequence. We do not assume data distribution, but rather relying on the
asymptotic distribution of extremal values, and reduce the problem to estimate
three parameters of the extreme value distributions and the extremal index. We
specially take care of data dependence via estimating extremal index since in
many settings, such as scan statistics, change-point detection, and extreme
bandits, where dependence in the sequence of statistics can be significant. Key
features of our DTM also include robustness and the computational efficiency,
and it only requires one sample path to form a reliable estimate of the
threshold, in contrast to the Monte Carlo sampling approach which requires
drawing a large number of sample paths. We demonstrate the good performance of
DTM via numerical examples in various dependent settings.
Kwang-Sung Jun, Francesco Orabona, Rebecca Willett, Stephen Wright
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
This paper describes a new parameter-free online learning algorithm for
changing environments. In comparing against algorithms with the same time
complexity as ours, we obtain a strongly adaptive regret bound that is a factor
of at least $sqrt{log(T)}$ better, where $T$ is the time horizon. Empirical
results show that our algorithm outperforms state-of-the-art methods in
learning with expert advice and metric learning scenarios.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, Miguel R. D. Rodrigues
Comments: 9 pages, 3 figures
Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Computer Vision and Pattern Recognition (cs.CV); Learning (cs.LG)
This paper studies the generalization error of invariant classifiers. In
particular, we consider the common scenario where the classification task is
invariant to certain transformations of the input, and that the classifier is
constructed (or learned) to be invariant to these transformations. Our approach
relies on factoring the input space into a product of a base space and a set of
transformations. We show that whereas the generalization error of a
non-invariant classifier is proportional to the complexity of the input space,
the generalization error of an invariant classifier is proportional to the
complexity of the base space. We also derive a set of sufficient conditions on
the geometry of the base space and the set of transformations that ensure that
the complexity of the base space is much smaller than the complexity of the
input space. Our analysis applies to general classifiers such as convolutional
neural networks. We demonstrate the implications of the developed theory for
such classifiers with experiments on the MNIST and CIFAR-10 datasets.
Tor Lattimore, Csaba Szepesvari
Comments: 13 pages
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
Stochastic linear bandits are a natural and simple generalisation of
finite-armed bandits with numerous practical applications. Current approaches
focus on generalising existing techniques for finite-armed bandits, notably the
optimism principle and Thompson sampling. While prior work has mostly been in
the worst-case setting, we analyse the asymptotic instance-dependent regret and
show matching upper and lower bounds on what is achievable. Surprisingly, our
results show that no algorithm based on optimism or Thompson sampling will ever
achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even
in very simple cases. This is a disturbing result because these techniques are
standard tools that are widely used for sequential optimisation. For example,
for generalised linear bandits and reinforcement learning.
Casper Kaae Sønderby, Jose Caballero, Lucas Theis, Wenzhe Shi, Ferenc Huszár
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI); Learning (cs.LG); Machine Learning (stat.ML)
Image Super-resolution (SR) is an underdetermined inverse problem, where a
large number of plausible high-resolution images can explain the same
downsampled image. Most current single image SR methods use empirical risk
minimisation, often with a pixel-wise mean squared error (MSE) loss. However,
the outputs from such methods tend to be blurry, over-smoothed and generally
appear implausible. A more desirable approach would employ Maximum a Posteriori
(MAP) inference, preferring solutions that always have a high probability under
the image prior, and thus appear more plausible. Direct MAP estimation for SR
is non-trivial, as it requires us to build a model for the image prior from
samples. Furthermore, MAP inference is often performed via optimisation-based
iterative algorithms which don’t compare well with the efficiency of
neural-network-based alternatives. Here we introduce new methods for amortised
MAP inference whereby we calculate the MAP estimate directly using a
convolutional neural network. We first introduce a novel neural network
architecture that performs a projection to the affine subspace of valid SR
solutions ensuring that the high resolution output of the network is always
consistent with the low resolution input. We show that, using this
architecture, the amortised MAP inference problem reduces to minimising the
cross-entropy between two distributions, similar to training generative models.
We propose three methods to solve this optimisation problem: (1) Generative
Adversarial Networks (GAN) (2) denoiser-guided SR which backpropagates
gradient-estimates from denoising to train the network, and (3) a baseline
method using a maximum-likelihood-trained image prior. Our experiments show
that the GAN based approach performs best on real image data, achieving
particularly good results in photo-realistic texture SR.
Ievgen Redko, Amaury Habrard, Marc Sebban
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
Domain adaptation (DA) is an important and emerging field of machine learning
that tackles the problem occurring when the distributions of training (source
domain) and test (target domain) data are similar but different. Current
theoretical results show that the efficiency of DA algorithms depends on their
capacity of minimizing the divergence between source and target probability
distributions. In this paper, we provide a theoretical study on the advantages
that concepts borrowed from optimal transportation theory can bring to DA. In
particular, we show that the Wasserstein metric can be used as a divergence
measure between distributions to obtain generalization guarantees for three
different learning settings: (i) classic DA with unsupervised target data (ii)
DA combining source and target labeled data, (iii) multiple source DA. Based on
the obtained results, we provide some insights showing when this analysis can
be tighter than other existing frameworks. We also show that in the context of
multiple source DA, the problem of estimating of the best joint hypothesis
between source and target labeling functions can be reformulated using a
Wasserstein distance-based loss function. We think that these results open the
door to novel ideas and directions for DA.
Ryohei Hisano
Subjects: Machine Learning (stat.ML); Learning (cs.LG); Social and Information Networks (cs.SI); Physics and Society (physics.soc-ph)
We propose a simple discrete time semi-supervised graph embedding approach to
link prediction in dynamic networks. The learned embedding reflects information
from both the temporal and cross-sectional network structures, which is
performed by defining the loss function as a weighted sum of the supervised
loss from past dynamics and the unsupervised loss of predicting the
neighborhood context in the current network. Our model is also capable of
learning different embeddings for both formation and dissolution dynamics.
These key aspects contributes to the predictive performance of our model and we
provide experiments with three real–world dynamic networks showing that our
method is comparable to state of the art methods in link formation prediction
and outperforms state of the art baseline methods in link dissolution
prediction.
Alaa Saade
Comments: PhD dissertation
Subjects: Disordered Systems and Neural Networks (cond-mat.dis-nn); Information Theory (cs.IT); Learning (cs.LG)
In an era of unprecedented deluge of (mostly unstructured) data, graphs are
proving more and more useful, across the sciences, as a flexible abstraction to
capture complex relationships between complex objects. One of the main
challenges arising in the study of such networks is the inference of
macroscopic, large-scale properties affecting a large number of objects, based
solely on the microscopic interactions between their elementary constituents.
Statistical physics, precisely created to recover the macroscopic laws of
thermodynamics from an idealized model of interacting particles, provides
significant insight to tackle such complex networks.
In this dissertation, we use methods derived from the statistical physics of
disordered systems to design and study new algorithms for inference on graphs.
Our focus is on spectral methods, based on certain eigenvectors of carefully
chosen matrices, and sparse graphs, containing only a small amount of
information. We develop an original theory of spectral inference based on a
relaxation of various mean-field free energy optimizations. Our approach is
therefore fully probabilistic, and contrasts with more traditional motivations
based on the optimization of a cost function. We illustrate the efficiency of
our approach on various problems, including community detection, randomized
similarity-based clustering, and matrix completion.
Michael Brand
Comments: 50 pages, 0 figures
Subjects: Machine Learning (stat.ML); Learning (cs.LG); Statistics Theory (math.ST)
Minimum Message Length (MML) is a popular method for statistical inference,
belonging to the Minimum Description Length (MDL) family. It is a general name
for any of several computationally-feasible approximations to the generally
NP-Hard Strict Minimum Message Length (SMML) estimator. One often-cited
showcase for the power of MML is the Neyman-Scott estimation problem, where
most popular estimation algorithms fail to produce a consistent result. MML’s
performance on Neyman-Scott was analysed by Dowe and Wallace (1997) and by
Wallace (2005) and MML was shown to be consistent for the problem. However,
this analysis was not performed on SMML, but rather on two SMML approximations:
Wallace-Freeman and Ideal Group. As for most estimation problems, the exact
SMML solution is not known for Neyman-Scott. We analyse the Dowe-Wallace
solution, and show that it hinges critically on the use of an unnatural prior
for the problem. We argue that the Jeffreys prior is a more natural prior to
assume in this case. Re-analysing the problem over its Jeffreys prior, we show
that both the Ideal Group and the Wallace-Freeman approximations converge to
the (inconsistent) Maximum Likelihood (ML) solution. We develop novel
techniques that enable determining properties of the SMML estimator for some
general families of estimation problems without requiring a full construction
of the estimator, and use these to show that for many problems, including
Neyman-Scott, the SMML estimator is not a point-estimator at all. Rather, it
maps each observation to an entire continuum of estimates. Furthermore, using
the tools developed we show that for Neyman-Scott the SMML estimate is
inconsistent for all parameter sets as well as asymptotically. We discuss
methodological problems in the arguments put forward by previous authors, who
argued that MML is consistent for Neyman-Scott and in general.
Ankur Moitra
Comments: 27 pages, 2 figures
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Learning (cs.LG)
In this paper we introduce a new approach for approximately counting in
bounded degree systems with higher-order constraints. Our main result is an
algorithm to approximately count the number of solutions to a CNF formula
$Phi$ with at least $k$ variables per clause and degree at most $d$ when $k$
is logarithmic in $d$. This closes an exponential gap between the known upper
and lower bounds.
Moreover our algorithm extends straightforwardly to approximate sampling,
which shows that under Lovasz Local Lemma-like conditions it is not only
possible to find a satisfying assignment, it is also possible to generate one
approximately uniformly at random from the set of all satisfying assignments.
Our approach is a significant departure from earlier techniques in approximate
counting, and is based on a framework to bootstrap an oracle for computing
marginal probabilities on individual variables. Finally, we give an application
of our results to show that it is algorithmically possible to sample from the
posterior distribution in an interesting class of graphical models.
Andrei A. Rusu, Matej Vecerik, Thomas Rothörl, Nicolas Heess, Razvan Pascanu, Raia Hadsell
Subjects: Robotics (cs.RO); Learning (cs.LG)
Applying end-to-end learning to solve complex, interactive, pixel-driven
control tasks on a robot is an unsolved problem. Deep Reinforcement Learning
algorithms are too slow to achieve performance on a real robot, but their
potential has been demonstrated in simulated environments. We propose using
progressive networks to bridge the reality gap and transfer learned policies
from simulation to the real world. The progressive net approach is a general
framework that enables reuse of everything from low-level visual features to
high-level policies for transfer to new tasks, enabling a compositional, yet
simple, approach to building complex skills. We present an early demonstration
of this approach with a number of experiments in the domain of robot
manipulation that focus on bridging the reality gap. Unlike other proposed
approaches, our real-world experiments demonstrate successful task learning
from raw visual input on a fully actuated robot manipulator. Moreover, rather
than relying on model-based trajectory optimisation, the task learning is
accomplished using only deep reinforcement learning and sparse rewards.
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Comments: 35 pages, 11 figures
Subjects: Information Theory (cs.IT); Computer Vision and Pattern Recognition (cs.CV); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC); Machine Learning (stat.ML)
Various alignment problems arising in cryo-electron microscopy, community
detection, time synchronization, computer vision, and other fields fall into a
common framework of synchronization problems over compact groups such as Z/L,
U(1), or SO(3). The goal of such problems is to estimate an unknown vector of
group elements given noisy relative observations. We present an efficient
iterative algorithm to solve a large class of these problems, allowing for any
compact group, with measurements on multiple ‘frequency channels’ (Fourier
modes, or more generally, irreducible representations of the group). Our
algorithm is a highly efficient iterative method following the blueprint of
approximate message passing (AMP), which has recently arisen as a central
technique for inference problems such as structured low-rank estimation and
compressed sensing. We augment the standard ideas of AMP with ideas from
representation theory so that the algorithm can work with distributions over
compact groups. Using standard but non-rigorous methods from statistical
physics we analyze the behavior of our algorithm on a Gaussian noise model,
identifying phases where the problem is easy, (computationally) hard, and
(statistically) impossible. In particular, such evidence predicts that our
algorithm is information-theoretically optimal in many cases, and that the
remaining cases show evidence of statistical-to-computational gaps.
Qiwen Wang, Mikael Skoglund
Subjects: Information Theory (cs.IT); Cryptography and Security (cs.CR); Information Retrieval (cs.IR)
A user wants to retrieve a file from a database without revealing the
identity of the file retrieved at the database, which is known as the problem
of private information retrieval (PIR). If it is further required that the user
obtains no information about the database other than the desired file, the
concept of symmetric private information retrieval (SPIR) is introduced to
guarantee privacy for both parties. In this paper, the problem of SPIR is
studied for a database stored among $N$ nodes in a distributed way, by using an
$(N,M)$-MDS storage code. The information-theoretic capacity of SPIR, defined
as the maximum number of symbols of the desired file retrieved per downloaded
symbol, for the coded database is derived. It is shown that the SPIR capacity
for coded database is $1-frac{M}{N}$, when the amount of the shared common
randomness of distributed nodes (unavailable at the user) is at least
$frac{M}{N-M}$ times the file size. Otherwise, the SPIR capacity for the coded
database equals zero.
Jy-yong Sohn, Beongjun Choi, Sung Whan Yoon, Jaekyun Moon
Comments: 7 pages, submitted to IEEE ICC 2017
Subjects: Information Theory (cs.IT)
A new system model reflecting the clustered structure of distributed storage
is suggested to investigate bandwidth requirements for repairing failed storage
nodes. Large data centers with multiple racks/disks or local networks of
storage devices (e.g. sensor network) are good applications of the suggested
clustered model. In realistic scenarios involving clustered storage structures,
repairing storage nodes using intact nodes residing in other clusters is more
bandwidth-consuming than restoring nodes based on information from
intra-cluster nodes. Therefore, it is important to differentiate between
intra-cluster repair bandwidth and cross-cluster repair bandwidth in modeling
distributed storage. Capacity of the suggested model is obtained as a function
of fundamental resources of distributed storage systems, namely, storage
capacity, intra-cluster repair bandwidth and cross-cluster repair bandwidth.
Based on the capacity expression, feasible sets of required resources which
enable reliable storage are analyzed. It is shown that the cross-cluster
traffic can be minimized to zero (i.e., intra-cluster local repair becomes
possible) by allowing extra resources on storage capacity and intra-cluster
repair bandwidth, according to a law specified in a closed-form. Moreover,
trade-off between cross-cluster traffic and intra-cluster traffic is observed
for sufficiently large storage capacity.
Marco Compagnoni, Alessia Pini, Antonio Canclini, Paolo Bestagini, Fabio Antonacci, Stefano Tubaro, Augusto Sarti
Comments: 26 pages, 10 figure, 2 tables
Subjects: Information Theory (cs.IT); Sound (cs.SD); Methodology (stat.ME)
The curse of outlier measurements in estimation problems is a well known
issue in a variety of fields. Therefore, outlier removal procedures, which
enables the identification of spurious measurements within a set, have been
developed for many different scenarios and applications. In this paper, we
propose a statistically motivated outlier removal algorithm for time
differences of arrival (TDOAs), or equivalently range differences (RD),
acquired at sensor arrays. The method exploits the TDOA-space formalism and
works by only knowing the relative sensor positions. As the proposed method is
completely independent from the application for which measurements are used, it
can be reliably used to identify outliers within a set of TDOA/RD measurements
in different fields (e.g. acoustic source localization, sensor synchronization,
radar, remote sensing, etc.). The whole theoretical derivation is validated by
means of synthetic simulations and real experiments.
Nian Li
Subjects: Information Theory (cs.IT)
Permutation polynomials with few terms attracts researchers’ interest in
recent years due to their simple algebraic form and some additional
extraordinary properties. In this paper, by analyzing the quadratic factors of
a fifth-degree polynomial and a seventh-degree polynomial over the finite field
$mathbb{F}_{3^{2k}}$, two conjectures on permutation trinomials over
$mathbb{F}_{3^{2k}}$ proposed recently by Li, Qu, Li and Fu are settled, where
$k$ is a positive integer.
Meesue Shin, Laura Toni, Sang-Hyo Kim, Seok-Ho Chang
Comments: 31 pages, 6 figures (15 subfigures), Submitted to IEEE Transactions on Image Processing
Subjects: Information Theory (cs.IT)
The optimization of joint source and channel coding for a sequence of
numerous progressive packets is a challenging problem. Further, the problem
becomes more complicated if the space-time coding is also involved with the
optimization in a multiple-input multiple-output (MIMO) system. This is because
the number of ways of jointly assigning channels codes and space-time codes to
progressive packets is much larger than that of solely assigning channel codes
to the packets. We are unaware of any feasible and complete solution for such
optimization of joint source, channel, and space-time coding of progressive
packets. This paper applies a parametric approach to address that complex joint
optimization problem in a MIMO system. We use the parametric methodology to
derive some useful theoretical results, and then exploit those results to
propose an optimization method where the joint assignment of channel codes and
space-time codes to the packets can be optimized in a packet-by-packet manner.
As a result, the computational complexity of the optimization is exponentially
reduced, compared to the conventional exhaustive search. The numerical results
show that the proposed method significantly improves the peak-signal-to-noise
ratio performance of the rate-based optimal solution in a MIMO system.
Jesper H. Sørensen, Petar Popovski, Jan Østergaard
Subjects: Information Theory (cs.IT)
We present a closed-form expression for the minimal delay that is achievable
in a setting that combines a buffer and an erasure code, used to mitigate the
packet delay variance. The erasure code is modeled according to the recent
information-theoretic results on finite block length codes. Evaluations reveal
that accurate knowledge of the network parameters is essential for optimal
operation. Moreover, it is shown that, when the network packet delay variance
is large, the buffer delay becomes negligible. Therefore, in this case the
delay budget should be spent mainly on the erasure code.
Hirofumi Tsuda, Ken Umeno
Comments: 7 pages IEEE ICC
Subjects: Information Theory (cs.IT)
Signal to Noise Ratio (SNR) is an important index for wireless
communications. There are many methods for increasing SNR. In CDMA systems,
spreading sequences are used. We consider the frequency-selective
wide-sense-stationary uncorrelated-scattering (WSSUS) channel and evaluate the
worst case of SNR. We construct the non-linear programing for maximizing the
lower bound of the average of SNR. This problem becomes the convex programming
if we did not take into account the norm constraint. We derive necessary
conditions for optimal spreading sequences for the problem.
Mario Blaum, Steve Hetzler
Comments: 37 pages
Subjects: Information Theory (cs.IT)
Generalized Product (GPC) Codes, an unification of Product Codes and
Integrated Interleaved (II) Codes, are presented. Applications for approaches
requiring local and global parities are described. The more general problem of
extending product codes by adding global parities is studied and an upper bound
on the minimum distance of such codes is obtained. Codes with one, two and
three global parities whose minimum distances meet the bound are presented.
Tradeoffs between optimality and field size are discussed.
Jorge Useche, Rafael Hurtado
Comments: 15 pages, 12 figures, 4 tables
Subjects: Sound (cs.SD); Information Theory (cs.IT); Data Analysis, Statistics and Probability (physics.data-an); Physics and Society (physics.soc-ph)
Consonance is related to the perception of pleasantness arising from the
combination of sounds and has been approached quantitatively using mathematical
relations, physics, information theory and psychoacoustics. Tonal consonance is
present in timbre, musical tuning, harmony and melody, and it is used for
conveying sensations and emotions in music. It involves the physical properties
of sound waves and is used to study melody and harmony through musical
intervals and chords. From the perspective of complexity, the macroscopic
properties of a system with many parts frequently rely on statistical
properties of its constituent elements. Here we show that melody in musical
pieces can be described in terms of the physical properties of melodic
intervals and the existence of an entropy extremalization principle in music
with psychoacoustic macroscopic constraints given by conserved quantities with
musical meaning. This result connects human perception with human creativity
through the physical properties of the musical stimulus.
Mahdi Jafari Siavoshani, Seyed Pooya Shariatpanahi, Hamid Ghasemi, Ali Pourmiri
Comments: 6 pages, 7 figures, submitted to conference
Subjects: Networking and Internet Architecture (cs.NI); Information Theory (cs.IT)
It is well known that load balancing and low delivery communication cost are
two critical issues in mapping requests to servers in Content Delivery Networks
(CDNs). However, the trade-off between these two performance metrics has not
been yet quantitatively investigated in designing efficient request mapping
schemes. In this work, we formalize this trade-off through a stochastic
optimization problem. While the solutions to the problem in the extreme cases
of minimum communication cost and optimum load balancing can be derived in
closed form, finding the general solution is hard to derive. Thus we propose
three heuristic mapping schemes and compare the trade-off performance of them
through extensive simulations.
Our simulation results show that at the expense of high query cost, we can
achieve a good trade-off curve. Moreover, by benefiting from the power of
multiple choices phenomenon, we can achieve almost the same performance with
much less query cost. Finally, we can handle requests with different delay
requirements at the cost of degrading network performance.
Alaa Saade
Comments: PhD dissertation
Subjects: Disordered Systems and Neural Networks (cond-mat.dis-nn); Information Theory (cs.IT); Learning (cs.LG)
In an era of unprecedented deluge of (mostly unstructured) data, graphs are
proving more and more useful, across the sciences, as a flexible abstraction to
capture complex relationships between complex objects. One of the main
challenges arising in the study of such networks is the inference of
macroscopic, large-scale properties affecting a large number of objects, based
solely on the microscopic interactions between their elementary constituents.
Statistical physics, precisely created to recover the macroscopic laws of
thermodynamics from an idealized model of interacting particles, provides
significant insight to tackle such complex networks.
In this dissertation, we use methods derived from the statistical physics of
disordered systems to design and study new algorithms for inference on graphs.
Our focus is on spectral methods, based on certain eigenvectors of carefully
chosen matrices, and sparse graphs, containing only a small amount of
information. We develop an original theory of spectral inference based on a
relaxation of various mean-field free energy optimizations. Our approach is
therefore fully probabilistic, and contrasts with more traditional motivations
based on the optimization of a cost function. We illustrate the efficiency of
our approach on various problems, including community detection, randomized
similarity-based clustering, and matrix completion.
Marco Compagnoni, Antonio Canclini, Paolo Bestagini, Fabio Antonacci, Augusto Sarti, Stefano Tubaro
Comments: 25 pages, 9 figures
Journal-ref: Multidimensional Systems and Signal Processing 2016
Subjects: Sound (cs.SD); Information Theory (cs.IT); Methodology (stat.ME)
In this manuscript, we formulate the problem of denoising Time Differences of
Arrival (TDOAs) in the TDOA space, i.e. the Euclidean space spanned by TDOA
measurements. The method consists of pre-processing the TDOAs with the purpose
of reducing the measurement noise. The complete set of TDOAs (i.e., TDOAs
computed at all microphone pairs) is known to form a redundant set, which lies
on a linear subspace in the TDOA space. Noise, however, prevents TDOAs from
lying exactly on this subspace. We therefore show that TDOA denoising can be
seen as a projection operation that suppresses the component of the noise that
is orthogonal to that linear subspace. We then generalize the projection
operator also to the cases where the set of TDOAs is incomplete. We
analytically show that this operator improves the localization accuracy, and we
further confirm that via simulation.