This open access book constitutes the thoroughly refereed post-conference proceedings of the 6th International Workshop on Graph Structures for Knowledge Representation and Reasoning, GKR 2020, held ...virtually in September 2020, associated with ECAI 2020, the 24th European Conference on Artificial Intelligence.The 7 revised full papers presented together with 2 invited contributions were reviewed and selected from 9 submissions. The contributions address various issues for knowledge representation and reasoning and the common graph-theoretic background, which allows to bridge the gap between the different communities.
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.
Until recently, almost all of the interactions between objects in virtual 3D worlds have been based on calculations performed using linear algebra. Linear algebra relies heavily on coordinates, ...however, which can make many geometric programming tasks very specific and complex-often a lot of effort is required to bring about even modest performance enhancements. Although linear algebra is an efficient way to specify low-level computations, it is not a suitable high-level language for geometric programming. Geometric Algebra for Computer Science presents a compelling alternative to the limitations of linear algebra. Geometric algebra, or GA, is a compact, time-effective, and performance-enhancing way to represent the geometry of 3D objects in computer programs. In this book you will find an introduction to GA that will give you a strong grasp of its relationship to linear algebra and its significance for your work. You will learn how to use GA to represent objects and perform geometric operations on them. And you will begin mastering proven techniques for making GA an integral part of your applications in a way that simplifies your code without slowing it down. * The first book on Geometric Algebra for programmers in computer graphics and entertainment computing* Written by leaders in the field providing essential information on this new technique for 3D graphics* This full colour book includes a website with GAViewer, a program to experiment with GA.
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.
This volume provides a detailed account of block cipher analysis, design, and deployment. The authors describe the most prominent block ciphers and give insights into their design.
PDF
