Alon Hazan, Yuval Harel, Ron Meir
Journal-ref: IEEE International Conference on the Science of Electrical
Engineering (ICSEE) (2016)
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
The Human visual perception of the world is of a large fixed image that is
highly detailed and sharp. However, receptor density in the retina is not
uniform: a small central region called the fovea is very dense and exhibits
high resolution, whereas a peripheral region around it has much lower spatial
resolution. Thus, contrary to our perception, we are only able to observe a
very small region around the line of sight with high resolution. The perception
of a complete and stable view is aided by an attention mechanism that directs
the eyes to the numerous points of interest within the scene. The eyes move
between these targets in quick, unconscious movements, known as “saccades”.
Once a target is centered at the fovea, the eyes fixate for a fraction of a
second while the visual system extracts the necessary information. An
artificial visual system was built based on a fully recurrent neural network
set within a reinforcement learning protocol, and learned to attend to regions
of interest while solving a classification task. The model is consistent with
several experimentally observed phenomena, and suggests novel predictions.
Christian Reul, Uwe Springmann, Frank Puppe
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
A semi-automatic open-source tool for layout analysis on early printed books
is presented. LAREX uses a rule based connected components approach which is
very fast, easily comprehensible for the user and allows an intuitive manual
correction if necessary. The PageXML format is used to support integration into
existing OCR workflows. Evaluations showed that LAREX provides an efficient and
flexible way to segment pages of early printed books.
Christian Reul, Marco Dittrich, Martin Gruner
Subjects: Computer Vision and Pattern Recognition (cs.CV)
This paper provides the first thorough documentation of a high quality
digitization process applied to an early printed book from the incunabulum
period (1450-1500). The entire OCR related workflow including preprocessing,
layout analysis and text recognition is illustrated in detail using the example
of ‘Der Heiligen Leben’, printed in Nuremberg in 1488. For each step the
required time expenditure was recorded. The character recognition yielded
excellent results both on character (97.57%) and word (92.19%) level.
Furthermore, a comparison of a highly automated (LAREX) and a manual (Aletheia)
method for layout analysis was performed. By considerably automating the
segmentation the required human effort was reduced significantly from over 100
hours to less than six hours, resulting in only a slight drop in OCR accuracy.
Realistic estimates for the human effort necessary for full text extraction
from incunabula can be derived from this study. The printed pages of the
complete work together with the OCR result is available online ready to be
inspected and downloaded.
Shuai Du, Youyi Zheng
Comments: 10 pages
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Acquiring 3D geometry of real world objects has various applications in 3D
digitization, such as navigation and content generation in virtual
environments. Image remains one of the most popular media for such visual tasks
due to its simplicity of acquisition. Traditional image-based 3D reconstruction
approaches heavily exploit point-to-point correspondence among multiple images
to estimate camera motion and 3D geometry. Establishing point-to-point
correspondence lies at the center of the 3D reconstruction pipeline, which
however is easily prone to errors. In this paper, we propose an optimization
framework which traces image points using a novel structure-guided dynamic
tracking algorithm and estimates both the camera motion and a 3D structure
model by enforcing a set of planar constraints. The key to our method is a
structure model represented as a set of planes and their arrangements.
Constraints derived from the structure model is used both in the correspondence
establishment stage and the bundle adjustment stage in our reconstruction
pipeline. Experiments show that our algorithm can effectively localize
structure correspondence across dense image frames while faithfully
reconstructing the camera motion and the underlying structured 3D model.
Abdolrahim Kadkhodamohammadi, Afshin Gangi, Michel de Mathelin, Nicolas Padoy
Comments: WACV 2017. Supplementary material video: this https URL
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Many approaches have been proposed for human pose estimation in single and
multi-view RGB images. However, some environments, such as the operating room,
are still very challenging for state-of-the-art RGB methods. In this paper, we
propose an approach for multi-view 3D human pose estimation from RGB-D images
and demonstrate the benefits of using the additional depth channel for pose
refinement beyond its use for the generation of improved features. The proposed
method permits the joint detection and estimation of the poses without knowing
a priori the number of persons present in the scene. We evaluate this approach
on a novel multi-view RGB-D dataset acquired during live surgeries and
annotated with ground truth 3D poses.
Zhenzhong Lan, Yi Zhu, Alexander G. Hauptmann
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We investigate the problem of representing an entire video using CNN features
for human action recognition. Currently, limited by GPU memory, we have not
been able to feed a whole video into CNN/RNNs for end-to-end learning. A common
practice is to use sampled frames as inputs and video labels as supervision.
One major problem of this popular approach is that the local samples may not
contain the information indicated by global labels. To deal with this problem,
we propose to treat the deep networks trained on local inputs as local feature
extractors. After extracting local features, we aggregate them into global
features and train another mapping function on the same training data to map
the global features into global labels. We study a set of problems regarding
this new type of local features such as how to aggregate them into global
features. Experimental results on HMDB51 and UCF101 datasets show that, for
these new local features, a simple maximum pooling on the sparsely sampled
features lead to significant performance improvement.
David Villacis, Santeri Kaupinmäki, Samuli Siltanen, Teemu Helenius
Comments: 9 pages, 12 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV); Data Analysis, Statistics and Probability (physics.data-an)
This is a photographic dataset collected for testing image processing
algorithms. The idea is to have images that can exploit the properties of total
variation, therefore a set of playing cards was distributed on the scene. The
dataset is made available at www.fips.fi/photographic_dataset2.php
Hakan Bilen, Andrea Vedaldi
Comments: 10 pages, 4 figures, 5 tables
Subjects: Computer Vision and Pattern Recognition (cs.CV); Machine Learning (stat.ML)
With the advent of large labelled datasets and high-capacity models, the
performance of machine vision systems has been improving rapidly. However, the
technology has still major limitations, starting from the fact that different
vision problems are still solved by different models, trained from scratch or
fine-tuned on the target data. The human visual system, in stark contrast,
learns a universal representation for vision in the early life of an
individual. This representation works well for an enormous variety of vision
problems, with little or no change, with the major advantage of requiring
little training data to solve any of them.
Yuanyi Zhong, Jiansheng Chen, Bo Huang
Comments: 9 pages, 8 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Plenty of effective methods have been proposed for face recognition during
the past decade. Although these methods differ essentially in many aspects, a
common practice of them is to specifically align the facial area based on the
prior knowledge of human face structure before feature extraction. In most
systems, the face alignment module is implemented independently. This has
actually caused difficulties in the designing and training of end-to-end face
recognition models. In this paper we study the possibility of alignment
learning in end-to-end face recognition, in which neither prior knowledge on
facial landmarks nor artificially defined geometric transformations are
required. Specifically, spatial transformer layers are inserted in front of the
feature extraction layers in a Convolutional Neural Network (CNN) for face
recognition. Only human identity clues are used for driving the neural network
to automatically learn the most suitable geometric transformation and the most
appropriate facial area for the recognition task. To ensure reproducibility,
our model is trained purely on the publicly available CASIA-WebFace dataset,
and is tested on the Labeled Face in the Wild (LFW) dataset. We have achieved a
verification accuracy of 99.08\% which is comparable to state-of-the-art single
model based methods.
Byunghwee Lee, Daniel Kim, Hawoong Jeong, Seunghye Sun, Juyong Park
Comments: 11 pages, 9 figures
Subjects: Computer Vision and Pattern Recognition (cs.CV); Physics and Society (physics.soc-ph)
Painting is an art form that has long functioned as major channel for
communication and creative expression. Understanding how painting has evolved
over the centuries is therefore an essential component for understanding
cultural history, intricately linked with developments in aesthetics, science,
and technology. The explosive growth in the ranges of stylistic diversity in
painting starting in the nineteenth century, for example, is understood to be
the hallmark of a stark departure from traditional norms on multidisciplinary
fronts. Yet, there exist few quantitative frameworks that allow us to
characterize such developments on an extensive scale, which would require both
robust statistical methods for quantifying the complexities of artistic styles
and data of sufficient quality and quantity to which we can fruitfully apply
them. Here we propose an analytical framework that allows us to capture the
stylistic evolution of paintings based on the color contrast relationships that
also incorporates the geometric separation between pixels of images in a
large-scale archive of 179,853 images. We first measure how paintings have
evolved over time, and then characterize the remarkable explosive growth in
diversity and individuality in the modern era. Our analysis demonstrates how
robust scientific methods married with large-scale, high-quality data can
reveal interesting patterns that lie behind the complexities of art and
culture.
Tong Shen, Guosheng Lin, Chunhua Shen, Ian Reid
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Semantic image segmentation is a fundamental task in image understanding.
Per-pixel semantic labelling of an image benefits greatly from the ability to
consider region consistency both locally and globally. However, many Fully
Convolutional Network based methods do not impose such consistency, which may
give rise to noisy and implausible predictions. We address this issue by
proposing a dense multi-label network module that is able to encourage the
region consistency at different levels. This simple but effective module can be
easily integrated into any semantic segmentation systems. With comprehensive
experiments, we show that the dense multi-label can successfully remove the
implausible labels and clear the confusion so as to boost the performance of
semantic segmentation systems.
Siddharth Srivastava, Gaurav Sharma, Brejesh Lall
Subjects: Computer Vision and Pattern Recognition (cs.CV)
We present a method for discovering objects in 3D point clouds from sensors
like Microsoft Kinect. We utilize supervoxels generated directly from the point
cloud data and design a Siamese network building on a recently proposed 3D
convolutional neural network architecture. At training, we assume the
availability of the some known objects—these are used to train a non-linear
embedding of supervoxels using the Siamese network, by optimizing the criteria
that supervoxels which fall on the same object should be closer than those
which fall on different objects, in the embedding space. We do not assume the
objects during test to be known, and perform clustering, in the embedding space
learned, of supervoxels to effectively perform novel object discovery. We
validate the method with quantitative results showing that it can discover
numerous unseen objects while being trained on only a few dense 3D models. We
also show convincing qualitative results of object discovery in point cloud
data when the test objects, either specific instances or even their categories,
were never seen during training.
Johan Thunberg, Florian Bernard, Jorge Goncalves
Comments: 18 pages, 2 figures
Subjects: Optimization and Control (math.OC); Computer Vision and Pattern Recognition (cs.CV); Distributed, Parallel, and Cluster Computing (cs.DC); Multiagent Systems (cs.MA)
This paper addresses the problem of synchronizing orthogonal matrices over
directed graphs. For synchronized transformations (or matrices), composite
transformations over loops equal the identity. We formulate the synchronization
problem as a least-squares optimization problem with nonlinear constraints. The
synchronization problem appears as one of the key components in applications
ranging from 3D-localization to image registration. The main contributions of
this work can be summarized as the introduction of two novel algorithms; one
for symmetric graphs and one for graphs that are possibly asymmetric. Under
general conditions, the former has guaranteed convergence to the solution of a
spectral relaxation to the synchronization problem. The latter is stable for
small step sizes when the graph is quasi-strongly connected. The proposed
methods are verified in numerical simulations.
Jae Kyu Choi, Bin Dong, Xiaoqun Zhang
Subjects: Numerical Analysis (math.NA); Computer Vision and Pattern Recognition (cs.CV); Functional Analysis (math.FA)
Wavelet frame systems are known to be effective in capturing singularities
from noisy and degraded images. In this paper, we introduce a new edge driven
wavelet frame model for image restoration by approximating images as piecewise
smooth functions. With an implicit representation of image singularities sets,
the proposed model inflicts different strength of regularization on smooth and
singular image regions and edges. The proposed edge driven model is robust to
both image approximation and singularity estimation. The implicit formulation
also enables an asymptotic analysis of the proposed models and a rigorous
connection between the discrete model and a general continuous variational
model. Finally, numerical results on image inpainting and deblurring show that
the proposed model is compared favorably against several popular image
restoration models.
Patrice Godefroid, Hila Peleg, Rishabh Singh
Subjects: Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR); Learning (cs.LG); Programming Languages (cs.PL); Software Engineering (cs.SE)
Fuzzing consists of repeatedly testing an application with modified, or
fuzzed, inputs with the goal of finding security vulnerabilities in
input-parsing code. In this paper, we show how to automate the generation of an
input grammar suitable for input fuzzing using sample inputs and
neural-network-based statistical machine-learning techniques. We present a
detailed case study with a complex input format, namely PDF, and a large
complex security-critical parser for this format, namely, the PDF parser
embedded in Microsoft’s new Edge browser. We discuss (and measure) the tension
between conflicting learning and fuzzing goals: learning wants to capture the
structure of well-formed inputs, while fuzzing wants to break that structure in
order to cover unexpected code paths and find bugs. We also present a new
algorithm for this learn&fuzz challenge which uses a learnt input probability
distribution to intelligently guide where to fuzz inputs.
Amir Husain (1), Bruce Porter (2) ((1) SparkCognition Inc. (2) Department of Computer Science, University of Texas at Austin)
Comments: 12 pages, 3 figures, 1 table
Subjects: Artificial Intelligence (cs.AI); Robotics (cs.RO)
This paper covers a number of approaches that leverage Artificial
Intelligence algorithms and techniques to aid Unmanned Combat Aerial Vehicle
(UCAV) autonomy. An analysis of current approaches to autonomous control is
provided followed by an exploration of how these techniques can be extended and
enriched with AI techniques including Artificial Neural Networks (ANN),
Ensembling and Reinforcement Learning (RL) to evolve control strategies for
UCAVs.
Alon Hazan, Yuval Harel, Ron Meir
Journal-ref: IEEE International Conference on the Science of Electrical
Engineering (ICSEE) (2016)
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
The Human visual perception of the world is of a large fixed image that is
highly detailed and sharp. However, receptor density in the retina is not
uniform: a small central region called the fovea is very dense and exhibits
high resolution, whereas a peripheral region around it has much lower spatial
resolution. Thus, contrary to our perception, we are only able to observe a
very small region around the line of sight with high resolution. The perception
of a complete and stable view is aided by an attention mechanism that directs
the eyes to the numerous points of interest within the scene. The eyes move
between these targets in quick, unconscious movements, known as “saccades”.
Once a target is centered at the fovea, the eyes fixate for a fraction of a
second while the visual system extracts the necessary information. An
artificial visual system was built based on a fully recurrent neural network
set within a reinforcement learning protocol, and learned to attend to regions
of interest while solving a classification task. The model is consistent with
several experimentally observed phenomena, and suggests novel predictions.
Christian Reul, Uwe Springmann, Frank Puppe
Subjects: Computer Vision and Pattern Recognition (cs.CV); Artificial Intelligence (cs.AI)
A semi-automatic open-source tool for layout analysis on early printed books
is presented. LAREX uses a rule based connected components approach which is
very fast, easily comprehensible for the user and allows an intuitive manual
correction if necessary. The PageXML format is used to support integration into
existing OCR workflows. Evaluations showed that LAREX provides an efficient and
flexible way to segment pages of early printed books.
Maged M. Eljazzar, Mostafa Abdulhamid, Mahmoud Mouneer, Ayman Salama
Comments: 6 pages
Subjects: Computers and Society (cs.CY); Artificial Intelligence (cs.AI)
Internet users are more likely to ignore Internet content verification and
more likely to share the content. When it comes to Islamic content, it is
crucial to share and spread fake or inaccurate content. Even if the
verification process of Islamic content is becoming easier every day, the
Internet users generally ignore the verification step and jump into sharing the
content. How many clicks away from users results? , this is the common question
that is considered as a rule in modern website design. Internet users prefer
the results to come to their page rather than to navigate it on their own. This
paper presents a simple method of bringing hadith verification to the user web
browser using web browser plugin.
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen
Subjects: Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Learning (cs.LG)
The (k)-Means clustering problem on (n) points is NP-Hard for any dimension
(dge 2), however, for the 1D case there exist exact polynomial time
algorithms. The current state of the art is a (O(kn^2)) dynamic programming
algorithm that uses (O(nk)) space. We present a new algorithm improving this to
(O(kn log n)) time and optimal (O(n)) space. We generalize our algorithm to
work for the absolute distance instead of squared distance and to work for any
Bregman Divergence as well.
Guillermo Vigueras (IMDEA Software Institute), Manuel Carro (IMDEA Software Institute and Universidad Politécnica de Madrid), Salvador Tamarit (Universidad Politécnica de Madrid), Julio Mariño (Universidad Politécnica de Madrid)
Comments: In Proceedings PROLE 2016, arXiv:1701.03069. This paper is based on arXiv:1603.03022, and has a thorough description of the proposed approach
Journal-ref: EPTCS 237, 2017, pp. 52-67
Subjects: Programming Languages (cs.PL); Artificial Intelligence (cs.AI)
The current trends in next-generation exascale systems go towards integrating
a wide range of specialized (co-)processors into traditional supercomputers.
Due to the efficiency of heterogeneous systems in terms of Watts and FLOPS per
surface unit, opening the access of heterogeneous platforms to a wider range of
users is an important problem to be tackled. However, heterogeneous platforms
limit the portability of the applications and increase development complexity
due to the programming skills required. Program transformation can help make
programming heterogeneous systems easier by defining a step-wise transformation
process that translates a given initial code into a semantically equivalent
final code, but adapted to a specific platform. Program transformation systems
require the definition of efficient transformation strategies to tackle the
combinatorial problem that emerges due to the large set of transformations
applicable at each step of the process. In this paper we propose a machine
learning-based approach to learn heuristics to define program transformation
strategies. Our approach proposes a novel combination of reinforcement learning
and classification methods to efficiently tackle the problems inherent to this
type of systems. Preliminary results demonstrate the suitability of this
approach.
Tim Althoff, Eric Horvitz, Ryen W. White, Jamie Zeitzer
Comments: Published in Proceedings of WWW 2017
Subjects: Human-Computer Interaction (cs.HC); Computers and Society (cs.CY); Information Retrieval (cs.IR); Neurons and Cognition (q-bio.NC)
Human cognitive performance is critical to productivity, learning, and
accident avoidance. Cognitive performance varies throughout each day and is in
part driven by intrinsic, near 24-hour circadian rhythms. Prior research on the
impact of sleep and circadian rhythms on cognitive performance has typically
been restricted to small-scale laboratory-based studies that do not capture the
variability of real-world conditions, such as environmental factors,
motivation, and sleep patterns in real-world settings. Given these limitations,
leading sleep researchers have called for larger in situ monitoring of sleep
and performance. We present the largest study to date on the impact of
objectively measured real-world sleep on performance enabled through a
reframing of everyday interactions with a web search engine as a series of
performance tasks. Our analysis includes 3 million nights of sleep and 75
million interaction tasks. We measure cognitive performance through the speed
of keystroke and click interactions on a web search engine and correlate them
to wearable device-defined sleep measures over time. We demonstrate that
real-world performance varies throughout the day and is influenced by both
circadian rhythms, chronotype (morning/evening preference), and prior sleep
duration and timing. We develop a statistical model that operationalizes a
large body of work on sleep and performance and demonstrates that our estimates
of circadian rhythms, homeostatic sleep drive, and sleep inertia align with
expectations from laboratory-based sleep studies. Further, we quantify the
impact of insufficient sleep on real-world performance and show that two
consecutive nights with less than six hours of sleep are associated with
decreases in performance which last for a period of six days. This work
demonstrates the feasibility of using online interactions for large-scale
physiological sensing.
Panagiotis Papadopoulos, Nicolas Kourtellis, Pablo Rodriguez Rodriguez, Nikolaos Laoutaris
Subjects: Computer Science and Game Theory (cs.GT); Computers and Society (cs.CY); Information Retrieval (cs.IR)
Online advertising is progressively moving towards a targeted model of
programmatic ad buying in which advertisers bid for ad-slots on a
per-impression basis. This model runs over the Real Time Bidding (RTB) protocol
and is driven by the information provided by a large ecosystem of data
collection companies that track users online. Concern about online tracking has
spurred a huge public debate around data protection, as well as intense
innovation around personal information management systems, markets, and
business models. Core to all the above is being able to know the value of
users’ personal information.
In this study, we develop a first of its kind methodology for computing
exactly that – the value of a single user for the programmatic ad buying
ecosystem. Our goal is to increase user awareness for the value of their data
as well as to inspire new online economies where users give access to their
data in exchange for discounted services. Our approach is based on tapping on
the RTB protocol to collect cleartext and encrypted prices for winning bids. To
estimate the value of the latter, we train a machine learning model using as
ground truth prices obtained by running our own “probe” ad-campaigns. We
validate our methodology using a one year long trace of mobile user browsing
data as well as two real world mobile ad-campaigns.
Chen Xing, Wei Wu, Yu Wu, Ming Zhou, Yalou Huang, Wei-Ying Ma
Subjects: Computation and Language (cs.CL)
We study multi-turn response generation in chatbots where a response is
generated according to a conversation context. Existing work has modeled the
hierarchy of the context, but does not pay enough attention to the fact that
words and utterances in the context are differentially important. As a result,
they may lose important information in context and generate irrelevant
responses. We propose a hierarchical recurrent attention network (HRAN) to
model both aspects in a unified framework. In HRAN, a hierarchical attention
mechanism attends to important parts within and among utterances with word
level attention and utterance level attention respectively. With the word level
attention, hidden vectors of a word level encoder are synthesized as utterance
vectors and fed to an utterance level encoder to construct hidden
representations of the context. The hidden vectors of the context are then
processed by the utterance level attention and formed as context vectors for
decoding the response. Empirical studies on both automatic evaluation and human
judgment show that HRAN can significantly outperform state-of-the-art models
for multi-turn response generation.
Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Jan Manuch, Lata Narayanan, Jaroslav Opatrny, Ladislav Stacho
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Optimization and Control (math.OC)
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner
in a rectangular region. They are required to move to final locations so that
they can detect any intruder crossing the region in a direction parallel to the
sides of the rectangle, and thus provide weak barrier coverage of the region.
We study three optimization problems related to the movement of sensors to
achieve weak barrier coverage: minimizing the number of sensors moved (MinNum),
minimizing the average distance moved by the sensors (MinSum), and minimizing
the maximum distance moved by the sensors (MinMax). We give an O(n^{3/2}) time
algorithm for the MinNum problem for sensors of diameter 1 that are initially
placed at integer positions; in contrast we show that the problem is NP-hard
even for sensors of diameter 2 that are initially placed at integer positions.
We show that the MinSum problem is solvable in O(n log n) time for homogeneous
range sensors in arbitrary initial positions, while it is NP-hard for
heterogeneous sensor ranges. Finally, we prove that even very restricted
homogeneous versions of the MinMax problem are NP-hard.
Shaowei Wang, Liusheng Huang, Pengzhan Wang, Hongli Xu, Wei Yang
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Human-Computer Interaction (cs.HC); Learning (cs.LG)
Ensemble learning has been widely employed by mobile applications, ranging
from environmental sensing to activity recognitions. One of the fundamental
issue in ensemble learning is the trade-off between classification accuracy and
computational costs, which is the goal of ensemble pruning. During
crowdsourcing, the centralized aggregator releases ensemble learning models to
a large number of mobile participants for task evaluation or as the
crowdsourcing learning results, while different participants may seek for
different levels of the accuracy-cost trade-off. However, most of existing
ensemble pruning approaches consider only one identical level of such
trade-off. In this study, we present an efficient ensemble pruning framework
for personalized accuracy-cost trade-offs via multi-objective optimization.
Specifically, for the commonly used linear-combination style of the trade-off,
we provide an objective-mixture optimization to further reduce the number of
ensemble candidates. Experimental results show that our framework is highly
efficient for personalized ensemble pruning, and achieves much better pruning
performance with objective-mixture optimization when compared to state-of-art
approaches.
Liang Yu, Tao Jiang, Ming Sun, Yulong Zou
Comments: 8 pages
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC)
As a complement to cloud computing, fog computing can offer many benefits in
terms of avoiding the long wide-area network (WAN) propagation delay and
relieving the network bandwidth burden by providing local services to nearby
end users, resulting in a reduced revenue loss associated with the WAN
propagation delay and network bandwidth cost for a cloud provider. However,
serving the requests of end-users would lead to additional energy costs for fog
devices, thus the could provider must compensate fog devices for their losses.
In this paper, we investigate the problem of minimizing the total cost of a
cloud provider without sacrificing the interests of fog devices. To be
specific, we first formulate a total cost minimization problem for the cloud
provider, where the cost consists of four parts, namely the energy cost of data
centers, network bandwidth cost, revenue loss associated with WAN propagation
delay, and the economic compensation paid to fog devices. Note that the
formulated problem is a large-scale mixed integer linear programming, which is
in general NP-hard. To solve the problem efficiently, a distributed heuristic
algorithm is designed based on Proximal Jacobian Alternating Direction Method
of Multipliers (ADMM), which determines the number of active fog devices,
workload allocation, and the number of active servers in each cloud data
center. Extensive simulation results show the effectiveness of the designed
heuristic algorithm.
Johan Thunberg, Florian Bernard, Jorge Goncalves
Comments: 18 pages, 2 figures
Subjects: Optimization and Control (math.OC); Computer Vision and Pattern Recognition (cs.CV); Distributed, Parallel, and Cluster Computing (cs.DC); Multiagent Systems (cs.MA)
This paper addresses the problem of synchronizing orthogonal matrices over
directed graphs. For synchronized transformations (or matrices), composite
transformations over loops equal the identity. We formulate the synchronization
problem as a least-squares optimization problem with nonlinear constraints. The
synchronization problem appears as one of the key components in applications
ranging from 3D-localization to image registration. The main contributions of
this work can be summarized as the introduction of two novel algorithms; one
for symmetric graphs and one for graphs that are possibly asymmetric. Under
general conditions, the former has guaranteed convergence to the solution of a
spectral relaxation to the synchronization problem. The latter is stable for
small step sizes when the graph is quasi-strongly connected. The proposed
methods are verified in numerical simulations.
Amirhossein Javaheri, Hadi Zayyani, Farokh Marvasti
Comments: 12 pages, 6 figures
Subjects: Learning (cs.LG); Machine Learning (stat.ML)
This paper investigates the problem of recovering missing samples using
methods based on sparse representation adapted especially for image signals.
Instead of (l_2)-norm or Mean Square Error (MSE), a new perceptual quality
measure is used as the similarity criterion between the original and the
reconstructed images. The proposed metric called Convex SIMilarity (CSIM) index
is a modified version of the Structural SIMilarity (SSIM) index which despite
its predecessor, is convex and uni-modal. We also propose an iterative sparse
recovery method based on a constrained (l_1)-norm minimization problem
involving CSIM as the fidelity criterion. This optimization problem which is
adopted for missing sample recovery of images is efficiently solved via an
algorithm based on Alternating Direction Method of Multipliers (ADMM).
Simulation results show the performance of the new similarity index as well as
the proposed algorithm for missing sample recovery of test images.
Ken Dahm, Alexander Keller
Subjects: Learning (cs.LG); Graphics (cs.GR)
We show that the equations of reinforcement learning and light transport
simulation are related integral equations. Based on this correspondence, a
scheme to learn importance while sampling path space is derived. The new
approach is demonstrated in a consistent light transport simulation algorithm
that uses reinforcement learning to progressively learn where light comes from.
As using this information for importance sampling includes information about
visibility, too, the number of light transport paths with non-zero contribution
is dramatically increased, resulting in much less noisy images within a fixed
time budget.
Yuxi Li
Comments: arXiv admin note: text overlap with arXiv:1605.07669 by other authors
Subjects: Learning (cs.LG)
We give an overview of recent exciting achievements of deep reinforcement
learning (RL). We start with background of deep learning and reinforcement
learning, as well as introduction of testbeds. Next we discuss Deep Q-Network
(DQN) and its extensions, asynchronous methods, policy optimization, reward,
and planning. After that, we talk about attention and memory, unsupervised
learning, and learning to learn. Then we discuss various applications of RL,
including games, in particular, AlphaGo, robotics, spoken dialogue systems
(a.k.a. chatbot), machine translation, text sequence prediction, neural
architecture design, personalized web services, healthcare, finance, and music
generation. We mention topics/papers not reviewed yet. After listing a
collection of RL resources, we close with discussions.
Doyen Sahoo, Chenghao Liu, Steven C.H. Hoi
Subjects: Learning (cs.LG); Cryptography and Security (cs.CR)
Malicious URL, a.k.a. malicious website, is a common and serious threat to
cybersecurity. Malicious URLs host unsolicited content (spam, phishing,
drive-by exploits, etc.) and lure unsuspecting users to become victims of scams
(monetary loss, theft of private information, and malware installation), and
cause losses of billions of dollars every year. It is imperative to detect and
act on such threats in a timely manner. Traditionally, this detection is done
mostly through the usage of blacklists. However, blacklists cannot be
exhaustive, and lack the ability to detect newly generated malicious URLs. To
improve the generality of malicious URL detectors, machine learning techniques
have been explored with increasing attention in recent years. This article aims
to provide a comprehensive survey and a structural understanding of Malicious
URL Detection techniques using machine learning. We present the formal
formulation of Malicious URL Detection as a machine learning task, and
categorize and review the contributions of literature studies that addresses
different dimensions of this problem (feature representation, algorithm design,
etc.). Further, this article provides a timely and comprehensive survey for a
range of different audiences, not only for machine learning researchers and
engineers in academia, but also for professionals and practitioners in
cybersecurity industry, to help them understand the state of the art and
facilitate their own research and practical applications. We also discuss
practical issues in system design, open research challenges, and point out some
important directions for future research.
Marcella Astrid, Seung-Ik Lee
Comments: Accepted as a conference paper at BigComp 2017
Subjects: Learning (cs.LG)
Convolutional Neural Networks (CNNs) has shown a great success in many areas
including complex image classification tasks. However, they need a lot of
memory and computational cost, which hinders them from running in relatively
low-end smart devices such as smart phones. We propose a CNN compression method
based on CP-decomposition and Tensor Power Method. We also propose an iterative
fine tuning, with which we fine-tune the whole network after decomposing each
layer, but before decomposing the next layer. Significant reduction in memory
and computation cost is achieved compared to state-of-the-art previous work
with no more accuracy loss.
Nayyar A. Zaidi, Yang Du, Geoffrey I. Webb
Subjects: Learning (cs.LG)
Learning algorithms that learn linear models often have high representation
bias on real-world problems. In this paper, we show that this representation
bias can be greatly reduced by discretization. Discretization is a common
procedure in machine learning that is used to convert a quantitative attribute
into a qualitative one. It is often motivated by the limitation of some
learners to qualitative data. Discretization loses information, as fewer
distinctions between instances are possible using discretized data relative to
undiscretized data. In consequence, where discretization is not essential, it
might appear desirable to avoid it. However, it has been shown that
discretization often substantially reduces the error of the linear generative
Bayesian classifier naive Bayes. This motivates a systematic study of the
effectiveness of discretizing quantitative attributes for other linear
classifiers. In this work, we study the effect of discretization on the
performance of linear classifiers optimizing three distinct discriminative
objective functions — logistic regression (optimizing negative
log-likelihood), support vector classifiers (optimizing hinge loss) and a
zero-hidden layer artificial neural network (optimizing mean-square-error). We
show that discretization can greatly increase the accuracy of these linear
discriminative learners by reducing their representation bias, especially on
big datasets. We substantiate our claims with an empirical study on (42)
benchmark datasets.
Faicel Chamroukhi
Comments: arXiv admin note: substantial text overlap with arXiv:1506.06707, arXiv:1612.06879
Journal-ref: Neural Networks 79: 20-36 (2016)
Subjects: Methodology (stat.ME); Learning (cs.LG); Machine Learning (stat.ML)
Mixture of Experts (MoE) is a popular framework for modeling heterogeneity in
data for regression, classification, and clustering. For regression and cluster
analyses of continuous data, MoE usually use normal experts following the
Gaussian distribution. However, for a set of data containing a group or groups
of observations with heavy tails or atypical observations, the use of normal
experts is unsuitable and can unduly affect the fit of the MoE model. We
introduce a robust MoE modeling using the (t) distribution. The proposed (t)
MoE (TMoE) deals with these issues regarding heavy-tailed and noisy data. We
develop a dedicated expectation-maximization (EM) algorithm to estimate the
parameters of the proposed model by monotonically maximizing the observed data
log-likelihood. We describe how the presented model can be used in prediction
and in model-based clustering of regression data. The proposed model is
validated on numerical experiments carried out on simulated data, which show
the effectiveness and the robustness of the proposed model in terms of modeling
non-linear regression functions as well as in model-based clustering. Then, it
is applied to the real-world data of tone perception for musical data analysis,
and the one of temperature anomalies for the analysis of climate change data.
The obtained results show the usefulness of the TMoE model for practical
applications.
Oren Anava, Kfir Y. Levy
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
The weighted k-nearest neighbors algorithm is one of the most fundamental
non-parametric methods in pattern recognition and machine learning. The
question of setting the optimal number of neighbors as well as the optimal
weights has received much attention throughout the years, nevertheless this
problem seems to have remained unsettled. In this paper we offer a simple
approach to locally weighted regression/classification, where we make the
bias-variance tradeoff explicit. Our formulation enables us to phrase a notion
of optimal weights, and to efficiently find these weights as well as the
optimal number of neighbors efficiently and adaptively, for each data point
whose value we wish to estimate. The applicability of our approach is
demonstrated on several datasets, showing superior performance over standard
locally weighted methods.
François G. Meyer, Alexander M. Benison, Zachariah Smith, Daniel S. Barth
Subjects: Neurons and Cognition (q-bio.NC); Learning (cs.LG); Quantitative Methods (q-bio.QM)
We describe here the recent results of a multidisciplinary effort to design a
biomarker that can actively and continuously decode the progressive changes in
neuronal organization leading to epilepsy, a process known as epileptogenesis.
Using an animal model of acquired epilepsy, wechronically record hippocampal
evoked potentials elicited by an auditory stimulus. Using a set of reduced
coordinates, our algorithm can identify universal smooth low-dimensional
configurations of the auditory evoked potentials that correspond to distinct
stages of epileptogenesis. We use a hidden Markov model to learn the dynamics
of the evoked potential, as it evolves along these smooth low-dimensional
subsets. We provide experimental evidence that the biomarker is able to exploit
subtle changes in the evoked potential to reliably decode the stage of
epileptogenesis and predict whether an animal will eventually recover from the
injury, or develop spontaneous seizures.
Patrice Godefroid, Hila Peleg, Rishabh Singh
Subjects: Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR); Learning (cs.LG); Programming Languages (cs.PL); Software Engineering (cs.SE)
Fuzzing consists of repeatedly testing an application with modified, or
fuzzed, inputs with the goal of finding security vulnerabilities in
input-parsing code. In this paper, we show how to automate the generation of an
input grammar suitable for input fuzzing using sample inputs and
neural-network-based statistical machine-learning techniques. We present a
detailed case study with a complex input format, namely PDF, and a large
complex security-critical parser for this format, namely, the PDF parser
embedded in Microsoft’s new Edge browser. We discuss (and measure) the tension
between conflicting learning and fuzzing goals: learning wants to capture the
structure of well-formed inputs, while fuzzing wants to break that structure in
order to cover unexpected code paths and find bugs. We also present a new
algorithm for this learn&fuzz challenge which uses a learnt input probability
distribution to intelligently guide where to fuzz inputs.
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen
Subjects: Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Learning (cs.LG)
The (k)-Means clustering problem on (n) points is NP-Hard for any dimension
(dge 2), however, for the 1D case there exist exact polynomial time
algorithms. The current state of the art is a (O(kn^2)) dynamic programming
algorithm that uses (O(nk)) space. We present a new algorithm improving this to
(O(kn log n)) time and optimal (O(n)) space. We generalize our algorithm to
work for the absolute distance instead of squared distance and to work for any
Bregman Divergence as well.
Shan You, Chang Xu, Yunhe Wang, Chao Xu, Dacheng Tao
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
This paper presents privileged multi-label learning (PrML) to explore and
exploit the relationship between labels in multi-label learning problems. We
suggest that for each individual label, it cannot only be implicitly connected
with other labels via the low-rank constraint over label predictors, but also
its performance on examples can receive the explicit comments from other labels
together acting as an emph{Oracle teacher}. We generate privileged label
feature for each example and its individual label, and then integrate it into
the framework of low-rank based multi-label learning. The proposed algorithm
can therefore comprehensively explore and exploit label relationships by
inheriting all the merits of privileged information and low-rank constraints.
We show that PrML can be efficiently solved by dual coordinate descent
algorithm using iterative optimization strategy with cheap updates. Experiments
on benchmark datasets show that through privileged label features, the
performance can be significantly improved and PrML is superior to several
competing methods in most cases.
Shaowei Wang, Liusheng Huang, Pengzhan Wang, Hongli Xu, Wei Yang
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Human-Computer Interaction (cs.HC); Learning (cs.LG)
Ensemble learning has been widely employed by mobile applications, ranging
from environmental sensing to activity recognitions. One of the fundamental
issue in ensemble learning is the trade-off between classification accuracy and
computational costs, which is the goal of ensemble pruning. During
crowdsourcing, the centralized aggregator releases ensemble learning models to
a large number of mobile participants for task evaluation or as the
crowdsourcing learning results, while different participants may seek for
different levels of the accuracy-cost trade-off. However, most of existing
ensemble pruning approaches consider only one identical level of such
trade-off. In this study, we present an efficient ensemble pruning framework
for personalized accuracy-cost trade-offs via multi-objective optimization.
Specifically, for the commonly used linear-combination style of the trade-off,
we provide an objective-mixture optimization to further reduce the number of
ensemble candidates. Experimental results show that our framework is highly
efficient for personalized ensemble pruning, and achieves much better pruning
performance with objective-mixture optimization when compared to state-of-art
approaches.
Emilio Jesús Gallego Arias (MINES ParisTech, PSL Research University, France), Benoît Pin (MINES ParisTech, PSL Research University, France), Pierre Jouvelot (MINES ParisTech, PSL Research University, France)
Comments: In Proceedings UITP 2016, arXiv:1701.06745
Journal-ref: EPTCS 239, 2017, pp. 15-27
Subjects: Programming Languages (cs.PL); Human-Computer Interaction (cs.HC); Learning (cs.LG); Logic in Computer Science (cs.LO)
We describe jsCcoq, a new platform and user environment for the Coq
interactive proof assistant. The jsCoq system targets the HTML5-ECMAScript 2015
specification, and it is typically run inside a standards-compliant browser,
without the need of external servers or services. Targeting educational use,
jsCoq allows the user to start interaction with proof scripts right away,
thanks to its self-contained nature. Indeed, a full Coq environment is packed
along the proof scripts, easing distribution and installation. Starting to use
jsCoq is as easy as clicking on a link. The current release ships more than 10
popular Coq libraries, and supports popular books such as Software Foundations
or Certified Programming with Dependent Types. The new target platform has
opened up new interaction and display possibilities. It has also fostered the
development of some new Coq-related technology. In particular, we have
implemented a new serialization-based protocol for interaction with the proof
assistant, as well as a new package format for library distribution.
Min Lu, Hemant Ishwaran
Subjects: Machine Learning (stat.ML); Learning (cs.LG)
This paper presents an alternative approach to p-values in regression
settings. This approach, whose origins can be traced to machine learning, is
based on the leave-one-out bootstrap for prediction error. In machine learning
this is called the out-of-bag (OOB) error. To obtain the OOB error for a model,
one draws a bootstrap sample and fits the model to the in-sample data. The
out-of-sample prediction error for the model is obtained by calculating the
prediction error for the model using the out-of-sample data. Repeating and
averaging yields the OOB error, which represents a robust cross-validated
estimate of the accuracy of the underlying model. By a simple modification to
the bootstrap data involving “noising up” a variable, the OOB method yields a
variable importance (VIMP) index, which directly measures how much a specific
variable contributes to the prediction precision of a model. VIMP provides a
scientifically interpretable measure of the effect size of a variable, we call
the “predictive effect size”, that holds whether the researcher’s model is
correct or not, unlike the p-value whose calculation is based on the assumed
correctness of the model. We also discuss a marginal VIMP index, also easily
calculated, which measures the marginal effect of a variable, or what we call
“the discovery effect”. The OOB procedure can be applied to both parametric and
nonparametric regression models and requires only that the researcher can
repeatedly fit their model to bootstrap and modified bootstrap data. We
illustrate this approach on a survival data set involving patients with
systolic heart failure and to a simulated survival data set where the model is
incorrectly specified to illustrate its robustness to model misspecification.
Zhiyong Chen, Hui Liu
Comments: Submitted to IEEE ISIT 2017
Subjects: Information Theory (cs.IT)
In this paper, we investigate the signal shaping in a two-user discrete time
memoryless Gaussian multiple-access channel (MAC) with computation. It is shown
that by optimizing input probability distribution, the transmission rate per
transmitter is beyond the cut-set bound. In contrast with the single-user
discrete memoryless channel, the Maxwell-Boltzmann distribution is no longer a
good approximation to the optimal input probability distribution for this
discrete-time Gaussian MAC with computation. Specifically, we derive and
analyze the mutual information for this channel. Because of the computation in
the destination, the mutual information is not concave in general on the input
probability distribution, and then primal-dual interior-point method is used to
solve this non-convex problem. Finally, some good input probability
distributions for 16-ary pulse amplitude modulation (PAM) constellation are
obtained and achieve (4.0349) dB gain over the cut-set bound for the target
transmission rate (3.0067) bits/(channel use).
Rick Fritschek, Gerhard Wunder
Comments: 6 pages, 3 figures, short version submitted to ISIT2017
Subjects: Information Theory (cs.IT)
We study a deterministic approximation of the two-user multiple access
wiretap channel. This approximation enables results beyond the recently shown
( frac{2}{3}) secure degrees of freedom (s.d.o.f.) for the Gaussian multiple
access channel. While the s.d.o.f. were obtained by real interference
alignment, our approach uses signal-scale alignment. We show an achievable
scheme which is independent of the rationality of the channel gains. Moreover,
our result can differentiate between channel strengths, in particular between
both users, and establishes a secrecy rate dependent on this difference. We can
show that the resulting achievable secrecy rate tends to the s.d.o.f. for
vanishing channel gain differences. Moreover, we extend the s.d.o.f. bound
towards a general bound for varying channel strengths and show that our
achievable scheme reaches the bound for certain channel gain parameters. We
believe that our analysis is the first step towards a constant-gap analysis of
the Gaussian multiple access wiretap channel.
Patrick Schulte, Bernhard Geiger
Comments: 5 pages, 1 figure
Subjects: Information Theory (cs.IT)
Distribution matching is the process of mapping a uniformly distributed input
sequence onto sequences that approximate the output of a desired discrete
memoryless source and the original input sequence can be recovered. The special
case of a binary output alphabet and one-to-one mapping is studied. A
fixed-length distribution matcher is proposed that is optimal in the sense of
minimizing the unnormalized divergence between its output distribution and a
binary memoryless target distribution. Upper and lower bounds on the
unnormalized divergence are computed that increase logarithmically in the
output block length (n). It follows that a recently proposed constant
composition distribution matcher performs within a constant gap of the minimal
achievable informational divergence.
Eric Graves, Tan F. Wong
Comments: Submitted to ISIT2017
Subjects: Information Theory (cs.IT)
This paper employs equal-image-size source partitioning techniques to derive
the capacities of the general discrete memoryless wiretap channel (DM-WTC)
under four different secrecy criteria. These criteria respectively specify
requirements on the expected values and tail probabilities of the differences,
in absolute value and in exponent, between the joint probability of the secret
message and the eavesdropper’s observation and the corresponding probability if
they were independent. Some of these criteria reduce back to the standard
leakage and variation distance constraints that have been previously considered
in the literature. The capacities under these secrecy criteria are found to be
different when non-vanishing error and secrecy tolerances are allowed. Based on
these new results, we are able to conclude that the strong converse property
generally holds for the DM-WTC only under the two secrecy criteria based on
constraining the tail probabilities. Under the secrecy criteria based on the
expected values, an interesting phase change phenomenon is observed as the
tolerance values vary.
Geonu Kim, Jungwoo Lee
Comments: Longer version of a submission to ISIT 2017
Subjects: Information Theory (cs.IT)
When a node in a distributed storage system fails, it needs to be promptly
repaired to maintain system integrity. While typical erasure codes can provide
a significant storage advantage over replication, they suffer from poor repair
efficiency. Locally repairable codes (LRCs) tackle this issue by reducing the
number of nodes participating in the repair process (locality), at the cost of
reduced minimum distance. In this paper, we study the tradeoff characteristics
between locality and minimum distance of LRCs with local codes that have an
arbitrary distance requirement. Our approach is different from previous ones
where a common locality requirement is imposed on every node in that we allow
the locality requirements to vary arbitrarily from node to node. Such a
property can be an advantage for distributed storage systems with
non-homogeneous characteristics. We present Singleton-type distance upper
bounds and also provide an optimal code construction with respect to these
bounds. In addition, the possible rate region is characterized by a dimension
upper bound that does not depend on the distance. In line with a previous work,
our first bounds utilize the notion of locality profile, which refers to the
every symbol locality specified in a minimal sense. Since the notion of
locality profile is less desirable than the locality requirement, which all
conventional problem formulations are also based on, we provide locality
requirement-based bounds by exhaustively comparing over the relevant locality
profiles. Furthermore, and most importantly, we derive bounds with direct
expressions in terms of the locality requirements.
Bin Chen, Tanya Ignatenko, Frans M.J. Willems, Roel Maes, Erik van der Sluis, Georgios Selimis
Comments: 5 pages, 5 figures, Submitted to the IEEE International Symposium on Information Theory (ISIT) 2017
Subjects: Information Theory (cs.IT)
Physical unclonable functions (PUFs) can be used to generate cryptographic
keys by making use of the intrinsic randomness resulting from manufacturing
variations. Error correction codes (ECCs) help to make SRAM-PUFs, which are
always effected by noise and environmental changes, suitable for security
applications. In this paper, we propose practical error correction schemes for
PUF-based secret generation that are based on polar codes. The proposed scheme
could generate a 128-bit key using 1024 PUF bits and (896) helper data bits and
achieve a failure probability of 10^{-9} or lower for a practical SRAM-PUFs
setting with cross-over probability of 15%. The method is based on successive
cancellation in combination with list decoding and hash-based checking, making
use of the hash that is already available at the decoder. In addition, an
adaptive list decoder for polar codes is investigated. This decoder increases
the list size only if needed.
Giacomo Ricciutelli, Marco Baldi, Franco Chiaraluce, Gianluigi Liva
Comments: 5 pages, 5 figures, submitted
Subjects: Information Theory (cs.IT)
In this paper, the analysis of the performance of the concatenation of a
short polar code with an outer binary linear block code is addressed from a
distance spectrum viewpoint. The analysis targets the case where an outer
cyclic code is employed together with an inner systematic polar code. A
concatenated code ensemble is introduced placing an interleaver at the input of
the polar encoder. The introduced ensemble allows deriving bounds on the
achievable error rates under maximum likelihood decoding, by applying the union
bound to the (expurgated) average weight enumerators. The analysis suggests the
need of careful optimization of the outer code, to attain low error floors.
Anirban Ghatak
Subjects: Information Theory (cs.IT)
Recently a construction of optimal non-constant dimension subspace codes,
also termed projective space codes, has been reported in a paper of
Honold-Kiermaier-Kurz. Restricted to binary codes in a 5-dimensional ambient
space with minimum subspace distance 3, these optimal codes were interpreted in
terms of maximal partial spreads of 2-dimensional subspaces. In a parallel
development, an optimal binary (5,3) code was obtained by a minimal change
strategy on a nearly optimal example of Etzion and Vardy. In this article, we
report several examples of optimal binary (5,3) codes obtained by the
application of this strategy combined with changes to the spread structure of
existing codes. We also establish that, based on the types of constituent
spreads, our examples lie outside the framework of the existing construction.
Inaki Estella Aguerri, Abdellatif Zaidi, Giuseppe Caire, Shlomo Shamai (Shitz)
Comments: Submitted to the 2017 IEEE Int. Symposium on Information Theory (extended version, with more results, will be submitted to the IEEE Trans. on Information Theory)
Subjects: Information Theory (cs.IT)
We study the transmission over a network in which users send information to a
remote destination through relay nodes that are connected to the destination
via finite-capacity error-free links, i.e., a cloud radio access network. The
relays are constrained to operate without knowledge of the users’ codebooks,
i.e., they perform oblivious processing – The destination, or central
processor, however, is informed about the users’ codebooks. We establish a
single-letter characterization of the capacity region of this model for a class
of discrete memoryless channels in which the outputs at the relay nodes are
independent given the users’ inputs. We show that both relaying `a-la Cover-El
Gamal, i.e., compress-and-forward with joint decompression and decoding, and
“noisy network coding”, are optimal. The proof of the converse part
establishes, and utilizes, connections with the Chief Executive Officer (CEO)
source coding problem under logarithmic loss distortion measure. Extensions to
general discrete memoryless channels are also investigated. In this case, we
establish inner and outer bounds on the capacity region. For memoryless
Gaussian channels within the studied class of channels, we characterize the
capacity under Gaussian channel inputs.
Hilal Asi, Eitan Yaakobi
Subjects: Information Theory (cs.IT)
In this work we study two families of codes with availability, namely private
information retrieval (PIR) codes and batch codes. While the former requires
that every information symbol has (k) mutually disjoint recovering sets, the
latter asks this property for every multiset request of (k) information
symbols. The main problem under this paradigm is to minimize the number of
redundancy symbols. We denote this value by (r_P(n,k), r_B(n,k)), for PIR,
batch codes, respectively, where (n) is the number of information symbols.
Previous results showed that for any constant (k), (r_P(n,k) =
Theta(sqrt{n})) and (r_B(n,k)=O(sqrt{n}log(n)). In this work we study the
asymptotic behavior of these codes for non-constant (k) and specifically for
(k=Theta(n^epsilon)). We also study the largest value of (k) such that the
rate of the codes approaches 1, and show that for all (epsilon<1),
(r_P(n,n^epsilon) = o(n)), while for batch codes, this property holds for all
(epsilon< 0.5).
Yuval Cassuto, Evyatar Hemo, Sven Puchinger, Martin Bossert
Subjects: Information Theory (cs.IT)
We define multi-block interleaved codes as codes that allow reading
information from either a small sub-block or from a larger full block. The
former offers faster access, while the latter provides better reliability. We
specify the correction capability of the sub-block code through its gap (t)
from optimal minimum distance, and look to have full-block minimum distance
that grows with the parameter (t). We construct two families of such codes when
the number of sub-blocks is (3). The codes match the distance properties of
known integrated-interleaving codes, but with the added feature of mapping the
same number of information symbols to each sub-block. As such, they are the
first codes that provide read access in multiple size granularities and
correction capabilities.
Hoang Dau, Iwan Duursma, Han Mao Kiah, Olgica Milenkovic
Comments: 5 pages. arXiv admin note: substantial text overlap with arXiv:1612.01361
Subjects: Information Theory (cs.IT)
Despite their exceptional error-correcting properties, Reed-Solomon (RS)
codes have been overlooked in distributed storage applications due to the
common belief that they have poor repair bandwidth: A naive repair approach
would require the whole file to be reconstructed in order to recover a single
erased codeword symbol. In a recent work, Guruswami and Wootters (STOC’16)
proposed a single-erasure repair method for RS codes that achieves the optimal
repair bandwidth amongst all linear encoding schemes. We extend their trace
collection technique to cope with two erasures.
Karthikeyan Shanmugam, Antonia M. Tulino, Alexandros G. Dimakis
Comments: 5 pages, 1 Figure
Subjects: Information Theory (cs.IT)
Coded caching is a problem where encoded broadcasts are used to satisfy users
requesting popular files and having caching capabilities. Recent work by
Maddah-Ali and Niesen showed that it is possible to satisfy a scaling number of
users with only a constant number of broadcast transmissions by exploiting
coding and caching. Unfortunately, all previous schemes required the splitting
of files into an exponential number of packets before the significant coding
gains of caching appeared. The question of what can be achieved with polynomial
subpacketization (in the number of users) has been a central open problem in
this area. We resolve this problem and present the first coded caching scheme
with polynomial (in fact, linear) subpacketization. We obtain a number of
transmissions that is not constant, but can be any polynomial in the number of
users with an exponent arbitrarily close to zero. Our central technical tool is
a novel connection between Ruzsa-Szem’eredi graphs and coded caching.
Irene Marquez-Corbella, Jean-Pierre Tillich
Subjects: Information Theory (cs.IT)
In this paper we show how to attain the capacity of discrete symmetric
channels with polynomial time decoding complexity by considering iterated
((U|U+V)) constructions with Reed-Solomon code or algebraic geometry code
components. These codes are decoded with a recursive computation of the {em a
posteriori} probabilities of the code symbols together with the Koetter-Vardy
soft decoder used for decoding the code components in polynomial time. We show
that when the number of levels of the iterated ((U|U+V)) construction tends to
infinity, we attain the capacity of any discrete symmetric channel in this way.
This result follows from the polarization theorem together with a simple lemma
explaining how the Koetter-Vardy decoder behaves for Reed-Solomon codes of rate
close to (1). However, even if this way of attaining the capacity of a
symmetric channel is essentially the Ar{i}kan polarization theorem, there are
some differences with standard polar codes.
Indeed, with this strategy we can operate succesfully close to channel
capacity even with a small number of levels of the iterated ((U|U+V))
construction and the probability of error decays quasi-exponentially with the
codelength in such a case (i.e. exponentially if we forget about the
logarithmic terms in the exponent). We can even improve on this result by
considering the algebraic geometry codes constructed in cite{TVZ82}. In such a
case, the probability of error decays exponentially in the codelength for any
rate below the capacity of the channel. Moreover, when comparing this strategy
to Reed-Solomon codes (or more generally algebraic geometry codes) decoded with
the Koetter-Vardy decoding algorithm, it does not only improve the noise level
that the code can tolerate, it also results in a significant complexity gain.
Mandar N. Kulkarni, Jeffrey G. Andrews, Amitava Ghosh
Comments: submitted to IEEE Trans. Wireless Commun
Subjects: Information Theory (cs.IT)
Initial deployments of millimeter wave (mmWave) cellular networks are likely
to be enabled with self-backhauling, meaning that a fraction of the base
stations (BSs), called slave BSs, wirelessly backhaul data to/from BSs equipped
with fiber backhaul, called master BSs. In this work, we propose a general
random spatial model to analyze uplink (UL) and downlink (DL) SINR distribution
and mean rates corresponding to different access-backhaul and UL-DL resource
allocation schemes in a self-backhauled mmWave cellular network. In particular,
we focus on heuristic implementations of static and dynamic time division
duplexing (TDD) for access links with synchronized or unsynchronized
access-backhaul (SAB or UAB) time splits. We propose Poisson point process
(PPP) approximations to characterize the distribution of the new types of
interference encountered with dynamic TDD and UAB. These schemes offer better
resource utilization than static TDD and SAB, however the increasing
interference makes their choice non-trivial and the offered gains sensitive to
different network parameters, including UL/DL traffic asymmetry, user load per
BS or number of slave BSs per master BS. One can harness notable gains from UAB
and/or dynamic TDD only if backhaul links are designed to have much larger
throughput than the access links.
Jiachun Liao, Lalitha Sankar, Flavio P. Calmon, Vincent Y. F. Tan
Comments: An extended version version for the paper submitted to ISIT 2017
Subjects: Information Theory (cs.IT)
The problem of publishing privacy-guaranteed data for hypothesis testing is
studied using the maximal leakage (ML) as a metric for privacy and the type-II
error exponent as the utility metric. The optimal mechanism (random mapping)
that maximizes utility for a bounded leakage guarantee is determined for the
entire leakage range for binary datasets. For non-binary datasets,
approximations in the high privacy and high utility regimes are developed. The
results show that, for any desired leakage level, maximizing utility forces the
ML privacy mechanism to reveal partial to complete knowledge about a subset of
the source alphabet. The results developed on maximizing a convex function over
a polytope may also of an independent interest.
Ozgun Y. Bursalioglu, Chenwei Wang, Haralabos Papadopoulos, Giuseppe Caire
Comments: In the proceedings of the 50th Asilomar Conference on Signals, Systems, and Computers, Nov. 2016
Subjects: Information Theory (cs.IT)
We consider wireless networks of remote radio heads (RRH) with large
antenna-arrays, operated in TDD, with uplink (UL) training and
channel-reciprocity based downlink (DL) transmission. To achieve large area
spectral efficiencies, we advocate the use of methods that rely on rudimentary
scheduling, decentralized operation at each RRH and user-centric DL
transmission.
A slotted system is assumed, whereby users are randomly scheduled (e.g., via
shuffled round robin) in slots and across the limited pilot dimensions per
slot. As a result, multiple users in the vicinity of an RRH can simultaneously
transmit pilots on the same pilot dimension (and thus interfering with one
another). Each RRH performs rudimentary processing of the pilot observations in
“sectors”. In a sector, the RRH is able to resolve a scheduled user’s channel
when that user is determined to be the only one among the scheduled users (on
the same pilot dimension) with significant received power in the sector.
Subsequently, only the subset of scheduled users whose channels are resolved in
at least one sector can be served by the system.
We consider a spatially consistent evaluation of the area multiplexing gains
by means of a Poisson Point Process (PPP) problem formulation where RRHs,
blockers, scatterers and scheduled user terminals are all PPPs with individual
intensities. Also, we study directional training at the user terminals. Our
simulations suggest that, by controlling the intensity of the scheduled user
PPP and the user-pilot beam-width, many fold improvements can be expected in
area multiplexing gains with respect to conventional spatial pilot reuse
systems.
Oliver Johnson, Saikat Guha
Comments: 9 pages, shorter version submitted to ISIT 2017
Subjects: Information Theory (cs.IT)
We discuss properties of the “beamsplitter addition” operation, which
provides a non-standard scaled convolution of random variables supported on the
non-negative integers. We give a simple expression for the action of
beamsplitter addition using generating functions. We use this to give a
self-contained and purely classical proof of a heat equation and de Bruijn
identity, satisfied when one of the variables is geometric.
Thomas Debris-Alazard, Jean-Pierre Tillich
Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT)
The security of code-based cryptography relies primarily on the hardness of
generic decoding with linear codes. The study in depth of this problem is
crucial when it comes to assess the security level of any code-based
cryptosystem. The best known algorithms are all improvements of an old
algorithm due to Prange: they are known under the name of information set
decoding techniques (ISD). A while ago a generic decoding algorithm which does
not belong to this family has been proposed: statistical decoding. It is a
randomized algorithm that requires the computation of a large set of
parity-check equations of moderate weight. Several questions were left open
here, namely (i) what is the asymptotic complexity of this algorithm, (ii) is
there an efficient way to compute the parity-check equations for this
algorithm, (iii) can it be competitive in a certain range of parameters when
compared to ISD type algorithms ? In this paper we address all three issues. We
give in particular the asymptotic complexity of this algorithm, give a rather
efficient way of computing the parity-check equations needed for this algorithm
inspired by ISD techniques and give a lower bound on its complexity showing
that for standard cryptographic parameters it can never be better than Prange’s
algorithm.
Lixing Chen, Sheng Zhou, Jie Xu
Subjects: Networking and Internet Architecture (cs.NI); Information Theory (cs.IT)
Merging Mobile Edge Computing (MEC), which is an emerging paradigm to meet
the increasing computation demands from mobile devices, with the dense
deployment of Base Stations (BSs), is foreseen as a key step towards the next
generation mobile networks. However, new challenges arise for designing energy
efficient networks since radio access resources and computing resources of BSs
have to be jointly managed, and yet they are complexly coupled with traffic in
both spatial and temporal domains. In this paper, we address the challenge of
incorporating MEC into dense cellular networks, and propose an efficient online
algorithm, called ENGINE (ENErgy constrained offloadINg and slEeping) which
makes joint computation offloading and BS sleeping decisions in order to
maximize the quality of service while keeping the energy consumption low. Our
algorithm leverages Lyapunov optimization technique, works online and achieves
a close-to-optimal performance without using future information. Our simulation
results show that our algorithm can effectively reduce energy consumption
without sacrificing the user quality of service.
Jie Xu, Yuxuan Sun, Lixing Chen, Sheng Zhou
Subjects: Networking and Internet Architecture (cs.NI); Information Theory (cs.IT)
Merging mobile edge computing with the dense deployment of small cell base
stations promises enormous benefits such as a real proximity, ultra-low latency
access to cloud functionalities. However, the envisioned integration creates
many new challenges and one of the most significant is mobility management,
which is becoming a key bottleneck to the overall system performance. Simply
applying existing solutions leads to poor performance due to the highly
overlapped coverage areas of multiple base stations in the proximity of the
user and the co-provisioning of radio access and computing services. In this
paper, we develop a novel user-centric mobility management scheme, leveraging
Lyapunov optimization and multi-armed bandits theories, in order to maximize
the edge computation performance for the user while keeping the user’s
communication energy consumption below a constraint. The proposed scheme
effectively handles the uncertainties present at multiple levels in the system
and provides both short-term and long-term performance guarantee. Simulation
results show that our proposed scheme can significantly improve the computation
performance (compared to state of the art) while satisfying the communication
energy constraint.
Shuai Li, Mingxin Zhou, Jianjun Wu, Lingyang Song, Yonghui Li, Hongbin Li
Comments: letter
Subjects: Networking and Internet Architecture (cs.NI); Information Theory (cs.IT)
In this letter, we propose a joint transmission mode and transmit/receive
(Tx/Rx) antenna configuration scheme referred to as X-duplex in the relay
network with one source, one amplify-and-forward (AF) relay and one
destination. The relay is equipped with two antennas, each of which is capable
of reception and transmission. In the proposed scheme, the relay adaptively
selects its Tx and Rx antenna, operating in either full-duplex (FD) or
half-duplex (HD) mode. The proposed scheme is based on minimizing the symbol
error rate (SER) of the relay system. The asymptotic expressions of the
cumulative distribution function (CDF) for the end-to-end signal to
interference plus noise ratio (SINR), average SER and diversity order are
derived and validated by simulations. Results show that the X-duplex scheme
achieves additional spatial diversity, significantly reduces the performance
floor at high SNR and improves the system performance.
Hongxing Xia, Yongzhao Li, Hailin Zhang
Subjects: Networking and Internet Architecture (cs.NI); Information Theory (cs.IT)
We consider the wireless powered communications where users harvest energy
from non-dedicated sources. The user follows a harvest-then-transmit protocol:
in first phase of a slot time the source node harvests energy from a nearby
conventional Access Point, then transmit information to its destination node or
relay node in the second phase. We obtain the optimal extit{ harvesting ratio}
to maximize the expected throughput for direct transmission (DT )and decode
forward (DF) relay under outage constraint, respectively. Our results reveal
that the optimal harvest ratio for DT is dominated by the outage constraint
while for DF relay, by the data causality .
Yu-Jia Chen, Li-Chun Wang
Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT)
Taking into account of both the huge computing power of intruders and
untrusted cloud servers, we develop an enhanced secure pseudonym scheme to
protect the privacy of mobile cloud data. To face the huge computing power
challenge, we develop an unconditionally secure lightweight network coding
pseudonym scheme. For the privacy issue of untrusted cloud server, we further
design a two tier network coding to decouple the stored mobile cloud data from
the owner pseudonyms. Therefore, our proposed network coding based pseudonym
scheme can simultaneously defend against attackers from both outside and
inside. We implement our proposed two-tier light-weight network coding
mechanism in a group location based service (LBS) using untrusted cloud
database. Compared to computationally secure Hash-based pseudonym, our proposed
scheme is not only unconditionally secure, but also can reduce more than 90
percent of processing time as well as 10 percent of energy consumption.