Recently, many streaming algorithms have utilized generalizations of the fact
that the expected maximum distance of any $4$-wise independent random walk on a
line over $n$ steps is $O(\sqrt{n})$. In this paper, we show that $4$-wise
independence is required for all of these algorithms, by constructing a
$3$-wise independent random walk with expected maximum distance
$\Omega(\sqrt{n} \lg n)$ from the origin. We prove that this bound is tight for
the first and second moment, and also extract a surprising matrix inequality
from these results.
Next, we consider a generalization where the steps $X_i$ are $k$-wise
independent random variables with bounded $p$th moments. For general $k, p$, we
determine the (asymptotically) maximum possible $p$th moment of the supremum of
$X_1 + \dots + X_i$ over $1 \le i \le n$. We highlight the case $k = 4, p = 2$:
here, we prove that the second moment of the furthest distance traveled is
$O(\sum X_i^2)$. For this case, we only need the $X_i$'s to have bounded second
moments and do not even need the $X_i$'s to be identically distributed. This
implies an asymptotically stronger statement than Kolmogorov's maximal
inequality that requires only $4$-wise independent random variables, and
generalizes a recent result of B{\l}asiok.
Authors' comments: 26 pages
While there are numerous criteria for photometrically identifying active
galactic nuclei (AGNs), searches in the optical and UV tend to exclude galaxies
that are highly dust obscured. This is problematic for constraining models of
AGN evolution and estimating the AGN contribution to the cosmic X-ray and IR
backgrounds, as highly obscured objects tend to be underrepresented in
large-scale surveys. To address this, we identify potentially obscured AGNs
using mid-IR color colors from the Wide-field Infrared Survey Explorer (WISE)
catalog. This paper presents the results of optical spectroscopy of obscured
AGN candidates using Keck DEIMOS, and their physical properties derived from
these spectra. We find that a $W1-W2>0.8$ color criterion effectively selects
AGNs with a higher median level of $E(B-V)$ extinction compared to the AGNs
found in the SDSS DR7 survey. This optical extinction can be measured using SED
modeling or by using $r-W1$ as a measure of optical to IR flux. We find that
specific, targeted observations are necessary to find the most highly optically
obscured AGNs, and that additional far-IR photometry is necessary to further
constrain the dust properties of these AGNs.
Authors' comments: 20 pages, 25 figures, accepted by MNRAS
Low precision weights, activations, and gradients have been proposed as a way
to improve the computational efficiency and memory footprint of deep neural
networks. Recently, low precision networks have even shown to be more robust to
adversarial attacks. However, typical implementations of low precision DNNs use
uniform precision across all layers of the network. In this work, we explore
whether a heterogeneous allocation of precision across a network leads to
improved performance, and introduce a learning scheme where a DNN
stochastically explores multiple precision configurations through learning.
This permits a network to learn an optimal precision configuration. We show on
convolutional neural networks trained on MNIST and ILSVRC12 that even though
these nets learn a uniform or near-uniform allocation strategy respectively,
stochastic precision leads to a favourable regularization effect improving
generalization.
Authors' comments: UAI 2018
Leading eigenvalue problems for large scale matrices arise in many
applications. Coordinate-wise descent methods are considered in this work for
such problems based on a reformulation of the leading eigenvalue problem as a
non-convex optimization problem. The convergence of several coordinate-wise
methods is analyzed and compared. Numerical examples of applications to quantum
many-body problems demonstrate the efficiency and provide benchmarks of the
proposed coordinate-wise descent methods.
This article introduces the pammtools package, which facilitates data
transformation, estimation and interpretation of Piece-wise exponential
Additive Mixed Models. A special focus is on time-varying effects and
cumulative effects of time-dependent covariates, where multiple past
observations of a covariate can cumulatively affect the hazard, possibly
weighted by a non-linear function. The package provides functions for
convenient simulation and visualization of such effects as well as a robust and
versatile function to transform time-to-event data from standard formats to a
format suitable for their estimation. The models can be represented as
Generalized Additive Mixed Models and estimated using the R package mgcv. Many
examples on real and simulated data as well as the respective R code are
provided throughout the article.
In this paper, we propose a method for obtaining sentence-level embeddings.
While the problem of securing word-level embeddings is very well studied, we
propose a novel method for obtaining sentence-level embeddings. This is
obtained by a simple method in the context of solving the paraphrase generation
task. If we use a sequential encoder-decoder model for generating paraphrase,
we would like the generated paraphrase to be semantically close to the original
sentence. One way to ensure this is by adding constraints for true paraphrase
embeddings to be close and unrelated paraphrase candidate sentence embeddings
to be far. This is ensured by using a sequential pair-wise discriminator that
shares weights with the encoder that is trained with a suitable loss function.
Our loss function penalizes paraphrase sentence embedding distances from being
too large. This loss is used in combination with a sequential encoder-decoder
network. We also validated our method by evaluating the obtained embeddings for
a sentiment analysis task. The proposed method results in semantic embeddings
and outperforms the state-of-the-art on the paraphrase generation and sentiment
analysis task on standard datasets. These results are also shown to be
statistically significant.
Authors' comments: COLING 2018 (accepted)
Future mobile devices are anticipated to perceive, understand and react to
the world on their own by running multiple correlated deep neural networks
on-device. Yet the complexity of these neural networks needs to be trimmed down
both within-model and cross-model to fit in mobile storage and memory. Previous
studies focus on squeezing the redundancy within a single neural network. In
this work, we aim to reduce the redundancy across multiple models. We propose
Multi-Task Zipping (MTZ), a framework to automatically merge correlated,
pre-trained deep neural networks for cross-model compression. Central in MTZ is
a layer-wise neuron sharing and incoming weight updating scheme that induces a
minimal change in the error function. MTZ inherits information from each model
and demands light retraining to re-boost the accuracy of individual tasks.
Evaluations show that MTZ is able to fully merge the hidden layers of two
VGG-16 networks with a 3.18% increase in the test error averaged on ImageNet
and CelebA, or share 39.61% parameters between the two networks with <0.5%
increase in the test errors for both tasks. The number of iterations to retrain
the combined network is at least 17.8 times lower than that of training a
single VGG-16 network. Moreover, experiments show that MTZ is also able to
effectively merge multiple residual networks.
Authors' comments: Published as a conference paper at NeurIPS 2018
Motion detection algorithms that can be applied to surveillance cameras such
as CCTV (Closed Circuit Television) have been studied extensively. Motion
detection algorithm is mostly based on background subtraction. One main issue
in this technique is that false positives of dynamic backgrounds such as wind
shaking trees and flowing rivers might occur. In this paper, we proposed a
method to search for dynamic background region by analyzing the video and
removing false positives by re-checking false positives. The proposed method
was evaluated based on CDnet 2012/2014 dataset obtained at
"changedetection.net" site. We also compared its processing speed with other
algorithms.
Authors' comments: 8 pages
Deep learning stands at the forefront in many computer vision tasks. However,
deep neural networks are usually data-hungry and require a huge amount of
well-annotated training samples. Collecting sufficient annotated data is very
expensive in many applications, especially for pixel-level prediction tasks
such as semantic segmentation. To solve this fundamental issue, we consider a
new challenging vision task, Internetly supervised semantic segmentation, which
only uses Internet data with noisy image-level supervision of corresponding
query keywords for segmentation model training. We address this task by
proposing the following solution. A class-specific attention model unifying
multiscale forward and backward convolutional features is proposed to provide
initial segmentation "ground truth". The model trained with such noisy
annotations is then improved by an online fine-tuning procedure. It achieves
state-of-the-art performance under the weakly-supervised setting on PASCAL
VOC2012 dataset. The proposed framework also paves a new way towards learning
from the Internet without human interaction and could serve as a strong
baseline therein. Code and data will be released upon the paper acceptance.
To achieve parsimonious inference in per-pixel labeling tasks with a limited
computational budget, we propose a \emph{Pixel-wise Attentional Gating} unit
(\emph{PAG}) that learns to selectively process a subset of spatial locations
at each layer of a deep convolutional network. PAG is a generic,
architecture-independent, problem-agnostic mechanism that can be readily
"plugged in" to an existing model with fine-tuning. We utilize PAG in two ways:
1) learning spatially varying pooling fields that improve model performance
without the extra computation cost associated with multi-scale pooling, and 2)
learning a dynamic computation policy for each pixel to decrease total
computation while maintaining accuracy.
We extensively evaluate PAG on a variety of per-pixel labeling tasks,
including semantic segmentation, boundary detection, monocular depth and
surface normal estimation. We demonstrate that PAG allows competitive or
state-of-the-art performance on these tasks. Our experiments show that PAG
learns dynamic spatial allocation of computation over the input image which
provides better performance trade-offs compared to related approaches (e.g.,
truncating deep models or dynamically skipping whole layers). Generally, we
observe PAG can reduce computation by $10\%$ without noticeable loss in
accuracy and performance degrades gracefully when imposing stronger
computational constraints.
Authors' comments: https://www.ics.uci.edu/~skong2/PAG.html
This paper proposes a deep neural network (DNN) for piece-wise planar
depthmap reconstruction from a single RGB image. While DNNs have brought
remarkable progress to single-image depth prediction, piece-wise planar
depthmap reconstruction requires a structured geometry representation, and has
been a difficult task to master even for DNNs. The proposed end-to-end DNN
learns to directly infer a set of plane parameters and corresponding plane
segmentation masks from a single RGB image. We have generated more than 50,000
piece-wise planar depthmaps for training and testing from ScanNet, a
large-scale RGBD video database. Our qualitative and quantitative evaluations
demonstrate that the proposed approach outperforms baseline methods in terms of
both plane segmentation and depth estimation accuracy. To the best of our
knowledge, this paper presents the first end-to-end neural architecture for
piece-wise planar reconstruction from a single RGB image. Code and data are
available at https://github.com/art-programmer/PlaneNet.
Authors' comments: CVPR 2018
Harvesting dense pixel-level annotations to train deep neural networks for
semantic segmentation is extremely expensive and unwieldy at scale. While
learning from synthetic data where labels are readily available sounds
promising, performance degrades significantly when testing on novel realistic
data due to domain discrepancies. We present Dual Channel-wise Alignment
Networks (DCAN), a simple yet effective approach to reduce domain shift at both
pixel-level and feature-level. Exploring statistics in each channel of CNN
feature maps, our framework performs channel-wise feature alignment, which
preserves spatial structures and semantic information, in both an image
generator and a segmentation network. In particular, given an image from the
source domain and unlabeled samples from the target domain, the generator
synthesizes new images on-the-fly to resemble samples from the target domain in
appearance and the segmentation network further refines high-level features
before predicting semantic maps, both of which leverage feature statistics of
sampled images from the target domain. Unlike much recent and concurrent work
relying on adversarial training, our framework is lightweight and easy to
train. Extensive experiments on adapting models trained on synthetic
segmentation benchmarks to real urban scenes demonstrate the effectiveness of
the proposed framework.
This paper tackles the problem of video object segmentation, given some user
annotation which indicates the object of interest. The problem is formulated as
pixel-wiseretrieval in a learned embedding space: we embed pixels of the same
object instance into the vicinity of each other, using a fully convolutional
network trained by a modified triplet loss as the embedding model. Then the
annotated pixels are set as reference and the rest of the pixels are classified
using a nearest-neighbor approach. The proposed method supports different kinds
of user input such as segmentation mask in the first frame (semi-supervised
scenario), or a sparse set of clicked points (interactive scenario). In the
semi-supervised scenario, we achieve results competitive with the state of the
art but at a fraction of computation cost (275 milliseconds per frame). In the
interactive scenario where the user is able to refine their input iteratively,
the proposed method provides instant response to each input, and reaches
comparable quality to competing methods with much less interaction.
Authors' comments: Accepted to CVPR 2018
By means of a varied-shape thermophysical model (VS-TPM) of Hanus et al.
(2015) that takes into account asteroid shape and pole uncertainties, we
analyze the thermal IR data acquired by the NASA's WISE satellite of about 300
asteroids with derived convex shape models. We utilize publicly available
convex shape models and rotation states as input for the TPM. For more than one
hundred asteroids, the TPM gives us an acceptable fit to the thermal IR data
allowing us to report their size, thermal inertia, surface roughness or visible
geometric albedo. This work more than doubles the number of asteroids with
determined thermophysical properties. In the remaining cases, the shape model
and pole orientation uncertainties, specific rotation or thermophysical
properties, poor thermal IR data or their coverage prevent the determination of
reliable thermophysical properties. Finally, we present the main results of the
statistical study of derived thermophysical parameters within the whole
population of main-belt asteroids and within few asteroid families. Our sizes
are, in average, consistent with the radiometric sizes reported by Mainzer et
al. (2016). The thermal inertia increases with decreasing size, but a large
range of thermal inertia values is observed within the similar size ranges
between D~10-100 km. We derived unexpectedly low thermal inertias (<20 SI) for
several asteroids with sizes 10<D<50 km, indicating a very fine and mature
regolith on their surface. The thermal inertia values seem to be consistent
within several collisional families. The fast rotators with P<4 h tend to have
slightly larger thermal inertia values, so probably are not covered by a fine
regolith. This could be explained, for example, by the loss of the fine
regolith due to the centrifugal force, or by the ineffectiveness of the
regolith production (e.g., by the thermal cracking mechanism of Delbo' et al.
2014).
Authors' comments: Published in Icarus
We apply a measurement-based closed-loop control scheme to the dissipative
Lipkin-Meshkov-Glick model. Specifically, we use the Wiseman-Milburn feedback
master equation to control its quantum phase transition.For the steady state
properties of the Lipkin-Meshkov-Glick system under feedback we show that the
considered control scheme changes the critical point of the phase transition.
Finite-size corrections blur these signatures in operator expectation values
but entanglement measures such as concurrence can be used to locate the
transition point more precisely. We find that with feedback, the position of
the critical point can be shifted to smaller spin-spin interactions, which is
potentially useful for setups with limited control on these.
Gradient Boosted Decision Trees (GBDT) is a very successful ensemble learning
algorithm widely used across a variety of applications. Recently, several
variants of GBDT training algorithms and implementations have been designed and
heavily optimized in some very popular open sourced toolkits including XGBoost,
LightGBM and CatBoost. In this paper, we show that both the accuracy and
efficiency of GBDT can be further enhanced by using more complex base learners.
Specifically, we extend gradient boosting to use piecewise linear regression
trees (PL Trees), instead of piecewise constant regression trees, as base
learners. We show that PL Trees can accelerate convergence of GBDT and improve
the accuracy. We also propose some optimization tricks to substantially reduce
the training time of PL Trees, with little sacrifice of accuracy. Moreover, we
propose several implementation techniques to speedup our algorithm on modern
computer architectures with powerful Single Instruction Multiple Data (SIMD)
parallelism. The experimental results show that GBDT with PL Trees can provide
very competitive testing accuracy with comparable or less training time.
Graphical modeling explores dependences among a collection of variables by
inferring a graph that encodes pairwise conditional independences. For jointly
Gaussian variables, this translates into detecting the support of the precision
matrix. Many modern applications feature high-dimensional and contaminated data
that complicate this task. In particular, traditional robust methods that
down-weight entire observation vectors are often inappropriate as
high-dimensional data may feature partial contamination in many observations.
We tackle this problem by giving a robust method for sparse precision matrix
estimation based on the $\gamma$-divergence under a cell-wise contamination
model. Simulation studies demonstrate that our procedure outperforms existing
methods especially for highly contaminated data.
Programs are bloated. Our study shows that only 5% of libc is used on average
across the Ubuntu Desktop environment (2016 programs); the heaviest user, vlc
media player, only needed 18%.
In this paper: (1) We present a debloating framework built on a compiler
toolchain that can successfully debloat programs (shared/static libraries and
executables). Our solution can successfully compile and load most libraries on
Ubuntu Desktop 16.04. (2) We demonstrate the elimination of over 79% of code
from coreutils and 86% of code from SPEC CPU 2006 benchmark programs without
affecting functionality. We show that even complex programs such as Firefox and
curl can be debloated without a need to recompile. (3) We demonstrate the
security impact of debloating by eliminating over 71% of reusable code gadgets
from the coreutils suite and show that unused code that contains real-world
vulnerabilities can also be successfully eliminated without adverse effects on
the program. (4) We incur a low load time overhead.
Authors' comments: Usenix Security 2018
In this work we propose a method for anatomical data augmentation that is
based on using slices of computed tomography (CT) examinations that are
adjacent to labeled slices as another resource of labeled data for training the
network. The extended labeled data is used to train a U-net network for a
pixel-wise classification into different hepatic lesions and normal liver
tissues. Our dataset contains CT examinations from 140 patients with 333 CT
images annotated by an expert radiologist. We tested our approach and compared
it to the conventional training process. Results indicate superiority of our
method. Using the anatomical data augmentation we achieved an improvement of 3%
in the success rate, 5% in the classification accuracy, and 4% in Dice.
Authors' comments: To be presented at IEEE ISBI 2018
Multi-color photometry is presented for a sample of 60 dwarf ellipticals (dE)
selected by morphology. The sample uses data from GALEX, SDSS and WISE to
investigate the colors in filters NUV, ugri and W1 (3.4mum). We confirm the
blueward shift in the color-magnitude relation for dwarf ellipticals, compared
to CMR for bright ellipticals, as seen in previous studies. However, we find
the deviation in color across the UV to near-IR for dE's is a strong signal of
a younger age for dwarf ellipticals, one that indicates decreasing mean age
with lower stellar mass. Lower mass dE's are found to have mean ages of 4 Gyrs
and mean [Fe/H] values of -1.2. Age and metallicity increase to the most
massive dE's with mean ages similar to normal ellipticals (12 Gyrs) and their
lowest metallicities ([Fe/H] = -0.3). Deduced initial star formation rates for
dE's, combined with their current metallicities and central stellar densities,
suggests a connection between field LSB dwarfs and cluster dE's, where the
cluster environment halts star formation for dE's triggering a separate
evolutionary path.
Authors' comments: 15 pages, 9 figure, accepted for AJ. arXiv admin note: text overlap
with arXiv:1609.07500
