s2fieldsofstudy:
Computer Science
Philosophy

text:
DeFind: A Protege Plugin for Computing Concept Definitions in EL Ontologies

We introduce an extension to the Protege ontology editor, which allows for discovering concept definitions, which are not explicitly present in axioms, but are logically implied by an ontology. The plugin supports ontologies formulated in the Description Logic EL, which underpins the OWL 2 EL profile of the Web Ontology Language and despite its limited expressiveness captures most of the biomedical ontologies published on the Web. The developed tool allows to verify whether a concept can be defined using a vocabulary of interest specified by a user. In particular, it allows to decide whether some vocabulary items can be omitted in a formulation of a complex concept. The corresponding definitions are presented to the user and are provided with explanations generated by an ontology reasoner.

Introduction
The development and application of large terminological systems pose new challenges for ontology engineering and automated reasoning tools. A question which becomes evidently important in the context of large ontologies is whether their content and logical consequences are easy to comprehend. To address this problem, a number of visualization and explanation tools has been integrated into ontology editing environments such as, e.g., visualization and explanation services implemented for the Protégé ontology editor. It is common that an expert exploring an ontology encounters concepts, which are formulated in a vocabulary she is not familiar with. More generally, only a certain part of an ontology vocabulary may be familiar to an expert, while the remaining part may be not. When a formulation of some concept employs vocabulary items unknown to an expert, typically she would like to know whether this concept can be reformulated in the familiar vocabulary. To give a simplified example, suppose an ontology of cuisines contains axiom Dumplings Entree Gnocci (stating that Dumplings being Entree are Gnocci) together with concept inclusions Gnocci Dumplings and Dumplings Entree. Assume an expert is familiar with concepts Entree and Gnocci and she encounters the concept Dumplings Entree mentioned in the ontology. First, one may notice that this concept can be simplified, i.e., it is equivalent to Dumplings wrt the ontology, due to the inclusions above. Second, the ontology entails that Dumplings and Gnocci are equivalent, thus, the original concept can be reformulated as Gnocci (or as Gnocci Entree) in the vocabulary known to the user.
In this paper, we introduce DeFind, an extension to the Protégé ontology editor, which allows to find concept definitions in a user specified vocabulary consisting of concept and relations names from an input ontology. In particular, it allows to verify whether some concept or relation names can be omitted in a formulation of a (complex) concept. To the best of our knowledge, this is the first implementation of these reasoning services as a part of an ontology editing tool. Specifically, for a given ontology Ø, vocabulary Σ, and a concept C of interest, DeFind computes definitions of C wrt Ø in Σ, i.e. concepts {D 1 , . . . , D n } (whenever they exist) such that D i contains symbols only from Σ and Ø |= C ≡ D i , for all i = 1, . . . , n. DeFind supports ontologies formulated in the Description Logic EL, which allows for building concepts using conjunction and existential restriction, and includes built-in concepts such as ⊥ and . For example, it is possible to state in EL that some concepts are disjoint (e.g., Entree Dessert ⊥), specify subsumption relationship between concepts (Dumplings Entree Gnocci) or domains of relations (∃hasIngredient. F ood), and use existential restriction to specify relationships of other kinds (e.g., Salad ∃hasDressing. , ∃hasIngredient.M eat N onV egeterianF ood). The expressive features of EL although limited (e.g., negation/disjunction of concepts is not allowed), are sufficient to capture a great variety of ontologies. Most of the biomedical ontologies published on the Web fall within the formalism of EL, which underpins the OWL 2 EL profile of the Web Ontology Language.

Techniques
In the Description Logic EL, concepts are built using a countably infinite alphabet of roles names N r and concept names N c , with two distinguished concepts ⊥, ∈ N c . The notion of concept is defined inductively: any element of N c is a concept and if C, D are concepts and r ∈ N r is a role then C D and ∃r.C are concepts. A concept inclusion is an expression of the form C D, where C, D are concepts. A concept equivalence is a expression C ≡ D. An ontology is a finite set of concept inclusions and equivalences (called axioms). A signature is a subset of N r ∪ N c \ {⊥, }. The signature of a concept C, denoted as sig (C), is the set of role and concept names (excluding ⊥ and ), which occur in C. The signature of a concept inclusion or ontology is defined similarly. Semantics is defined by using the notion of interpretation, which is a pair I = ∆, · I , where ∆ is a universe and · I is a function which maps every concept name from N c to a subset of ∆ such that (⊥) I = ∅, ( ) I = ∆, and every role name to a subset of ∆ × ∆. This function is extended to arbitrary concepts by setting (C D) I = C I ∩D I and (∃r.C) I = {x ∈ ∆ | ∃y x, y ∈ r I and y ∈ C I }. Let Σ be a signature. We say that a concept C is Σ-definable wrt an ontology Ø if Ø |= C ≡ D, where sig (D) ⊆ Σ. The concept D is called Σ-definition of C (wrt ontology Ø). For example, the concept Dumplings Entree is Σ-definable wrt the ontology from the introduction, where Σ = {Gnocci}. It is known that in EL a concept C is Σ-definable wrt an ontology Ø iff it holds Ø ∪ Ø * |= C C * , where Ø * and C * are "copies" of Ø and C, respectively, obtained by an injective renaming of all non-Σ-symbols into "fresh" ones, not occurring in Ø and C. Indeed, if Ø |= C ≡ D, for some concept D, with sig (D) ⊆ Σ, then it holds Ø |= C D and Ø * |= D C * , which means Ø ∪ Ø * |= C C * . The converse can be proved constructively by computing the corresponding concept D from a proof of the inclusion C C * from Ø ∪ Ø * ; we provide a justification below. Various proof systems have been proposed for the Description Logic EL in the literature. For example, it follows from the results in [1] that the following set of inference rules is sound and complete for entailment of concept inclusions C D from an ontology Ø, where C and D occur in the axioms of Ø:

. Basic inference rules for reasoning in EL
An inference is a triple rule name, premises, conclusion of the form R, {ϕ 1 , .., ϕ n }, ψ , where n 0 and ψ is obtained by an inference rule R with premises ϕ 1 , , . . . , ϕ n . A proof of a concept inclusion ψ (from an ontology Ø) is a set of inferences {ι 1 , . . . , ι n }, where n 1, such that ψ is the conclusion of ι n and for all k = 1, . . . , n and any axiom ϕ, if ϕ is a premise of ι k , then there is a unique j < k such that ϕ is the conclusion of ι j and if ϕ is the conclusion of ι k and k = n then there is l > k such that ϕ is a premise of ι l . Observe that due to the injective renaming of non Σ-symbols it holds sig (Ø) ∩ sig (Ø * ) ⊆ Σ and whenever a concept C occurs in ontology Ø, we have sig (C) ⊆ sig (Ø) and hence, sig Proof. We note the following property (referred to as ), which immediately follows from the definition of the inference rules: if there is a proof of a concept inclusion C E from an ontology Ø then either it is obtained by one of the rules R , R ⊥ , R ⊥ ∃ , or E occurs in C or Ø. We use induction on the number of inferences in a proof ι i , . . . , ι n of a concept inclusion ϕ = C 1 which is an interpolant for ϕ. If i = 1 then sig (E 1 ) ⊆ sig (Ø 2 ) yields sig (E 1 ) ⊆ Σ and hence, E 1 is an interpolant for ϕ. Finally, if the rule is R ∃ then it follows from ( ) that sig (∃r.E) ⊆ sig (Ø i ), for some i = 1, 2. If i = 2 then there is an interpolant for C ∃r.E, which is an interpolant for ϕ. If i = 1 then it follows from the condition sig (∃r.F ) ⊆ sig (Ø 2 ) that r ∈ Σ and by the induction assumption there is an interpolant D for E F . Then ∃r.D is an interpolant for ϕ.
The proof of the theorem gives an idea of a recursive algorithm for computing interpolants and hence, concept definitions, by traversing proofs of C C * from the union Ø Ø * . In general, there can exist several proofs and each of them can yield a different definition of the concept C. Although the idea is simple, its implementation is not straightforward. First, it requires an ontology reasoner, which is not only able to decide entailment of concept inclusions from an ontology, but supports proof tracing, i.e., provides proofs as certificates for entailment. Second, the method presented by Theorem 1 has to rely on a proof system implemented by a reasoner. DeFind employs ELK [1], which is a highly optimized reasoner for the Description Logic EL and its extensions. The add-ons to ELK, which provide proof tracing and explanation services, employ the set of inference rules given in Figure 2. Showing a direct analogue of Theorem 1 for this proof system is not straightforward, since (in contrast to the rules from Figure  1) there exist proofs, from which an interpolant can not be directly computed. However, it can be shown that there always exists (at least a single) proof, which is appropriate for computing interpolants and hence, concept definitions.
DeFind implements a recursive procedure, which traverses proofs obtained by using the tracing service for ELK reasoner. Proofs are built for the entailment Ø ∪ Ø * |= C C * , where Ø * and C * are "copies" (of a given ontology Ø and concept C) constructed wrt a specified signature Σ. The procedure applies recursively the rules below to compute a label expression L(ϕ) for every concept inclusion ϕ appearing as the conclusion of an inference and outputs a label computed for C C * . Whenever there are several proofs for the same ϕ, each of them is traversed. A label is a concept formulated in an extension of EL with disjunction (denoted as EL ) and a distinguished "empty" concept , for which the following holds: D = , D = D, ∃r. = , and ∃r.(D E) = ∃r.D ∃r.E, for any concepts D, E and role r. By using the latter equation, the notion of Disjunctive Normal Form of a EL -concept is naturally defined. We say that a label expression is empty if it equals . Initially the label of every conclusion appearing in a proof is assumed to be empty. Each rule below is provided with a name and gives a label to the conclusion ϕ of an inference being visited during proof traversal, depending on the type of the inference rule and the labels of its premises. We use the notations from Figure 2 for the premises of each inference rule mentioned below: Theorem 2. Let Σ be a signature, Ø ontology, and C a concept occurring in Ø. The concept C is Σ-definable wrt Ø iff the procedure returns a non-empty EL -expression L(C C * ). Every conjunct from the Disjunctive Normal Form of L(C C * ) is a EL-concept and it is a Σ-definition of C wrt Ø.

Complexity of Definitions
We now estimate the size and the number of definitions computed by DeFind. The above mentioned procedure recursively computes labels for conclusions of inferences appearing in proofs. Under the assumption that every proof is computed in polynomial time in the size of an input ontology Ø (which is true when using the ELK reasoner), the size of every proof is polynomially bounded by the size of Ø. For any conclusion, the label is computed once, when traversing a single proof. The rules (L ⊥ ), (L Σ ) give a label concept from a conclusion of some inference and hence, its size is bounded by the size of Ø. Every other rule of the procedure gives a label, which is obtained as a combination (under , , or ∃r., with r ∈ sig (Ø)) of k expressions computed at the previous steps of the recursion, where k 1 is the number of premises of an inference rule and hence, k is bounded by the size of the proof. In particular, the rules L , L + give a label, which is at most k times longer than the labels of the premises of S , S + . Therefore, the size of any label computed from a single proof is at most exponential in the size of the ontology. Since every proof is polynomially bounded, there are at most exponentially many proofs for any conclusion and hence, the output of the procedure has at most exponential size. By Theorem 2, every conjunct from the DNF of the output label is a definition and therefore, the upper bound on the number of definitions computed by DeFind is double exponential in the size of the ontology. To estimate the size of the computed definitions one can w.l.o.g. assume that every rule of the procedure gives a label in DNF and show the following by induction. Every conjunct from a label obtained by some rule of the procedure is either a concept from a conclusion of an inference from a proof, or a combination (under , , or ∃r.) of conjuncts from the labels computed at the previous steps. Therefore, the size of every definition is at most exponential in the size of the input ontology. We now show that these bound are tight by giving an example of an ontology Ø, concept C, and a signature Σ such that there is a double exponential number of shortest Σ-definitions of C wrt Ø, where every definition has size exponential in the size of Ø. Let Σ = {r, s, D 1 , D 2 }, C = A 0 , and for n 1, let Ø consist of axioms: Converting this expression into DNF gives four Σ-definitions of A n−1 wrt Ø, i.e., concepts ∃r.D i ∃s.D j , where i, j = 1, 2. Similarly, A 0 is equivalent wrt Ø to a EL -concept, which has 2 n occurrences of D 1 D 2 . Converting this concept into DNF gives a double exponential number of Σ-definitions of A 0 wrt Ø and it can be shown that no shorter Σ-definitions exist.

Features of DeFind
DeFind (available at https://github.com/stiv-yakovenko/defind) requires the ELK reasoner [1] and proof explanation plugin [2] for Protégé. The interface of DeFind is given in Figure 4. The screenshot shows Σ-definitions of concept ∃r.A 1 ∃s.A 1 computed by Defind wrt ontology Ø and signature Σ from the previous section for n = 1. The user can input a complex concept in the Manchester OWL Syntax into the field "Class expression" or drag-and-drop a concept name from the class hierarchy of the ontology. To specify concept and role names for the target signature, one can drag-and-drop items from the class or object property hierarchy. One can simultaneously add all role names from the ontology into the target signature by pressing "Add all Object Properties" button. Selecting "doesn't include symbols" option sets the target signature to consist of all those concept an role names from the ontology, which are not listed in the "Target signature" field. On pressing "Compute definitions", the corresponding Σ-definitions are computed (or a notification is shown if no definition exists). On pressing the question mark at the right-hand side of a definition, an explanation is shown, why it corresponds to the specified class expression: the Protégé proof explanation plugin is called to visualize a proof (see, e.g., Figure 5 in [2]) of the equivalence of the class expression to the concept computed by DeFind.

Related Work
In [3], a similar approach is implemented to compute concept definitions from tableaux proofs in the Description Logic ALC and its extensions. The authors provide a constructive proof of an analogue of Theorem 1 and derive an algorithm, which computes a definition of at most double exponential size, whenever there exists one in a target signature. This bound is tight and is one exponential larger than the size of the shortest definitions in EL. It is known that general tableaux methods, when applied to EL, provide exponentially longer proofs than the ones obtained in the proof systems from this paper. It should be noted that the algorithm from [3] computes a single definition from a proof, whereas DeFind computes several definitions, the number of which is bounded by a double exponential in the size of the ontology. DeFind explores all proofs provided by a reasoner and traversing a single proof can potentially give several definitions for a concept of interest. In [4], the authors propose an algorithm, which finds a single concept definition in a signature of interest wrt a normalised EL-ontology. The algorithm computes an algebraic representation of an ontology as a canonical model provided with an information on how each element of the model is obtained. Essentially, it implements the two features, which are required for computing concept definitions, i.e., ontology reasoning and proof tracing. In contrast, DeFind relies on external reasoning and proof tracing services. The question whether it suffices to compute a single concept definition strongly depends on application. For instance, the method from [3] is employed in [5] to compute query reformulations. In [6], checking for existence of a concept definition (or computing a single one) is used for ontology decomposition. In both applications, the quality of the obtained result is strongly related to the form of a computed definition. On the other hand, it is argued in [7] that having multiple definitions is helpful in the context of ontology alignment, since having a choice of several (semantically equivalent, but syntactically different) definitions facilitates finding matches between concepts from different ontologies. The authors propose a heuristic approach for computing concept definitions based on examination of concept definition patterns, which typically occur in ontologies. This solution does not employ ontology reasoning and is in general faster, but it can miss some definitions computed by the methods that employ proof tracing.
The exponential lower bound for the size and number of shortest concept definitions is shown in this paper by an artificial ontology example. However it demonstrates the natural phenomenon: some concepts can be used as auxiliary ones in ontology to make definitions shorter. If one asks whether there is a definition, which does not contain certain concept or role names, then one may get a positive answer, but the obtained definition may be long and not easy to comprehend. It is to be understood whether a significant increase of definition size can happen in real-world ontologies. Further, it may be important to develop techniques that help to automatically suggest extensions of the target signature, when a blow-up is unavoidable. One of the primary goals of further implementation is to support other language features of OWL 2 EL profile of the Web Ontology Language, e.g., inclusion and composition of roles. These features are particularly interesting, because on one hand they are frequently used in ontologies and on the other hand, Theorem 1 is no longer true for EL extended with these features. Finally, there is a room for optimizations for DeFind. If the plugin is used extensively to compute definitions of the same concept wrt different signatures then it makes sense to implement optimizations proposed in [4], which employ incremental reasoning to reduce computation overhead, when only a small part of the input is changed.


extfieldsofstudy:
Computer Science
Mathematics

text:
Adversarial Autoencoders for Generating 3D Point Clouds

Deep generative architectures provide a way to model not only images, but also complex, 3-dimensional objects, such as point clouds. In this work, we present a novel method to obtain meaningful representations of 3D shapes that can be used for clustering and reconstruction. Contrary to existing methods for 3D point cloud generation that train separate decoupled models for representation learning and generation, our approach is the first end-to-end solution that allows to simultaneously learn a latent space of representation and generate 3D shape out of it. To achieve this goal, we extend a deep Adversarial Autoencoder model (AAE) to accept 3D input and create 3D output. Thanks to our end-to-end training regime, the resulting method called 3D Adversarial Autoencoder (3dAAE) obtains either binary or continuous latent space that covers much wider portion of training data distribution, hence allowing smooth interpolation between the shapes. Finally, our extensive quantitative evaluation shows that 3dAAE provides state-of-the-art results on a set of benchmark tasks.

Introduction
Creating useful and compact data representations is one of the main challenges tackled by machine learning and computer vision. Although learning various (binary and continuous) representations for 2D images has been extensively investigated [3,9,14,18,20,21,22], so far relatively little attention was paid to representations of three dimensional shapes and structures [1,5,13,19].
As more and more sensors offer capturing depth along with other visual cues, three dimensional data points start to play a pivotal role in many real-life applications, including simultaneous localization and mapping or 3D object detection. Proliferation of devices such as RGB-D cameras and LIDARs leads to increased amount of 3D data that is being captured and analysed, e.g. by autonomous cars and robots. Since storing and processing 3D data points in their raw form quickly becomes a bottleneck of a processing system, compact and efficient representations are needed. Generative models, such as those inspired by GANs [6], can learn such representations in an unsupervised manner which reduces annotation and labeling efforts. Furthermore, those models are able at the same time and no additional cost to provide tooling for synthetic generation and augmentation of existing datasets. This, in turn, can be helpful for training more advanced and effective machine learning algorithms, e.g. designed for 3D object detection.
Most of the contemporary works on 3D shape representations learn them using voxel-, view-and point-based projections [19,5,1] and we follow this approach in this paper. The main advantage of such 3D point cloud representations is their similarity to the 3D objects present in real life, however processing them can be cumbersome due to their invariance to permutation.
Due to the complex nature of 3D representations, several approaches based on deep neural networks have been proposed [1,5,13,16,19]. In [19], the authors propose an extension of a standard GAN architecture [6] that allows to generate realistic 3D shapes sampled from a manifold of latent variable space. PointNet model [13], on the other hand, provides a universal architecture to input 3D points in a permutation invariant manner and we incorporate this work in our model. [16] uses a version of Variational Autoencoder [9] to build a semantic representation of a 3D scene that is later used for relocalization in SLAM.
Perhaps the most relevant to our work is [1] where the authors propose a method for encoding and generating 3D point clouds. Their cascaded architecture consists of two separate modules: the autoencoder trained to obtain a latent representation and a corresponding generative model to transform the latent space into a 3D shape. Since those two models are trained separately, both sampling and coding representations are different and cannot be translated or interpreted within both spaces.
In this work, we address this limitation of the existing method and introduce the first end-to-end 3D point cloud generative model called 3D Adversarial Autoencoder (3dAAE) that is capable of creating smooth transitions between database objects. This functionality is available when sampling latent variable space modelled with this approach, since 3dAAE allows for much wider coverage of the training dataset manifold of 3D shapes. More precisely, thanks to introducing Earth-Mover loss into an Adversarial Autoencoder scheme connected with a PointNet module, we are able to increase the granularity of the latent space used by the generative part of the model to create point cloud. As a result, our proposed 3dAAE model offers state-of-the-art results in terms of generation and retrieval, as well as realistic generation capabilities and latent variable space arithmetics.
To summarize, in this work we present the following contributions: • We show that variational autoencoders can be applied directly on encoding space with no significant decrease in reconstruction and generative capabilities of the model.
• We introduce adversarial autoencoders for 3D point clouds that are capable to learn any distribution on latent space.
• We show how adversarial autoencoders can solve challenging tasks, such as 3D points clustering or 3D object retrieval using binary embeddings.
Our work is organized as follows: Section 2 presents preliminary information and notation used in the paper. Section 3 outlines generative models upon which we build our proposed model. In Section 4 we introduce our approach for learning latent representations of point clouds. Section 5 contains thorough evaluation of our model with quantitive and qualitive results. The paper is summarized and concluded in Section 6.

Preliminaries and Notation
In this section we provide necessary definitions and present metrics used to compare similarities between two point clouds that are used for model training. We conclude this section with an explanation of the notation used in subsequent sections.
A point cloud, which we will denote by s, is a n × 3 matrix, where each row represent a point in a 3D euclidean space.
Earth Mover's Distance (EMD): introduced in [15] is a metric between two distributions based on the minimal cost that must be paid to transform one distribution into the other. For two equally sized subsets s 1 ⊆ R 3 , s 2 ⊆ R 3 , their EMD is defined as: where φ is a bijection. Chamfer pseudo-distance (CD): measures the squared distance between each point in one set to its nearest neighbor in the other set: (2) In contrast to EMD which is only differentiable almost everywhere, CD is fully differentiable. Additionally, CD is computationally less requiring.
In the rest of our work, we use bold lower-case letters, such as s to represent point clouds and lower-case letter, such as x, to represent vectors. Finally, upper-case italic letters such as E, G or D denote model components.

Variational Autoencoders
Variational Autoencoders (VAE) are the generative models that are capable of learning approximated data distribution by applying variational inference [9].
We consider the latent stochastic space z and optimize the upper-bound on the negative log-likelihood of x: where KL is the Kullback-Leibler divergence, p d (x) is the empirical distribution, q(z|x) is the variational posterior (the encoder E), p(x|z) is the generative model (the generator G) and p(z) is the prior. In practical applications p(x|z) and q(z|x) are parametrized with neural networks and sampling from q(z|x) is performed by so called reparametrization trick. The total loss used to train VAE can be represented by two factors: reconstruction term, that is 2 norm taken from the difference between sampled and reconstructed object if p(x|z) is assumed to be normal distribution and regularization term that forces z generated from q(z|x) network to be from a prior distribution p(z).

Adversarial Autoencoders
The main limitation of VAE models is that regularization term requires particular prior distribution to make KL(· ·) divergence tractable. In order to deal with that limitation authors of [12] introduced Adversarial Autoencoders (AAE) that utilize adversarial training to force a particular distribution on z space. The model assumes that an additional neural network -discriminator D, which is responsible for distinguishing between fake and true samples, where the true samples are sampled from assumed prior distribution p(z) and fake samples are generated via encoding network q(z|x). The adversarial part of training can be expressed in the following way: The training procedure is characteristic for GAN models and is performed by alternating updates of parameters of encoder E and discriminator D. The parameters of discriminator D are updated by minimizing the L D = −V (E, D) and the parameters of encoder E and generator G are optimized by minimizing the reconstruction error together with V (E, D): L EG = reconstruction + V (E, D). In practical applications, the stated criterion can be substituted with so called Wasserstein criterion [7].
Learning prior on z latent space using adversarial training has couple of advantages over standard VAE approaches [12]. First of all, the data examples coded with the encoder exhibits sharp transitions indicating that the coding space is filled which is beneficial in terms of interpolating on the latent space. Secondly, there are no limitation for the distribution that is adjusted to z space. Figure 2. 3dAAE model architecture that extends AE with an additional decoder D. The role of the decoder is to distinguish between true samples generated from p(z) and fakes delivered by the encoder E. Encoder is trying to generate artificial samples, that are difficult to be distinguished by the discriminator.

Adversarial Autoencoders for 3D point clouds
The superior generative power of GAN models [11] over classical autoencoders in terms of generating artificial images is mainly caused by the difficulties in defining good distance measure in data (pixel) space that is essential for the encoders. Thanks to the distance measures, like Chamfer of Earth-Mover, this limitation is no longer observed for 3D point clouds. Therefore, we introduce VAE and AAE models for 3D point clouds and call them 3dVAE and 3dAAE, respectively. VAE for 3D point clouds (3dVAE) assumes an additional KL(· ·) regularization term in training the AE model that enforces latent space z to be from the assumed prior. The training criterion for the model is composed of reconstruction error defined with Earth-Mover distance between original and reconstructed samples, and KL(· ·) distance between samples generated by encoder and the samples generated from prior distribution. Samples from the encoder are obtained by application of reparametrization trick on the last layer. To balance the gap caused by the orders of magnitude between the components of the loss we scale the Earth-Mover component by multiplying it by the scaling parameter λ.
Due to the limitations of VAE listed in the previous section, namely narrow spectrum of possible priors and worse distribution adjustment, we propose the adversarial approach adjusted to be applied to 3D point clouds (3dAAE). The scheme of adversarial autoencoder for 3D point clouds is presented in Figure 2. The model is composed of an encoder E that is represented by PointNet [13] Figure 3. t-SNE plot for the latent space obtained from AE and 3dAAE models (chair category). One can notice the interpolation gap between two chairs for AE. For encodings obtained from 3dAAE model this phenomenon is not observed and the latent variable space is much more dense which allows for smooth transition within the space. architecture and transforms 3D points into latent space z. The latent coding z is further used by generator G to reconstruct or generate 3D point clouds. To train the assumed prior distribution p(z) we utilize a discriminator D that is involved in the process of distinguishing between true samples generated from prior distribution p(z) and fake samples obtained from encoder E. If z is either normal distribution or Mixture of Gaussians we apply reparametrization trick to the encoder E to obtain z samples.
The model is trained in the adversarial training scheme describe in details in Section 3.2. As a reconstruction loss we take Earth-Mover loss described in Section 2. For the GAN part of training we utilize Wasserstein criterion.
In Figure 3 we present the 2D visualization of the coding space for AE and 3dAAE methods. For 3dAAE model we can observe, that the encoding are clustered consistently to the prior distribution. For the AE model we can find the gaps in some spaces that may lead in poor interpolation results.
Contrary to the stacked models presented in [1] our model is trained in end-to-end framework. The latent coding space that is used for both representation and sampling purposes. Thanks to the application of adversarial training we obtain data codes that are consistent with the assumed prior distribution p(z).

Evaluation
In this section we describe experimental results of the proposed generative models in various tasks including 3D points reconstruction, generation, binary representation and clustering.

Metrics
Following the methodology for evaluating generative fidelity and samples diversification provided in [1] we utilize the following criteria for evaluation: Jensen-Shannon Divergence, Coverage and Minimum Matching Distance.
Coverage (COV): measure of generative capabilities in terms of richness of generated samples from the model. For point cloud sets A and B coverage is defined as a fraction of point clouds in B that are in the given metric the nearest neighbor to some point cloud in A.
Minimum Matching Distance (MMD): Since COV only takes the closest point clouds into account and does not depend on distance between the matchings additional metric was introduced. For point cloud sets A and B MMD is a measure of similarity between point clouds in A to those in B.
Both COV and MMD can be calculated using Chamfer (COV-CD, MMD-CD) and Earth-Mover (COV-EMD, MMD-EMD) distances, respectively. For completeness we report all possible combinations.

Network architecture
In all of our experiments we use the following network architectures: • Encoder (E) is a PointNet network composed of five conv1d layers, one fully-connected layer and two separate fully-connected layers for reparametrization trick. ReLU activations are used for all except the last layer used for reparametrization.
• Generator (G) is fully-connected network with 5 layers and ReLU activations except the last layer.
• Discriminator (D) is fully-connected network with 5 layers and ReLU activations except the last layer. For training we use Adam [8] optimization algorithm with the following values of hyperparameters: learning rate equal to 0.0001 and β1 value equal to 0.5 and β2 value equal to 0.999. In all experiments we use scaling parameter λ that indicates the impact of reconstruction error in aggregated loss is equal 0.05.

Experimental setup
For all of the experiments we use ShapeNet dataset [4] transformed to the 3 × 2048 point cloud representation following the methodology provided in [1]. Unless otherwise stated, we train models with point clouds from a single object class and work with train/validation/test sets of an 85% − 5% − 10% split. When reporting JSD measurements we use a 28 3 regular voxel grid to compute the statistics.

Models used for evaluation
The following reference models introduced in [1] are considered in experiments: • Autoencoder (AE). Simple architecture of autoencoder that converts input point cloud to the bottleneck representation z with encoder. The model is used for representing 3D points in latent space without any additional mechanisms that can be used to sample artificial 3D objects. Two approaches to train AE are considered: 1) with Chamfer (AE-CD) or 2) Earth-Mover (AE-EMD) distance as a way to calculate reconstruction error.
• Raw point cloud GAN (r-GAN). Basic architecture of GAN, that learns to generate point clouds directly from the sampled latent vector.
• Latent-space (Wasserstein) GAN (l-(W)GAN). Extended version of GAN trained in stacked mode on la-tent space z with and without an application of Wasserstein criterion [2].
• Gaussian mixture model (GMM). Gaussian Mixture of Models fitted on the latent space of an encoder in the stacked mode.
Finally, we also evaluate the models proposed in this work as well as their variations: • Variational Autoencoder (3dVAE). Autoencoder with EMD reconstruction error and KL(· ·) regularizer.
• Adversarial Autoencoder. Adversarial autoencoder introduced in Section 4 that make use of prior p(z) to learn the distribution directly on latent space z. Various types of priors are considered in our experiments: normal distribution (3dAAE), mixture of Gaussians (3dAAE-G).
• Categorical Adversarial Autoencoder (3dAAE-C). AAE model with and additional category output returned by encoder for clustering purposes (see Section 5.9).

Reconstruction capabilities
In this experiment we evaluate the reconstruction capabilities of the proposed autoencoders using unseen test examples. We confront the reconstruction results obtained by AE model with our approaches to examine the influence of prior regularization on reconstruction quality. In Table 1 we report the MMD-CD and MMD-EMD between reconstructed point clouds and their corresponding ground-truth in the test dataset of the chair object class. It can be observed, that 3dVAE model does not suffer from overregularization problem raised in [1]. Both reconstruction measures are on the comparable level or even slightly lower for

Method
MMD-CD MMD-EMD AE [1] 0 3dAAE-G. For qualitative analysis (see Figure 5) we use our 3dAAEs to encode unseen samples from the test split (bottom row) and then decode and compare them visually to the input (top row).

Generative capabilities
We present the evaluation of our models, that are involved in sampling procedure directly on z latent space and compare them with the generative models trained in stacked mode basing on the latent representation of AE.
For evaluation purposes we use chair category and the following five measures: JSD, MMD-CD, MMD-EMD, COV-CD, COV-EMD. For each of the considered models we select the best one according to the JSD measure on validation set. To reduce the sampling bias of these measurements each generator produces a set of synthetic samples that is 3x the population of the comparative set (test or validation) and repeat the process 3 times and report the averages.
In Table 2 we report the generative result for memorization baseline model, 5 generative models introduced in [1] and three our approaches: 3dVAE, 3dAAE and 3dAAE-G. A baseline model memorizes a random subset of the train-ing data of the same size as the other generated sets. For 3dAAE-G model we fix the number of Gaussian equal 32 with a different mean values and fixed diagonal covariance matrices.
It can be observed, that all of our approaches achieved the best results in terms of JSD measure. Practically, it means that our models are capable to learn better global statistics for generated point locations than reference solutions. We also noticed the slight improvement on MMD criteria for both of the considered distances. In terms of coverage criteria the results are comparable to the results obtained by the best GAN model and GMM approach.
In Table 3 we present an additional results on four categories: car, rifle, sofa and table. For further evaluation we use MMD-EMD and COV-EMD metrics. 3dAAE-G model achieved the best results considering MMD-EMD criterion for each of the datasets and the highest value for three of them. Practically, it means that the assumed Gaussian model with diagonal covariance matrix is sufficient to represent the data in latent space and training GMM in stacked mode is unnecessary when adversarial training with fixed prior is performed. In order to present qualitative result we provide synthetic samples generated by the model in   Table 2. Evaluating generative capabilities on the test split of the chair dataset on epochs/models selected via minimal JSD on the validation-split. We report A) sampling-based memorization baseline and the following reference methods from [1]:

Latent space arithmetic
One of the most important characteristic of well-trained latent representations is its ability to generate good-looking samples based on embeddings created by performing interpolation or simple linear algebra. It shows, that model is able to learn distribution of the data without excessive under-or overfitting [17].  In Figure 4 we show that interpolation technique in the latent space produces smooth transitions between two distinct types of the same-class objects. It is worth mentioning that our model is able to change multiple characteristics of objects at once, e.g. shape and legs of the table. Figure 6 presents model ability to learn meaningful encodings that allows to perform addition and subtraction in latent space in order to modify existing point clouds. In this examples, we were able to focus on specific feature that we want to add to our initial point cloud, while leaving other characteristics unchanged. Moreover, the operations were done by using only one sample for each part of the transformation.

Learning binary embedding with AAE models
In this section we present the results for learning binary feature embeddings. We make use of the benefit of using Figure 7. 3dAAE-C model architecture that extends 3dAAE with an additional decoder Dc that enable to learn an additional categorical representation y. The encoder is involved in two adversarial trainings to learn both categorical (y) and numerical (z) representations. arbitrary selected prior distribution during the adversarial training to learn informative and diverse binary features. To achieve the stated goal we propose to sample z codes from Beta distribution that accumulates probability mass around 0 or 1 (by selecting low values of α and β hyperparameters) and sample the binary codes directly from Bernoulli distribution.
We examine the quality of the approaches for retrieval task taking under consideration mean average precision (mAP) as quality criterion. For each of the considered models we select the best model according to the mAP value on validation set.
The results obtained on test set are reported in Table 4. We present the results both for numerical and binarized z values. The binarization is performed simply by taking threshold value equal 0 for 3dAAE and 0.5 for 3dAAE-Beta and 3dAAE-Bernoulli.
It can be observed, that models that force the diversity of coding space (3dAAE-Beta, 3dAAE-Bernoulli) achieved significantly better retrieval results than the models without these mechanisms (AE, 3dAAE). In this subsection we introduce the extension of adver-sarial model for 3D point clouds (3dAAE-C) inspired by [12], that incorporates an additional one-hot coding unit y. This unit can be interpreted as a indicator of an abstract subclass for the 3D objects delivered on the input of the encoder.

Clustering 3D point clouds
The architecture for this model is provided in Figure 7 and extends the existing model (see Figure 2) with an additional discriminator D c . The role of the discriminator is to distinguish between noise samples generated from categorical distribution and one-hot codes y provided by the encoder. During the training procedure the encoder is incorporated in additional task in which it tries to full the discriminator D c to create samples from the categorical distribution. As a consequence, encoder is setting 1 value for the characteristic subcategories of the objects in the coding space z.
In Figure 8 we present the qualitative clustering results for chair test data. We trained the categorical adversarial autoencoder on chair dataset. We set the number of potential clusters to be extracted by our model to be equal 32. We selected 4 most dominant clusters and presented 6 randomly selected representatives for each of the them. It can be observed, that among the detected clusters we can observe the subgroups of chairs with characteristic features and shapes.

Conclusions
In this work we proposed an adversarial autoencoder for generating 3D point clouds. Contrary to the previous approaches [1] our model is an end-to-end 3D point cloud generative model that is capable to represent and sample artificial data from the same latent space. The possibility of use various priors in adversarial framework makes model useful not only for representation and generative purposes, but also in learning binary encoding and discovering hidden categories.
To show numerous capabilities of our model we provide various of experiments in terms of 3D points reconstruction, generation, retrieval and clustering. The results of the provided experiments confirm the good quality of the model in the mentioned tasks competitive for existing state-of-the-art solutions.