{'fraction_non_alphanumeric': 0.036101083032490974, 'fraction_numerical': 0.009257823746982348, 'mean_word_length': 4.7161666033675145, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Decision Tree Learning with Spatial Modal Logics

Symbolic learning represents the most straightforward approach to interpretable modeling, but its applications have been hampered by a single structural design choice: the adoption of propositional logic as the underlying language. Recently, more-than-propositional symbolic learning methods have started to appear, in particular for time-dependent data. These methods exploit the expressive power of modal temporal logics in powerful learning algorithms, such as temporal decision trees, whose classification capabilities are comparable with the best non-symbolic ones, while producing models with explicit knowledge representation. With the intent of following the same approach in the case of spatial data, in this paper we: i) present a theory of spatial decision tree learning; ii) describe a prototypical implementation of a spatial decision tree learning algorithm based, and strictly extending, the classical C4.5 algorithm; and iii) perform a series of experiments in which we compare the predicting power of spatial decision trees with that of classical propositional decision trees in several versions, for a multi-class image classification problem, on publicly available datasets. Our results are encouraging, showing clear improvements in the performances from the propositional to the spatial models, which in turn show higher levels of interpretability.


Introduction
Connectionist learning has been the driving force of machine learning for at least a decade, allowing advances in many difficult artificial intelligence tasks. Recently, however, we have seen a rising need for models that are interpretable and explainable, and it has been pointed out that, despite their potential and versatility, neural models often enclose complex algebraic functions that are difficult to interpret; such a need is even reflected in recent political initiatives (see, e.g., the 2016 General Data Protection Regulation -GDPR -of the European Union). A well-known approach to interpretable modeling is based on replacing the algebraic language that underlies a model with a logical language, and this foundational choice leads to the field of symbolic learning. As opposed to functional learning, where the learned model is an algebraic function, symbolic models are structures of logical formulas that are directly translatable to natural language. While logical languages make up a whole research field, in which languages are studied and categorized according to their expressive and computational properties, symbolic learning has always been limited to the use of propositional and first-order languages. Symbolic learning at the propositional level is very well-known, and includes a plethora of widely used methods ranging from decision trees to rule-based models; their clearest limit is the fact that complex relationships in data cannot be directly expressed. Symbolic learning at the first-order level is known as inductive logic programming (or ILP), and it is based on the assumption that entities and relationships in data are explicit. The limit of inductive logic programming is the fact that the extracted models are often very complex, and generally expressed in terms of logic programs, which is not suitable in many practical cases.
An alternative to both propositional and first-order symbolic learning is modal symbolic learning, which is emerging in the past few years. The idea is to re-design and generalize classical symbolic algorithms to exploit the expressive power of modal logics [7], which are more expressive than propositional ones but less than first-order ones. Modal logics are tailored to describe dimensional data in which the dimension(s) are implicit. Typical examples of modal logics are temporal and spatial logics. Temporal symbolic learning has been first presented in this form in [13,43,44], where the authors study the use of a temporal modal logic (in particular, Halpern and Shoham's logic of time intervals, or H S [21]) in order to learn temporal decision trees for multivariate time-series classification. Among the several examples of multivariate time-series classification models that can be extracted with these techniques in the form of trees or sets of rules, consider the illuminating example of the medical context, in which patients under observation for a period of time may be classified by patterns of the form if there exists an interval in time in which the body temperature is higher than 39, overlapped by an interval where heart rate is higher than 140 then the patient has a certain condition. The interval-based approach turns out to be very natural, allowing one to make decisions that are essentially not point-based (in our example, evaluating the temperature of a patient at a single moment is not really significative). Although this idea is still in its infancy, the initial results seem to indicate that the learned models are competitive, in statistical terms, with those that belong to more classical approaches (both symbolic and functional), while showing a high level of interpretability.
In this paper, we apply the same approach to the spatial domain by extending a classical decision tree learning algorithm, namely C4.5 [37], to allow it to pick up spatial patterns and describe them in terms of spatial relations between entities in a geometric space. While interval logic is the most natural choice to describe extended patterns in the single-dimensional (i.e., temporal) case, a wide range of possibilities arises with more than one dimensions: in fact, there exist several spatial logics characterized by their underlying ontology, represented by the choice of what constitutes spatial entities (e.g., triangles, rectangles, generic areas, and so on) and relations (e.g., containing, next to, to the right of, and so on). However, it turns out that generalizing interval temporal logic to many dimensions captures many of these choices, and it presents itself as a suitable compromise between a simple enough syntax and a high enough expressive power. Following the same interval-based approach as in the temporal case, in two dimensions intervals are replaced by rectangles, and our models can learn to classify an image according to whether it displays a pattern such as, for example, there exists a region in the image with a high level of red, containing another region with a low level of green. Moreover, such an approach can be further generalized to many dimensions, which may be useful for learning from multi-dimensional data (e.g., hyperspectral video streams). After defining a generalized version of H S , we test our implementation in the bi-dimensional case on a land cover classification problem, using public benchmark datasets. Since in a typical setting models for this problem are required to be interpretable, land cover classification has been initially approached using (propositional) decision tree learning [20,51]; nevertheless, in recent times functional methods seem to have taken over [14,42]. Since functional methods are specifically designed to obtain the best statistical performances, even at the expense of the interpretability of the model, they are not immediately comparable with symbolic ones, and such a comparison would probably not be very significant. In this paper, we show how the spatial symbolic approach improves both the performances and the expressive power of the propositional one, and how a logical theory of the underlying phenomenon can be extracted, discussed, interpreted, and translated into natural language, which would not be possible with a functional method. Although they are not immediately comparable to our solution, which is part of a long-term project that aims at generalizing symbolic learning with modal logics in a comprehensive way, there have been attempts at logic-based spatial learning. Among them Graphical representation x y x y x y x y x y x y x y we mention [26], in which the authors extract a regression function that depend on the spatial relationships among objects in an image, and it is more database-oriented rather than a pure learning method, and [16], in which a customized ILP-like approach is used to extract knowledge from video instances (in some sense, this approach is vaguely comparable with ours, except it requires first-order description of the data before the learning can take place). Finally, in [8] the authors propose a methodology to extract first-order decision trees; such an approach is comparable with ours (as we extract propositional modal decision trees), but, once again, in their case relations are supposed to be explicit, so the two approaches cannot be immediately applied to the same situations.
This paper is organized as follows. In Section 2 we briefly review the most important ontologies of space and present a generalization of the interval temporal logic H S for multi-dimensional reasoning. In Section 3 we present a formalization of classical decision tree learning, and its generalization to the case of modal logics. Then, in Section 4 we present the land cover classification problem, and we evaluate the performances of spatial decision trees on this problem, using public datasets, before concluding.

Modal Logics of Space
Ontologies of space. Because qualitative spatial reasoning (QSR) has important real-world applications (e.g., in geographic information systems), there is active research in deriving formal systems for reasoning about space. Throughout the last 30 years, many formalizations have been proposed for different purposes [39], mostly in the form of binary spatial calculi, but sometimes also in logical terms. As mentioned, two major structural choices for deriving a spatial logic concern the definition of spatial entities, namely, regions, and the set of relevant binary relations between such entities. These choices are to be tailored to the domain at hand. Depending on the application, objects are classically chosen to be represented as points or regions of a specific kind (e.g., convex regions). Points are more elementary, and they cannot express the extension of objects, thus they are not suitable in contexts where objects have diverse shapes, or when mereological aspects of space are relevant (e.g., grade of overlap between regions). Regions, on the other hand, can express extension, but are more complex to deal with. When regions are considered, they are usually assumed to be connected, which is in agreement with an implicit locality hypothesis on the objects of the reasoning. Although limited in terms of expressive power, convex regions are typically preferred as extended entities, or they are used to approximate complex shapes (e.g., by means of convex hulls [15]). Bidimensional convex regions providing a good trade-off between complexity of reasoning and expressive power include triangles and convex quadrilaterals. Regions can be further constrained in order to achieve higher specificity or lower complexity; for example, forcing all entities to be of the same size can be beneficial for specific domains (e.g., optical character recognition). Another sensible constraint is orthogonality: in the case of polygons, forcing the edges to be parallel to a given reference set of axes limits the set of possible relations, and sometimes lowers computational costs; in particular, rectangles with edges parallel to the axes have been deeply used in QSR due to their computational benefits. As for relation sets, different aspects can be considered (e.g., distance, size, shape), and two of the most studied relational aspects are directionality and topology. Directional relations account for the relative spatial arrangement of the two objects (e.g., next to, to the right of); they are not invariant under rotation/reflection, and are not as easily definable for generic types of regions. On the algebraic side, many calculi have been proposed, both with punctual entities [18] and regions of various types [4,34,46,45]; directional algebras could, in principle, give rise to their modal logic counterparts, but only a few attempts have been made in this sense [12,28,30,32]. While in this context an absolute frame of reference is generally adopted, there are examples of spatial logics and calculi that account for the orientation of objects, and are able to describe relations such as in front of, behind or facing each other [19,47]. On the other hand, topological relations generally address the different modalities of intersection between regions and their boundaries, which makes them invariant under rotation and reflection; being purely qualitative and easily definable for generic regions, topology is the most common choice, and is often preferred to directional approaches. The most popular characterization of topological binary relations is the set of Egenhofer-Franzosa relations, often referred to as RCC8 [17,38]. In its extended form, the set includes the 8 relations: disconnected, externally connected, partially overlapping, tangential proper part, non-tangential proper part, tangential proper part inverse, non-tangential proper part inverse, and equality. RCC8 can be made coarser by using unions of relations; the natural resulting, smaller, set of relations is known as RCC5. In [25] the modal logics that are entailed by these sets of relations, namely L RCC8 and L RCC5 , are studied. Compared to topological relations, jointly exhaustive region-based directional algebras (namely, in which each pair of entities are in at least a relation) generally present a high number of relations. A spatial logic for learning. Learning is an inductive process. As such, the logical language on which a learning model is designed is interesting for properties other than deduction ones. Inspired by both Halpern and Shoham's interval temporal logic [21] and Rectangle Algebra [4], here we introduce a very general spatial logic based on hyperrectangles on a finite, multi-dimensional space. Let: be a finite, linearly ordered set, and let D k = D × . . . × D be a k-dimensional, finite and discrete geometrical space. Elements of D k are called points, and are denoted as π = (x 1 , . . . , x k ). In analogy with interval temporal logic, an hyperrectangle in D k is an object of the type: where for each i, x i < y i (observe that, using this notation, in the one-dimensional case hyperrectangles are just intervals in their familiar notation, that is, [x 1 , y 1 ], by simply omitting the inner brackets). Hyperrectangles are essentially the extension of intervals in a higher dimensional space; as such, the notion of π belonging to a hyperrectangle (π ∈ [(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x k , y k )]) can be defined using the ordering relation of D, and, in fact, different such notions can be defined depending on the particular application. Now, let K(D k ) be the set of all hyperrectangles that can be formed on D k ; in the following, we use r, s . . . to denote hyperrectangles. On a linear order, there are 13 distinct relations between any two intervals; these are commonly referred to as Allen's relations [2], and the set is given by the six relations After, Later, Begins, Ends, During, Overlaps, their inverses, and the equality relation. Note that all except for the equality are logically interesting, thus in a single dimension, we represent relations by a symbol R X , where X ∈ {A, L, B, E, D, O, A, L, B, E, D, O}; their informal semantics is depicted in Fig. 1, in which we used Halpern and Shoham's notation. In the multi-dimensional generalization, we represent any relation as a tuple of k single-dimension relations, that is, with the additional constraint that they cannot be all the equality (since, again, equality cannot be lifted to the level of logical modality). Ultimately, this leads to a number of 13 k − 1 distinct relations between any two hyperrectangles in a k-dimensional space. Lifting such relations at the modal level entails introducing unary modal operators of the type: ϕ : where p is a propositional letter from a given set P. Such formulas are easily interpreted in a kdimensional spatial model M = K(D k ),V , where V is an evaluation function defined as: which assigns to each hyperrectangle the set of all and only propositional letters that are true on it, by means of the following truth relation: where, r ∈ K(D k ). The universal version [X 1 , . . . , X k ] of an existential modality is defined in the standard way. When k = 1 the resulting logic is precisely Halpern and Shoham's H S , and when k = 2 we obtain the natural unary modal logic that emerges from Rectangle Algebra. Moreover, for any k, one can easily define derived relations (and thus, modal operators) through union (that is, disjunction); for example, for k = 2, the topological relation disconnected (usually denoted DC) can be defined as the following union: In a similar way, each of the RCC8 and RCC5 relations can be expressed as disjunctions of H S k operators; in fact, restricting the language to RCC8 or RCC5 modalities corresponds to obtaining Lutz and Wolter's L RCC8 and L RCC5 interpreted on rectangles. In these two last cases, we use the names H S 2 RCC8 and H S 2 RCC5 . While encompassing as much as 168 different modal operators, H S 2 is very intuitive; a pictorial example of the relations that can be expressed in H S 2 is shown in Fig. 2

(left). H S 2
RCC8 and H S 2 RCC5 feature only 7 and 4 modal operators, respectively; to ease the notation we use the original one, so that DC, for example, denotes the relation disconnected and DC its corresponding modal operator; examples are shown in Fig. 2 (right). Some known result. Although H S k has not been studied per se, the literature that concerns its fragments is very wide. Very briefly, it is worth recalling that satisfiability for H S , its one-dimensional version, is undecidable [21], and that various strategies have been considered in the literature to define fragments or variants of H S with better computational behaviour. These include constraining the underlying temporal structure [31], restricting the set of modal operators [1,9], softening the semantics to a reflexive one [27,29], restricting the nesting of modal operators [10], restricting the propositional power of the languages [11], and considering coarser interval temporal logics based on interval relations that describe a less precise relationship between intervals (similarly to what topological relations do) [33]. In the case of H S 2 , only the sub-languages for H S 2 RCC8 and H S 2 RCC5 have been studied, in [25], and their satisfiability problem is undecidable as well, even under very simple assumptions, or can be proven so by exploiting the results on the one-dimensional case. In general, one can expect deduction in H S k to be a computationally hard problem even under very restrictive assumptions, such as finite domains. Although in the spirit of the existing work for interval temporal logic one can imagine exploring fragments of H S k , here we are interested in induction problems, for which expressive power and the possibility of describing patterns are more important qualities. In the following, we shall focus on bidimensional images, and therefore fix k = 2. The particular sub-language used in a given knowledge extraction problem is also a parameter, and we can choose, for example, to learn patterns in H S 2 ,

Decision tree learning
A theory of binary spatial decision trees. In the bidimensional setting, a spatial dataset is a set S = {S 1 , . . . , S m } of m spatial instances defined over a set of n spatial attributes A 1 , . . . , A n ; each attribute is a single-channel image with N S points π 1 , . . . , π N S , and we assume that such points form a bidimensional rectangular matrix, that is, N], and D = D, < . In this way, we can interpret spatial datasets as models of H S 2 , in which each point π is a pair (x 1 , x 2 ) ∈ D 2 . A categorical labelled spatial dataset is a spatial dataset where the instances are associated to a target variable C = {C 1 , . . . ,C l }, known as class variable. So, each image is described by many attributes, each of which can be thought of as a color channel, and expresses a real number for each spatial point (see Fig. 3). Digital images often depict objects in terms of colors from the visible spectrum, and usually encompass only a few color channels (e.g., three when using the popular RGB standard); however, there are situations where channels have a different interpretation (e.g., hyperspectral imagery). For a spatial attribute A ∈ A , let dom(A) denote its domain (i.e., the set of values of A that actually occur in S), and A(π) the value of A at the point π. The class of an instance S ∈ S is denoted by C(S). We assume that there are no missing values. We shall describe properties of images by expressing properties of rectangles, each denoted by a pair of points: r = [(x 1 , y 1 ), (x 2 , y 2 )]. Such properties are called propositional decisions: where ∈ {<, ≤, = , =}, and are evaluated on rectangles. The parameter γ ∈ (0, 1] allows us avoid a too strict evaluation of such propositions on rectangles; in particular, we first define, for a point π = (z,t): and, then, we establish that A γ a is true on a rectangle r if and only if it holds: Fixed an image S ∈ S , and a rectangle r in it, we denote the above situation as: Our theory of spatial decision trees is based on H S 2 (although, as we have recalled, the actual sublanguage used can be a parameter of the problem), thus, on top of propositional decisions, the language of spatial decision trees encompasses a set of modal decisions: where X 1 , X 2 is a H S 2 modality. Together, propositional and modal decisions form a set of decisions: Binary spatial decision trees are formulas of the following grammar: where W prop ∈ W prop and W mod ∈ W mod are decisions and C ∈ C is a class. To define the semantics of spatial decision trees on a spatial dataset, we need to first define how decisions are evaluated. In the static case of binary decision trees, from a dataset one immediately computes its partition into the two subsets that are entailed by a propositional decision. In the spatial case, we start by assuming that each instance S is anchored to a set of rectangles in the set K(D 2 ), denoted S.re f s. At the beginning of the learning phase, S.re f s = {r 0 } for every S, where r 0 is a distinguished rectangle that we interpret as a privileged observation point from which the learning takes place; for example, it can be the central unit rectangle, or a rectangle at a corner of the image. Spatial decision tree learning is a local learning process; the local nature of decision trees does not transpire at the static level, but it becomes evident at the modal one. Every decision entails, potentially, new reference rectangles for every instance of a dataset. In particular, given an image S with associated S.re f s, and given a decision W , we can compute a set of new reference rectangles f (S.re f s,W ) as: , and as: When W is clear from the context, we use S.re f s to denote f (S.re f s,W ). Splitting a dataset S on the basis of a decision becomes now possible. Given a spatial dataset S and a decision W , we say that S e = {S ∈ S | S.re f s = / 0}, and we assume that each image S ∈ S e is anchored to S.re f s , and whereas instances in S u remain anchored to their original set of rectangles. For a decision W , we use the notation S W or S, S.re f s W (respectively, S ¬W or S, S.re f s ¬W ) to identify the members of S e (respectively, S u ). To define how a binary spatial decision tree is evaluated on a spatial dataset we need to establish how single instances are classified. Thus, we denote by τ(S, S.re f s) the class assigned by τ to an instance S anchored at the set S.re f s, and define it inductively as: Then, we say that the class assigned by τ to S is τ(S) = τ(S, {r 0 }). Independently from the problem being propositional, temporal, or spatial, evaluating a tree τ on a dataset S entails classifying all its instances, and comparing the resulting class with the ground truth; such a comparison gives rise to a confusion matrix θ , and, in turn, to define the notion: When such an evaluation is performed on the training set, θ represents the training performance of τ, while when it is performed on a classified dataset not used for training is called test performance. Entropy based learning of spatial decision trees. The decision tree model was originally defined by [36], which resulted in the development of the Iterative Dichotomizer 3 (ID3) algorithm, that is able to extract decision trees from static categorical data, and its extension C4.5 [37], that includes the possibility of dealing with numerical attributes as well. Spatial C4.5 extends C4.5 to deal with spatial datasets, preserving its driving principles. Since learning optimal trees is a NP-hard problem at the propositional level already [22], so is at the spatial level, and Spatial C4.5, just like C4.5, implements a suboptimal, greedy approach generally known as entropy-based learning. Let ξ i be the fraction of instances labelled with class C i in a dataset S with distinct classes. Then, the information conveyed by S (or entropy of S ) is computed as: Intuitively, the entropy is inversely proportional to the purity degree of S with respect to the class values. In binary trees, splitting, which is the main greedy operation, is performed over a specific attribute A, a threshold value a ∈ dom(A), a value γ, and an operator . Let W (A, a, γ, ) be the decision entailed by A, a, γ, , and let (S e , S u ) be the partition of S entailed by W (A, a, γ, ) (as defined above). The splitting information of W = W (A, a, γ, ) is defined as: In this way, we can define the entropy gain of a decision as: Given a spatial dataset S , the language of all possible decisions, and therefore of all possible splits, is implicitly defined, and the generic, high level Spatial C4.5 algorithm works as shown in Alg. 1. This learning algorithm returns a binary tree τ, in which every node is associated with a subset of S , and every leaf node is associated with a class that depends on the labeling function that has been used. The most typical choice is labeling a leaf with the class that occurs the most in the associated dataset, but every labeling function, in general, generates a certain amount of misclassification. As in the propositional case, the procedure includes some stopping criteria, preventing the resulting model from overfitting to the training data. The stopping conditions, also called pre-pruning conditions, depend on the particular implementation and are subject to statistical evaluations; typical conditions include testing the purity of the dataset associated with the candidate-leaf node, evaluating its cardinality, and evaluating the information gain that may emerge from a further splitting step. Note, however, that there are other approaches to prevent overfitting (e.g., training ensambles of trees). The theoretical complexity of this algorithm mainly depends on the number of possible decisions, as well as the cost of checking the truth of each decision on each instance. Both at the propositional and spatial level, the time complexity is polynomial, but the truth-checking step in the spatial case adds a Θ(N 2k ) term (note that this is the number of different hyperrectangles in an N × . . . × N, k-dimensional dimensional space) that is not present at the propositional level. The parameters of Spatial C4.5 includes all classical propositional parameters (e.g., the stopping conditions) plus the subset of potential decisions, which in turn depends on the subset of (direct or disjunctive) operators of H S 2 and the admitted values of γ, and the location of the starting hyperrectangle r 0 . Algorithm 1: High-level description of Spatial C4.5.
input : S -spatial dataset output: τ -spatial decision tree function SpatialC4.5(S ): Preprocess(S ) τ ← Learn(S ) return τ end input : S -spatial dataset output: ν -decision node function Learn(S ): if some stopping condition applies then return CreateLea f Node(S ) return ν end Spatial C4.5 implementation. Implementations of decision tree learning algorithms exist in several learning suites; the most popular implementations are provided by the Scikit-learn suite [35] (in Python), and Weka [48] (in Java). In recent years, the Julia programming language is becoming increasingly popular for scientific computing and, although the language is still young, there exists a stable Julia package for decision tree learning [41]. Due to the performance gains that Julia, as a compiled language, enables, we developed an implementation of Spatial C4.5 starting from the existing Julia package.

Experimental results
Land cover classification. While spatial decision tree learning can be applied to many image-related tasks, we focus here on a single image classification problem that is suitable for small-scale, spatial, raw-pixel reasoning: land cover classification. The objective is to label each pixel in aerial/satellite imagery with a class label carrying meaningful information about its content (e.g., classify it as forest, urban area, or crop field). Due to the high altitude from which the images are captured, a single pixel carries the average electromagnetic response of a wider surface area (e.g., one to hundreds of squared meters) and, as such, the classification of a pixel in the image only depends on a close neighborhood of pixels. One can see how learning spatial patterns can be computationally easy in this context. Strictly speaking, land cover classification is an instance of image segmentation but, because of its properties, the problem has been often tackled by classifying each pixel independently. This choice is also supported by the fact that the imagery involved is often hyperspectral, that is, composed of many color channels, describing the strength of signals at different electromagnetic wavelengths; thus, each pixel holds a large number of values (e.g., usually in the hundreds) that, collectively, describe in a satisfactory way the nature of its content. Within this framework, a pixel can be represented as a single line of tabular data, and propositional symbolic methods naturally lend themselves for the job; together with the need for explicit classification rules and good performances, this is one of the reasons why this task has a long history being approached by propositional symbolic methods [5,6,20,23,49,50,51]. Although it proved fruitful in the past, classifying a pixel solely according to its spectral footprint is limited, as it disregards the spatial structure of the image. In recent times there have been many neural network-based applications that can capture spatial, inter-pixel dependencies in some sense [3,14,24,40,42,52]. These approaches leverage intrinsic spatial localities through the engineering of spatial features, and their performances are ultimately better than those of previous attempts; however, as we have already observed, as a general rule functional approaches give up the interpretability and the explainability of the resulting models.
Experimental setup. We have identified four datasets that are publicly available and commonly used to benchmark neural network-based methods for hyperspectral land cover classification. They are referred to as Indian Pines, Pavia University, Pavia Centre, and Salinas-A. Each dataset consists of an image of a piece of land, coupled with a ground-truth label mask, providing the correct class for some of the pixels in the image. In all cases, the image is captured by a dedicated sensor during a flight campaign: specifically, Pavia University and Pavia Centre were collected using a ROSIS sensor (Reflective Optics System Imaging Spectrometer) and the remaining ones using an AVIRIS sensor (Airborne Visible/Infrared Imaging Spectrometer). The ROSIS and AVIRIS yield spectral detections covering a range of frequencies from 0.43µm to 0.86µm and from 0.4µm to 2.45µm, with a number of channels of 103 and 200, respectively. The size of the images varies from 86 × 83 pixels for the Salinas-A dataset to 1096 × 1096 pixels for Pavia Centre; however, not all pixels are labelled. The typical approach to using these datasets for land cover classification involves gathering either all labelled pixels, or a randomly sampled subset, and applying a classifier model extraction to them. Some approaches also make use of the spatial structure, and consider, for the classification of each pixel, a set of neighboring pixels; the neighborhood is generally in the form of a d × d window centered in the pixel, for a natural odd number d. This one is also our solution, so that each dataset, for us, is a collection of d × d images. In general, the chosen datasets present somewhat skewed raw data; to correct the biases towards certain classes, in this experiment the class counts are balanced according to a simple transformation: a fixed number P of pixels is randomly sampled for each class, discarding less numerous classes. In this experiment, we fixed d = 3 and P = 100; this entailed producing the following classification sub-datasets: Indian Pines with 12 classes (and therefore 1200 instances), Pavia University with 9 (900), Pavia Centre with 9 (900), and Salinas-A with 6 (600). We used three of these four datasets for a systematic comparisons between different approaches to symbolic classification, and the fourth one to specifically extract interpretable models and show their potential. Each dataset of the first group (Indian Pines, Pavia University, and Pavia Centre) is then split in two balanced sets for training (80%) and test (20%); each execution, with a different seed (from 1 to 10), entails a different training/test pair. We compared the performances of the following approaches: (i) Spatial C4.5 with H S 2 RCC5 (simply referred to as H S 2 RCC5 ); (ii) Spatial C4.5 with H S 2 RCC8 (H S 2 RCC5 ); (iii) propositional single-pixel (single-pixel), in which we use standard C4.5 trees learned on the numerical description of the pixel to be classified, without spatial information; (iv) propositional flattened (flattened), in which we use standard C4.5 trees learned on the numerical descriptions of all pixels in the d × d image, without spatial information, and (v) propositional averaged (averaged), in which we use standard C4.5 trees learned on single pixels described by averaging all values of the d × d image, again, without spatial information. The baseline is clearly the simple approach, that classifies a single pixel based on its own spectral footprint (for example in the case of Indian Pines, this implies that a single pixel is classified using the values of the 200 spectral attributes describing it, but no values of any neighboring pixel). The flattened approach is the spatial equivalent of using lagged val-ues in standard temporal learning; in this case, the information of the neighboring pixel is included, but the spatial information is not preserved (again, in the example of Indian Pines, this means that each pixel is classified according to d 2 × 200, unordered attributes): as we shall see, this method performs generally bad, probably because of a too large number of variables, which has a negative effect on entropy-based, locally optimal learning. The averaged approach is based on describing every pixel with the average value of all its neighboring ones; in this way the spatial component is included in the learning, but in a unordered way: unlike the flattened version, however, the number of variables is again equal to the number of channels, allowing standard decision trees to work well enough. All approaches share the same implementation of Spatial C4.5; in the propositional experiments, the modal part is simply excluded. With regards to the pre-pruning parametrization, after some preliminary tests, three conditions were fixed: a minimum number of samples per leaf to 4, a minimum information gain of 0.01 for a split to be meaningful, and a maximum entropy at each leaf of 0.3. As for the spatial parametrization, we fixed r 0 to be always the minimum rectangle that contains the pixel to be classified. Moreover, to define the set of allowed decisions, we fixed = {≤, ≥} and γ ∈ {0.6, 0.7, 0.8, 0.9, 1}. Finally, in terms of performance metrics, we adopted: (i) accuracy, (ii) kappa coefficient (which relativizes the accuracy to the probability of a random correct answer), (iii) sensitivity, (iv) specificity, and (v) precision all computed in test mode. Each experiment is repeated a number times with different seeds for the sampling steps; this number was fixed to 10 to satisfy some time constraints.
Results and discussion Tab. 4 shows a comparison of the results of the four different approaches in the three datasets. Overall, the total computation time needed for the experiments was around 96 hours on a Dell PowerEdge server with Intel Xeon Gold 6238R processors, using multi-threading (4 threads). A great portion of this time was spent in searching the locally optimal decision in the spatial approaches, which takes 10 to 100 times more time, compared to the propositional approaches. Accuracy and κ coefficient show similar trends, and only differ in a significant way when the overall performance is low. The lowest performance is achieved on Pavia University and Pavia Centre with the flattened approach; these are cases where no split satisfies the constraints (e.g., no split is informative enough), and the trees only consist of a leaf node, eventually classifying all samples with the same class. The accuracy in these cases is similar to that of a random classifier. At a closer look, it appears that the flattened approach is never competitive with the other methods, and is never better than propositional ones (incidentally, this is exactly the opposite to what happens using lagged values in temporal reasoning). Altogether, the results across the five datasets show that both spatial approaches always yield better results than nonspatial ones. The improvements seem to be proportional to the intrinsic hardness of each classification problem; compared with the propositional approach, the average improvement of Spatial C4.5 ranges from 5% to 9%. The averaged approach performs better than the propositional one, but worse than the spatial one, except one case, Pavia Centre, in which the two approaches have essentially the same performance; yet, the averaged approach works with a computed feature (the average), so the original dataset and the averaged one are not really comparable to each other. Considering the test accuracies in the 10 executions per each dataset and per each approach, and interpreting them as populations, we also produced the boxplot for each dataset, in order to have a graphical understanding of the overall performances (see Fig. 5). One can observe how in two out of three cases, the spatial approaches behave better than all others. In two cases, the simple approach is very consistent, showing a very low variability (Pavia University and Pavia Centre), while this is not the case for the third one. Among the spatial approaches, H S 2 RCC5 is always slightly worse than H S 2 RCC8 , and it has always higher variability; moreover, H S 2 RCC8 presents no outliers. On top of the statistical analysis on the performances, we can see in Fig. 6 Figure 4: Comparison of the results on 3 datasets for land cover classification using propositional and spatial decision trees. Metrics, from left to right: kappa coefficient, accuracy, sensitivity, specificity, precision. All the results are in percentage points. executing Spatial C4.5 on a randomized training set extracted from Salinas-A. In this case, the problem to be solved is learning how to distinguish different types of vegetables. The one shown on the left side has been extracted by the propositional single-pixel approach, while the one on the right side has been extracted by the spatial RCC8 approach. The propositional tree presents κ = 92%, but a closer look reveals that the majority of the misclassifications concern the class C 2 (corn senesced green weeds), often confused with C 6 (lettuce romaine, 7 weeks) by this model (in particular, true C 2 instances are often classified as C 6 ), and the class-sensitivity of C 2 is only 75%. On the other hand, the spatial tree presents κ = 100%, which, in particular, implies that the class-sensitivity of all classes, and thus C 2 as well, is 100%. Since in this particular case both models have only one leaf per class, one can easily extract a rule that, in some sense, describes the spatial properties of this class. The two formulas that emerge are shown in Fig. 6 (bottom). As we can see, the propositional one gives very limited information, that only concerns the attributes of the pixel to be classified. The spatial one (in this case, a H S 2 RCC8 -formula), instead, describes a richer spatial scenario, which could be translated in natural language as follows: if the 3 × 3 window surrounding the to-be-classified pixel presents strictly more than 20% of pixels with A 43 < 1978, and at there exists at least one rectangle of neighboring pixels in which all of the pixels have A 83 ≥ 638 and A 6 ≤ 1625, then the pixel is corn senesced green weeds. In turn, such a formula could be translated to a spatial model, which, in essence, visually represents the class C 2 . Thus, we can explain why the propositional tree fails, when it does: the first split is performed on the characteristics of the pixel itself, while the class C 2 , seemingly, requires considerations on the windows in which it is submerged, to be correctly distinguished from C 6 . This example shows the advantages of symbolic models over non-symbolic ones: the models can be read in natural language.  Figure 6: Comparison between a propositional (left) and a spatial (right) decision tree extracted on Salinas-A. The highlighted paths show the rules that each model has extracted for the class C 2 (i.e., Corn senesced green weeds).
In this picture, γ is denoted simply as when γ = 1.0

Conclusion and future steps
In this paper, we proposed a novel technique for knowledge extraction from spatial data. In the context of a general approach called modal symbolic learning, we considered a well-known symbolic learning schema, namely decision trees, and enhanced it by substituting propositional logic with a suitable modal spatial logic. With this method we can exploit the spatial arrangements of objects, and therefore make more informed decisions towards the classification of images. This work should be looked at from different perspectives. First, from a purely statistical point of view, we proved that, at least for the land cover classification problem and the chosen benchmark datasets, our models behave much better than purely propositional ones, and very good in absolute terms. Second, from a foundational standpoint spatial decision trees are located at the intersection between the symbolic learning theory and the modal logic theory, therefore opening a new field of research in which both well-known and new modal languages can be studied from a new perspective (that is, induction). Third, from a machine learning perspective, we submit that spatial symbolic learning can be a serious alternative to functional learning, typically based on neural networks, being able to offer very accurate models that can, unlike functional ones, give rise to a logical theory of the phenomena under consideration, and therefore be interpreted in a much natural way. In this respect, one should add that it is customary in machine learning to judge a new learning model uniquely from its statistical performances, which is in fact very reductive; we believe that the fact of being able to extract a theory that can be analyzed, validated, and corrected with background knowledge which can be written in the same language can compensate even the loss of some points in the accuracy of a classification exercise. Finally, our approach can be further generalized to achieve true neuro-symbolic reasoning, in which inner objects are initially recognized with a functional method (e.g., a neural network) and then their spatial relationships are exploited with a spatial decision tree. Our approach can be further developed and extended into a theory of ensemble of trees; initial experiments in this sense show that the performances of the resulting models improve in a substantial way. Ensemble of trees are usually considered to be on the verge between symbolic and functional learning: however, ensembles of trees can be interpreted, at least partially, from a logical point of view, giving rise to a logical theory of the underlying phenomenon. While computing ensembles is usually more expensive than computing single trees, the requirements can be reduced through randomization and preprocessing.