Object Detection With Deep Learning: A Review Zhao, Zhong-Qiu; Zheng, Peng; Xu, Shou-Tao ...
IEEE transaction on neural networks and learning systems,
2019-Nov., 2019-11-00, 20191101, Letnik:
30, Številka:
11
Journal Article
Odprti dostop
Due to object detection's close relationship with video analysis and image understanding, it has attracted much research attention in recent years. Traditional object detection methods are built on ...handcrafted features and shallow trainable architectures. Their performance easily stagnates by constructing complex ensembles that combine multiple low-level image features with high-level context from object detectors and scene classifiers. With the rapid development in deep learning, more powerful tools, which are able to learn semantic, high-level, deeper features, are introduced to address the problems existing in traditional architectures. These models behave differently in network architecture, training strategy, and optimization function. In this paper, we provide a review of deep learning-based object detection frameworks. Our review begins with a brief introduction on the history of deep learning and its representative tool, namely, the convolutional neural network. Then, we focus on typical generic object detection architectures along with some modifications and useful tricks to improve detection performance further. As distinct specific detection tasks exhibit different characteristics, we also briefly survey several specific tasks, including salient object detection, face detection, and pedestrian detection. Experimental analyses are also provided to compare various methods and draw some meaningful conclusions. Finally, several promising directions and tasks are provided to serve as guidelines for future work in both object detection and relevant neural network-based learning systems.
We design a new distribution over
m
×
n
matrices
S
so that, for any fixed
n
×
d
matrix
A
of rank
r
, with probability at least 9/10, ∥
SAx
∥
2
= (1 ± ε)∥
Ax
∥
2
simultaneously for all
x
∈ R
d
. Here,
...m
is bounded by a polynomial in
r
ε
− 1
, and the parameter ε ∈ (0, 1. Such a matrix
S
is called a
subspace embedding
. Furthermore,
SA
can be computed in
O
(nnz(
A
)) time, where nnz(
A
) is the number of nonzero entries of
A
. This improves over all previous subspace embeddings, for which computing
SA
required at least Ω(
nd
log
d
) time. We call these
S
sparse embedding matrices
.
Using our sparse embedding matrices, we obtain the fastest known algorithms for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and ℓ
p
regression.
More specifically, let
b
be an
n
× 1 vector, ε > 0 a small enough value, and integers
k
,
p
⩾ 1. Our results include the following.
—
Regression:
The regression problem is to find
d
× 1 vector
x
′ for which ∥
Ax
′ −
b
∥
p
⩽ (1 + ε)min
x
∥
Ax
−
b
∥
p
. For the Euclidean case
p
= 2, we obtain an algorithm running in
O
(nnz(
A
)) +
Õ
(
d
3
ε
−2
) time, and another in
O
(nnz(
A
)log(1/ε)) +
Õ
(
d
3
log (1/ε)) time. (Here,
Õ
(
f
) =
f
ċ log
O
(1)
(
f
).) For
p
∈ 1, ∞), more generally, we obtain an algorithm running in
O
(nnz(
A
) log
n
) +
O
(
r
\ε
−1
)
C
time, for a fixed
C
.
—
Low-rank approximation:
We give an algorithm to obtain a rank-
k
matrix
Â
k
such that ∥
A
−
Â
k
∥
F
≤ (1 + ε )∥
A
−
A
k
∥
F
, where
A
k
is the best rank-
k
approximation to
A
. (That is,
A
k
is the output of principal components analysis, produced by a truncated singular value decomposition, useful for latent semantic indexing and many other statistical problems.) Our algorithm runs in
O
(nnz(
A
)) +
Õ
(
nk
2
ε
−4
+
k
3
ε
−5
) time.
—
Leverage scores:
We give an algorithm to estimate the leverage scores of
A
, up to a constant factor, in
O
(nnz(
A
)log
n
) +
Õ
(
r
3
)time.
Fair Enough Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
Journal of the ACM,
03/2018, Letnik:
65, Številka:
2
Journal Article
Recenzirano
We consider the problem of fairly allocating indivisible goods, focusing on a recently introduced notion of fairness called
maximin share guarantee
: each player’s value for his allocation should be ...at least as high as what he can guarantee by dividing the items into as many bundles as there are players and receiving his least desirable bundle. Assuming additive valuation functions, we show that such allocations may not exist, but allocations guaranteeing each player 2/3 of the above value always exist. These theoretical results have direct practical implications.
Mean field control (MFC) is an effective way to mitigate the curse of dimensionality of cooperative multi-agent reinforcement learning (MARL) problems. This work considers a collection of ...\(N_{\mathrm{pop}}\) heterogeneous agents that can be segregated into \(K\) classes such that the \(k\)-th class contains \(N_k\) homogeneous agents. We aim to prove approximation guarantees of the MARL problem for this heterogeneous system by its corresponding MFC problem. We consider three scenarios where the reward and transition dynamics of all agents are respectively taken to be functions of \((1)\) joint state and action distributions across all classes, \((2)\) individual distributions of each class, and \((3)\) marginal distributions of the entire population. We show that, in these cases, the \(K\)-class MARL problem can be approximated by MFC with errors given as \(e_1=\mathcal{O}(\frac{\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}}{N_{\mathrm{pop}}}\sum_{k}\sqrt{N_k})\), \(e_2=\mathcal{O}(\left\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right\sum_{k}\frac{1}{\sqrt{N_k}})\) and \(e_3=\mathcal{O}\left(\left\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right\left\frac{A}{N_{\mathrm{pop}}}\sum_{k\inK}\sqrt{N_k}+\frac{B}{\sqrt{N_{\mathrm{pop}}}\right\right)\), respectively, where \(A, B\) are some constants and \(|\mathcal{X}|,|\mathcal{U}|\) are the sizes of state and action spaces of each agent. Finally, we design a Natural Policy Gradient (NPG) based algorithm that, in the three cases stated above, can converge to an optimal MARL policy within \(\mathcal{O}(e_j)\) error with a sample complexity of \(\mathcal{O}(e_j^{-3})\), \(j\in\{1,2,3\}\), respectively.
Most Tensor Problems Are NP-Hard HILLAR, Christopher J; LIM, Lek-Heng
Journal of the ACM,
11/2013, Letnik:
60, Številka:
6
Journal Article
Recenzirano
Odprti dostop
We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear ...equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant is NP-, #P-, and VNP-hard.
Blockchain, as a decentralized and distributed public ledger technology in peer-to-peer network, has received considerable attention recently. It applies a linked block structure to verify and store ...data, and applies the trusted consensus mechanism to synchronize changes in data, which makes it possible to create a tamper-proof digital platform for storing and sharing data. It is believed that blockchain can be utilized in diverse Internet interactive systems (e.g., Internet of Things, supply chain systems, identity management, and so on). However, there are some privacy challenges that may hinder the applications of blockchain. The goal of this survey is to provide some insights into the privacy issues associated with blockchain. We analyze the privacy threats in blockchain and discuss existing cryptographic defense mechanisms, i.e., anonymity and transaction privacy preservation. Furthermore, we summarize some typical implementations of privacy preservation mechanisms in blockchain and explore future research challenges that still need to be addressed in order to preserve privacy when blockchain is used.
PDF
