Sofien Dhouib

Ievgen Redko

Carole Lartizien

On learning a large margin classifier for domain adaptation based on similarity functions

Keywords: binary classification, domain adaptation, large margin, similarity functions

Traditional supervised classification algorithms fail when unlabeled test data arise from a probability distribution that differs from that of the labeled training data. This problem is addressed by domain adaptation, an active research area in which one would like to transfer the knowledge acquired from a first labeled domain, the source, to a second one, the target. In this paper, we tackle this problem from the perspective of large margin classifiers based on ( , γ, τ )-good similarity functions. We first prove a bound on the error of such a classifier on the target domain. Then we present our algorithm consisting in minimizing this bound, allowing to learn a good classifier directly on the target domain without an intermediate domain alignment step. Under specific conditions, our algorithm can be formulated as a convex optimization problem that is solved efficiently. Its performance is assessed via experiments on on a toy set and a real world problem.

Introduction

Classification algorithms are used in several real world applications such as image recognition and sentiment analysis. Some of these algorithms output decision rules are based on a pairwise similarity between different data instances, with two of the most known algorithms of this kind being the nearest neighbors clas-sifier [START_REF] Cover | Nearest neighbor pattern classification[END_REF] and the support vector machine [START_REF] Boser | A Training Algorithm for Optimal Margin Classifiers[END_REF] (SVM). In order to determine the class of a given example, the former relies on the labels of its nearest neighbors in the sense of a given distance via a voting rule, whereas the latter outputs a classifier that is a linear combination of the point's similarity to the rest of the training data, where the used similarity is restricted to verify Mercer's theorem, i.e to be a kernel. Despite such a restriction, SVM's are appealing due to their great generalization capacity that is empirically observed and theoretically proven [START_REF] Cortes | Support-Vector Networks[END_REF]. In fact, their aim at separating the data with the largest possible margin is a major cause of their success. As a result, it seems interesting to keep this large margin separation aspect without constraining the used similarity function to be a kernel. This is the main topic of the two seminal papers of [START_REF] Balcan | A theory of learning with similarity functions[END_REF][START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF], which define and analyze the goodness of a similarity function for a given binary classification problem. The definition they introduce is rather intuitive, stating that with a high probability (1 -), the average similarity of a data point to landmarks of its own label is greater than that to the opposite label, with the difference between the two average similarities being at least equal to a margin γ. The landmarks are a priori fixed instances that represent a τ fraction of the available data. Given a similarity function verifying this intuitive condition, the authors define a new representation space in which an instance's features are its similarities to the different landmarks, and prove that with enough drawn landmarks, the two classes are linearly separable with a large margin in that representation. Given such encouraging theoretical guarantees, several works in the literature considered the problem of learning such func-tions ([BHS12, GY13, NGHS15, ISH + 15]).

The way they are defined, ( , γ, τ )-good similarity functions are convenient for a supervised learning setting in which the training and testing sets arise from the same probability distribution and belong to the same input space. This might not always be the case for real world applications where new partially or totally unlabeled data is available for a given application, but follows a probability distribution that differs from the one generating the labeled training data. An efficient approach to tackle such a problem is transferring the knowledge acquired on the training data to the new test data, and this task is at the heart of the domain adaptation, a currently active research area [PY10, [START_REF] Weiss | A survey of transfer learning[END_REF][START_REF] Margolis | A Literature Review of Domain Adaptation with Unlabeled Data[END_REF], in which the labeled domain is called the source, while the unlabeled one is called the target. More precisely, domain adaptation offers methodological frameworks and algorithms allowing to leverage information available from both domains to output decision rule that is good for the target one.

In this paper, we consider the aforementioned similarity functions in the challenging setting of unsupervised domain adaptation, where no labels are available for the target domain. We start our contribution by providing a theoretical bound on the error of a given similarity function on the target domain by bounding the error of the corresponding classifier. Up to some terms that are neglected afterwards, the bound is a trade off between a source error term and a disagreement between the two domains. The latter is similar to the H∆H divergence [BDBC + 10], and its generalization, the discrepancy distance [START_REF] Mansour | Domain Adaptation: Learning Bounds and Algo-rithms[END_REF]. Following this theoretical contribution, we derive an algorithm that minimizes this bound so that a classifier is directly learnt for the target domain without an additional domain alignment step.

As far as we know, the only works that consider the application of ( , γ, τ )-good similarities in domain adaptation are [START_REF] Morvant | Parsimonious unsupervised and semi-supervised domain adaptation with good similarity functions[END_REF] and [START_REF] Dhouib | Revisiting ( , γ, τ )-similarity learning for domain adaptation[END_REF]. The first one uses a heuristic to select landmarks that move closer the two distributions in the projection space, with the similarity function they used being a kernel that is iteratively reweighted. Our work differs from theirs as in our case the similarity function is learnt in one step and using all of the source instances as landmarks. The second establishes theoretical bounds for the error of a similarity function on a target domain in terms of 1 and χ 2 divergences between probability distributions. In this work, we provide a new bound that involves a domain disagreement term taking into account the considered hypothesis spaces.

In terms of its mechanism consisting in directly learning a classifier on the target domain without an alignment step, our algorithm is similar to the one proposed in [START_REF] Germain | PAC-Bayes and Domain Adaptation[END_REF]. However, while our domain disagreement term is defined by a supremum, theirs is rather an expectation over the set of considered hypotheses classes, as they consider a PAC-Bayesian setting.

The rest of the paper is organized as follows: the first section introduces required preliminary knowledge and notations. Section 2 is dedicated to our contributions, where we first derive a bound on the error term of the target domain. Then, this bound is used to derive an algorithm by considering a particular case of bilinear similarity functions and linear classifiers, resulting in a a convex programming formulation that is solved efficiently. Finally, in the last section we evaluate our algorithm on a toy data set and on a real world problem.

Preliminaries and notations

We consider a binary classification setting, in which the feature space is X ⊂ R d and the labels set is Y = {-1, 1}. Since we work in a domain adaptation context, we suppose having access to a labeled source sample S and an unlabeled target one T , drawn respectively from probability distributions S and T . Furthermore, we denote by f S and f T the two functions labeling the instances of both distributions.

We now recall the definition of a good similarity function

K : X × X → [-1, 1] introduced in [BBS08a]
Definition 1 (Balcan et. al. 2008). A similarity function K is ( , γ, τ )-good in hinge loss for problem (distribution) P if there exists a (probabilistic) indicator function R of a set of "reasonable points" such that:

E (x,y)∼P 1 - y.k(x) γ + ≤ , (1)
P x ∼P [R(x )] ≥ τ, (2)
where

k(x) = E (x ,y )∼P [y K(x, x )|R(x )].
This definition formalizes the intuition that most of instances drawn from a probability distribution P should have a greater average similarity to landmarks of their own class, than those of the opposite class by a margin γ at least. In fact, k(x) represents the difference between the instance x's average similarity to its own class and to the opposite class, and Equation (1) reflects a penalization for the case where yk(x) < γ, i.e where the signed difference is not large enough.

Equivalently, k can be seen as a hypothesis used to classify instances, and Equation (1) says that this hypothesis has an expected hinge loss bounded by at margin γ. We will consider this classifier throughout the next section detailing our contribution.

Given such a similarity function, the authors of [START_REF] Balcan | A theory of learning with similarity functions[END_REF][START_REF] Balcan | Improved guarantees for learning via similarity functions[END_REF] prove that with enough landmark instances, one can construct a new representation space where the features of an instance is its similarities to those landmarks, and where the two classes are linearly separable with a large margin. This result is reminiscent of the kernel trick for SVM's, but it is more general as K does not necessarily have to be a kernel. We note that Definition 1 was modified in [START_REF] Dhouib | Revisiting ( , γ, τ )-similarity learning for domain adaptation[END_REF] in a way allowing landmarks to come from a probability distribution that is not necessarily that of the tested data instances.

Using that modified definition, we introduce the following quantity for a probability distribution P that will be either S or T in the rest of the paper.

E P (k, h) := E x∼P [(1 -h(x)k(x)/γ p ) + ] (3)
where

k(x) := E (x ,y )∼S [K(x, x )f (x )] (4)
γ p is a margin associated to the probability distribution P and h is a classifier. We note regardless of distribution P, landmarks in E P (k, h) are drawn from distribution S. In the case where P = S, this corresponds to Definition 1 with τ = 1 and in the case of P = T , it corresponds to its modification in [START_REF] Dhouib | Revisiting ( , γ, τ )-similarity learning for domain adaptation[END_REF].

Learning a good classifier for the target domain

We hereby present our contribution, starting by establishing a theoretical bound on the average hinge loss of a classifier k on the target domain. This bound is further used to derive an algorithm that directly learns a good classifier for the target.

Problem setup

Our goal is to learn a classifier k, or equivalently a similarity function K that has a low error on the target domain E T (k, f T ). We follow an approach analogous to the ones presented in [BDBC + 10] and [START_REF] Mansour | Domain Adaptation: Learning Bounds and Algo-rithms[END_REF]. We recall the main result stated in [MMR09, Theorem 8]:

Theorem 1 [START_REF] Mansour | Domain Adaptation: Learning Bounds and Algo-rithms[END_REF]. Let H be a hypothesis space, and L : H × H → R + a symmetric loss function verifying the triangle inequality.

For a probability distribution P and h, g ∈ H, let

L P (h, g) = E x∼P [L(g(x), h(x))].
Let h * S and h * T as the best classifiers from H achieving the lowest errors on S and T respectively. Finally, define the discrepancy distance between S and T as disc L (T , S) = sup

h,h ∈H |L T (h, h ) -L S (h, h )|. Then, L T (h, f T ) ≤ L S (h, h * S ) + disc(T , S) L T (h * T , f T ) + L T (h * T , h * S )
The authors assume that L T (h * T , h * S ), the average loss between the best in-class hypotheses for each domain, is small for adaptation to be possible. Furthermore, the term L T (h * T , f T ) is assumed to be small given that the hypothesis space has enough richness to represent f T with low error, and L S (h, h * S ) is close to the considered classifier h's error on the source again if f S is well approximated by h * S . This bound will hence be small if h performs well on the source domain and if S and T are close in terms of the discrepancy distance.

The above result cannot be used directly as we consider the hinge loss that does not verify the triangular inequality. In order to prove our result, we assume that there exists a function f : X → [-1, 1] that performs well on the the source and target domains. In the case f achieves a perfect labeling of both the source and target domains, this assumption corresponds in the domain adaptation literature to the covariate shift [START_REF] Sugiyama | Covariate Shift Adaptation by Importance Weighted Cross Validation[END_REF]. Otherwise, it is similar to the ideal joint hypothesis defined in [BDBC + 10] and considered in [START_REF] Germain | PAC-Bayes and Domain Adaptation[END_REF]. While such a function is unknown, we suppose that it belongs to a hypothesis space H verifying h ∈ H ⇒ -h ∈ H.

With these assumptions, we are ready to state our bound on the expected error on the target domain E T (k, f T ).

Proposition 1. Given a similarity function K with a corresponding classifier k, two margins γ s , γ t respectively associated to the source and target domains and their ratio δ = γs γt , the following holds:

E T (k, f T ) ≤ E S (k, f S ) + 1 γ s sup h∈H ∆ δ (k, h) + E x∼S |f S (x) -f (x)| γ s + E x∼T |f T (x) -f (x)| γ t where ∆ δ (k, h) = E x∼T E x ∼S [k(x )h(x )] -δk(x)h(x)
Proof. We start by writing:

E T (k, f T ) = E T (k, f T ) -E T (k, f ) (5) + E T (k, f ) -E S (k, f ) (6) + E S (k, f ) -E S (k, f S ) (7) + E S (k, f S ).
For (7), we have:

E S (k, f ) -E S (k, f S ) = E x∼S (1 - k(x)f (x) γ s ) -E x∼S (1 - k(x)f S (x) γ s ) ≤ 1 γ s E x∼S [k(x)(f S (x) -f (x)) + ] .
Term (5) can be bounded in the same manner. Concerning term (6), we have:

ET (k, f ) -ES (k, f ) = E x∼T 1 - k(x)f (x) γt + -E x∼S 1 - k(x)f (x) γs + ≤ E x∼T 1 - k(x)f (x) γt + -1 -E x∼S k(x)f (x) γs + (8) ≤ E x∼T     E x ∼S [k(x )f (x )] γs - k(x)f (x) γt   +   (9) = 1 γs E x∼T E x ∼S k(x )f (x ) -δk(x)f (x) + ≤ 1 γs sup h∈H E x∼T E x ∼S k(x )h(x ) -δk(x)h(x) + = 1 γs sup h∈H E x∼T E x ∼S k(x )h(x ) -δk(x)h(x)
where (8) is obtained by applying Jensen's inequality to the convex function (1 -•) + . Then, using the inequality (t) + -(s) + ≤ (t -s) + (sub-additivity of the positive part), one gets line (9). The last line is a consequence of the fact that h ∈ H ⇒ -h ∈ H.

The established bound has 4 terms: the first one is the error on the source w.r.t function f S , known through the labels y. This term is similar to L S (h, h * S ) in theorem 1.

The second term reflects a disagreement between the source and the target w.r.t hypothesis k. Its counterpart in 1 is the discrepancy disc, and if K = H, both disagreement measures bound the same quantity:

E T (k, f ) -E S (k, f ) ≤ sup h,h ∈H |E T (h, h ) -E S (h, h )| = disc(T , S) E T (k, f ) -E S (k, f ) ≤ 1 γ s sup x∈ ∆ δ (k, h)
The last two terms are distances between f and the best hypotheses in H that respectively label elements drawn from S and T . We will neglect both of them in our algorithm's definition, as we would expect them to be small for the adaptation to be possible, given the existence of f . After omitting these two terms, the sum of the two remaining terms defines our algorithm that we detail in the next section.

Algorithm derivation

We suppose searching for the similarity function K in hypothesis space, and we denote by K the hypothesis space of classifiers it induces, i.e from which the resulting classifier k is picked. Our algorithm is then formulated as follows:

minimize k∈K E S (k, f S ) + 1 γ s sup h∈H ∆ δ (k, h)
The cost function in this case contains a supremum over the potentially infinite hypothesis set H, which makes the optimization difficult. However, we will show in the next section that a particular choice of H allows to deal efficiently with this term, transforming it into a maximum over a finite set. Using the Lagrange multipliers, the minimization problem is equivalent to:

minimize k∈K sup h∈H ∆ δ (k, h) subject to E S (k, f S ) ≤
where is a hyperparameter. Without the constraint on the source domain error, the trivial null similarity function K ≡ 0 is a solution to the problem. Thus, it plays a major role in avoiding this solution, in addition to imposing a low error on the source domain.

We note that if the constrained version of the minimization algorithm manages to find a small value for sup h∈H ∆ δ (k, h), then from the proof of Proposition 1, we have

E x∼T E x ∼S [k(x )f (x )] -δk(x)f (x) + = ∆ δ (k, f ) ≤ sup h∈H ∆ δ (k, h).
The left hand side of these inequalities penalizes the case 1 δ E

x ∼S

[k(x )f (x )] > k(x)f (x) for every instance

x drawn from the target distribution, resulting in similarity K that is good on T with margin γ =

γt γs E x∼S E x ∼S [K(x, x )f (x)f S (x )]
. This is the mean margin of K on the source domain when f and f S label respectively the data points and the landmarks, up to a scaling factor γt γs . This also means that the classifier k would have a low error on the target with a margin γ γs γ t , which is a scaled version of the originally considered margin γ t for the target domain.

Case of bilinear similarities and linear classifiers

Below, we discuss a particular choice for both hypotheses classes K and H in order to make the optimization problem tractable. To this end, we consider bilinear similarity functions K(x, x ) = x T Ax with A ∈ R d×d , A ≤ 1. Such functions were studied in the ( , γ, τ )-good framework in [START_REF] Bellet | Similarity Learning for Provably Accurate Sparse Linear Classification[END_REF]. By scaling the data instances so that their Euclidean norms are bounded by 1, K takes values in [-1, 1]. We proceed to determine the implied K space in this case. Let

x ∈ R d : k(x) = E x ∼S [K(x, x )f S (x )] = E x ∼S x T Ax f S (x ) = x T Aµ with µ = E x∼S [x.f S (x)
] and

K ={k : x → x T Aµ; A ∈ R d×d A ≤ 1} {Aµ; A ∈ R d×d ; A ≤ 1} ⊂{a ∈ R d ; a ≤ 1},
where the symbol denotes equality up to an isomorphism of vector spaces.

As for H, we choose the space of linear classifiers with bounded 1 norm:

H {w ∈ R d ; w 1 ≤ 1}. Hence, for k(x) = a T x and h(x) = w T x, one has ∆ δ (a, w) = E x∼T E x ∼S a T x x T w -δa T xx T w + = E x∼T a T ( E x ∼S x x T -δxx T )w .
For a fixed a ∈ R d , the function w → ∆ δ (a, w) is convex, hence its supremum over H, an 1 unit ball, is reached on one of its vertices sup

w 1 ≤1 ∆ δ (a, w) = max 1≤i≤d E x∼T a T (Σ S -δxx T )e i ,
where Σ S = E x∼S xx T and {e 1 , ..., e d } is the canonical basis of R d . Multiplying the cost function by γ s , the problem is written:

minimize a ≤1 E x∼S [(γ s -f S (x)k(x)) + ] + M s.t. M ≥ E x∼T a T (Σ S -δxx T )e i ∀1 ≤ i ≤ d.
In the empirical case, i.e when the expectation terms are replaced by corresponding empirical means over the source and target samples of respective sizes m and n, this is a quadratic optimization problem having d + m variables (d for the size of vector a, m for the positive variables representing the positive parts) and 1 + 2m + 2nd constraints (one for a , 2 for each source instance and 2d for each target one). It can be solved efficiently using standard convex optimization solvers.

Experiments

In this section, we evaluate our method on two domain adaptation problems. The first is defined by a toy set with a controllable difficulty, while the second is a real world problem.

Cross-validation

We choose the best values of hyperparameters γ s and δ by a reverse validation procedure ([ZFY + 10], [START_REF] Bruzzone | Domain Adaptation Problems: A DASVM Classification Technique and a Circular Validation Strategy[END_REF]) following the protocol of [START_REF] Germain | PAC-Bayes and Domain Adaptation[END_REF] with a 5 folds validation. Given a fold i ∈ 1, ..., 5 defining a training set S \ S i and a validation set and S i for the source, and similarly T \ T i and T i for the target, a classifier h is learnt from labeled S \ S i and unlabeled T \ T i . Then, keeping the same hyperparameters used to learn h, a reverse classifier h r is learnt from T \ T i labeled by h and unlabeled S \ S i , and finally evaluated on S i . The chosen hyperparameters are those minimizing the average error of h r over the folds. This way we do not make use of the target labels, which fits with the unsupervised domain adaptation setting. We slightly modify this procedure to suit our method: γ s and δ, or equivalently γ s and γ t are respectively associated with S and T , hence when computing the reverse classifier h r , we replace γ and δ respectively by γs δ = γ t and 1 δ = γt γs . Moreover, the best hyperparameters are those minimizing the average margin violation loss of h r on the source validation sets S i , i.e 1 5 where [. . .] denotes the Iverson bracket. After choosing the hyperparameters by this procedure, the resulting classifier's performance is evaluated on two independent source and target sets. This whole procedure (reverse validation then testing) is repeated 10 times, and the average performances over those repetitions are reported. For all of the experiments, we use the CVXPY modeling language ([DB16], [START_REF] Agrawal | A rewriting system for convex optimization problems[END_REF]) with the solver MOSEK ([ApS17]).

5 i=1 1 |S i | x∈Si [y(x)h r (x) < γ s ] Angle ( • )

Moons data set

We carry on our experiments on the moons data set used in [START_REF] Germain | A PAC-Bayesian Approach for Domain Adaptation with Specialization to Linear Classifiers[END_REF] and [START_REF] Courty | Optimal Transport for Domain Adaptation[END_REF]. The source data set is centered at the origin (0, 0), and has 300 instances, which are rotated around that point by a certain angle to get the target distribution. Obviously the greater is the angle, the further from each other are the two domains and the harder is the adaptation. To ensure the data is linearly separable, we apply a Kernel PCA [START_REF] Schölkopf | Kernel principal component analysis[END_REF] with a Gaussian kernel having a parameter σ equal to the mean Euclidean distance between instances (as done in [START_REF] Kar | Similarity-based Learning via Data Driven Embeddings[END_REF]), keeping respectively 8 and 20 components. The mean over 10 tests on independent data sets of 1000 instances are reported in Table 1, where our algorithm is compared to an SVM trained on the source domain (without adaptation) and domain adaptation algorithms DASVM [START_REF] Bruzzone | Domain Adaptation Problems: A DASVM Classification Technique and a Circular Validation Strategy[END_REF], PBDA [START_REF] Germain | PAC-Bayes and Domain Adaptation[END_REF], OT-GL [START_REF] Courty | Optimal Transport for Domain Adaptation[END_REF] and DASF [START_REF] Morvant | Parsimonious unsupervised and semi-supervised domain adaptation with good similarity functions[END_REF]. We observe that our method outperforms both DASVM and PBDA for angles up to 70 • . However, its performance remains lower than DASF and OT-GL except for angles 50 • and 70 • . We think that this difference is due to the fact that our bound overestimates the divergence between the two domains for small angles due to the supremum term in Proposition 1.

Prostate cancer data set

We test our algorithm on a real world problem: a clinical data set of multi-parametric magnetic resonance images (mp-MRI) collected to train a computer- To tackle the class imbalance illustrated in Table 2, we randomly select a balanced 2000 voxels data set for each of the 10 repeated reverse validation procedures. Moreover, we run a principal component analysis keeping 95% of the total variance, and reducing the number of features to 28. With the best found hyperparameters, our algorithm is evaluated 10 times on independent data sets of 10000 instances for each domain. Results are reported in Table 3, where we compare our algorithm with a linear SVM without adaptation (Scikit-Learn [PVG + 11]'s implementation). We notice that for both domain adaptation where we consider the 3T and 1.5T domains as source and target interchangeably, the scores on the target domain are close, reflecting a symmetry of the problem. Our method exhibits an improvement of 11% over the case without adaptation.

Problem

Conclusion and future perspectives

In this paper, we presented a new algorithm for domain adaptation that is suitable for large margin classifiers. Our algorithm is derived from a theoretical bound and allows to learn a classifier on the target domain directly without an additional alignment step. In the case of bilinear similarity functions and linear classifiers, it is formulated as a quadratic optimization problem that is solved efficiently. The results we obtain are encouraging, although not surpassing state of the art methods ([CFTR15], [START_REF] Morvant | Parsimonious unsupervised and semi-supervised domain adaptation with good similarity functions[END_REF]), and suggest trying to obtain a tighter bound from which the algorithm is derived or using a domain disagreement term that is less strict than a supremum. For example, considering an expectation over the considered set of classifiers [START_REF] Germain | PAC-Bayes and Domain Adaptation[END_REF] is worth a try. Moreover, in the context of large margin classifiers, questions about our method's generalization guarantees are naturally raised. Finally, the multi-class case and the semi-supervised domain adaptation (i.e when some labels are available on the target) are crucial extensions to add as they would allow us to test on more real world data sets.

Table 1 :

 1 Average 0-1 loss (percentage) over 10 realizations for the moons toy set.

	20	30	40	50	70	90

  aided diagnosis system for prostate cancer mapping [NRML + 12, ALP + 15]. This system learns a binary decision model in a multidimensional feature space based on training samples (voxels) from different classes of interest. This model is then used to generate cancer probability maps. Data description The considered source and target data are mp-MRI exams of 90 patients acquired on two different MRI scanners (1.5 T and 3T) and thus leading to images with different resolution and texture patterns. Details are given in Table 2.

	Scanner (domain)	1.5T	3T
	Number of patients	49	41
	Number of voxels	419348 987396
	% of positive class	13.38	14.26
	Table 2: mp-MRI data description.
	Each individual voxel is described by a binary la-
	bel (Cancer, Non Cancer) and a set of 95 handcrafted
	features consisting of image descriptors, texture coeffi-
	cients, gradients and other visual characteristics (more
	details in [NRML + 12]).

Table 3 :

 3 Average 0-1 loss (percentage) over 10 realizations for the mp-MRI data set.

		3T→1.5T 1.5T→3T
	Linear SVM (no adaptation)	49.99	49.56
	Our algorithm	38.99	38.39


R Khemmar

Li Delong

B Decoux

Jean-Yves Ertaud

REAL TIME PEDESTRIAN DETECTION-BASED FASTER HOG/DPM AND DEEP LEARNING APPROACH

Keywords: Pedestrian Detection, Pattern Recognition, Object Detection, HOG, DPM, ADAS Systems, Tracking, Deep Learning

The work presented aims to show the feasibility of scientific and technological concepts in embedded vision dedicated to the extraction of image characteristics allowing the detection and the recognition/localization of objects. Object and pedestrian detection are carried out by two methods: 1. Classical image processing approach, which are improved with Histogram Oriented Gradient (HOG) and Deformable Part Model (DPM) based detection and pattern recognition. We present how we have improved the HOG/DPM approach to make pedestrian detection as a real time task by reducing calculation time. The developed approach allows us not only a pedestrian detection but also calculates the distance between pedestrians and vehicle. 2. Pedestrian detection based Artificial Intelligence (AI) approaches such as Deep Learning (DL). This work has first been validated on a closed circuit and subsequently under real traffic conditions through mobile platforms (mobile robot, drone and vehicles). Several tests have been carried out in the city center of Rouen in order to validate the platform developed.

INTRODUCTION

The work presented in this paper is a part of M2SiNUM 1 project (Advanced Mathematical Modeling and NUMerical Simulation for Innovation in Environment and Health), which is dedicated to the development of generic platform with tools accessible to scientific community. One of the objective of the project is to develop an Advanced Driver Assistance System (ADAS) platform for pedestrian detection and tracking for application of road security and autonomous vehicle. Other objectives of the project are related to advances both in fundamental and technological research. The practical applications are clearly identified and the expected consequences for the project fall within: industrial applications, academic results and national/international developments. The work presented in this paper is dedicated to pedestrian detection in road traffic applications. In general, ADAS is used to improve safety and comfort in vehicles. ADAS is based on the combination of sensors (radar, LIDAR, cameras, etc.) and algorithms that ensure vehicle, driver, passenger's and pedestrian's safety [26]. Here in this project, ADAS aims to detect pedestrian. Our contribution aims on the development of perception system based object detection with different approaches such as HOG, DPM, and DL. This paper is organized as follows: Section 1 introduces the motivation of the paper. Section 2 presents the state of the art of pedestrian detection. Section 3 presents the architecture of the system through the different algorithms used and the results obtained. Section 4 illustrates our pedestrian detection algorithm-based Faster-HOG/DPM in which we present not only how to improve the quality of HOG/DPM pedestrian detection but also how to estimate the distance separating pedestrians to vehicles. Results are presented in Section 4 too. Finally, in Section 5, we will conclude this paper.

STATE OF THE ART AND RELATED WORK 2.1. State of the Art

Object detection is key problem in computer vision with several applications like automotive, manufacturing industry, mobile robotics, assisted living, etc. Pedestrian detection is a particular case of object detection that improve security road and is considered as an important ADAS in the autonomous vehicle. In [START_REF] Yan | The fastest deformable part model for object detection[END_REF], a very good state of the art for pedestrian detection is presented. Detection is disappointing at low resolutions and for partially occluded pedestrians. In [START_REF] Cho | Real-time Pedestrian Detection with Deformable Part Models[END_REF], a real time pedestrian detection with DPM algorithm applied to automotive application is presented. The system present superior detection performance based on multiresolution pedestrian model in order to detect small pixel-sized pedestrians when classical DPM approach missed them. The system was evaluated under Caltech Pedestrian benchmark [START_REF]Caltech Pedestrian Detection Benchmark Homepage[END_REF]. The DPM is presented as an algorithm between generative and discriminative model [START_REF] Girshick | Rich feature hierarchies for accurate object de-tection and semantic segmentation[END_REF][START_REF] Georgakis | Synthesizing Training Data for Object Detection in Indoor Scenes[END_REF]. The algorithm has different steps: build a pyramid for any scale under given image, use different filter and part filters to get responses. The algorithm combines these different responses in star-like model, uses a cost function, and train classifiers by SVM. This algorithm is still a widely used algorithm particularly in combination with DPM [START_REF] Dollar | Pedestrian Detection: An Evaluation of the State of the Art[END_REF]. As another method of object detection, the Integral Channel Features (ICF) [START_REF] Cho | Real-time Pedestrian Detection with Deformable Part Models[END_REF], we can find a combination of multiple registered image channels, which are computed by linear and nonlinear transformations [START_REF] Lowe | Distinct Image Features from Scale-Invariant Keypoints[END_REF]. Integration of some features like HOG and training by AdaBoost in cascade way can lead to pedestrian detection with good accuracy [START_REF] Lowe | Distinct Image Features from Scale-Invariant Keypoints[END_REF]. The sliding window methods (pyramid method) are used in object detection with a high cost of detection time. In a recent work, proposing high-recall important regions is widely used [START_REF]KLT Feature Tracker[END_REF]. In another way, the approaches based on intelligence based deep learning like Convolutional Neural Network (CNN) become very successful methods for features extraction in image classification task [START_REF] Odobez | Robust Multiresolution Estimation of Parametric Motion Models[END_REF]. We can give as an example the Rich Feature Hierarchies for CNN (RCNN) paper [START_REF]Object Detection Homepage[END_REF], that combine CNN and selective search. Next session presents some project in relation with these algorithms.

Related Work

In the literature, for similar tasks, several approaches were applied based on object detection and pattern recognition such as HOG/ DPM, KLT/RMR and Deep Learning [START_REF] Cho | Real-time Pedestrian Detection with Deformable Part Models[END_REF]. For example, in Google Robot's Project [START_REF] Gershgon | Google's Robot Are Learning How to Pick Things Up[END_REF][START_REF] Levine | Learning Hand-Eye Coordination for Robotic Grasping with DeepLearning and Large-Scale Data Collection[END_REF], we can find a deep learning model applied to articulated robot for how to pick things up. In Kitti Vision Benchmark Suite Project [START_REF] Geiger | Object Detection Evaluation[END_REF], an object detection and orientation estimation benchmark is carried out. In [START_REF] Forson | Understanding SSD MultiBox-Real Time Object Detection in Deep Learning[END_REF], as an example of end-toend object detection from Microsoft is shown. For the task of detecting objects in images, recent methods based on CNN like SSD [START_REF] Geiger | Object Detection Evaluation[END_REF][START_REF] Liu | Single-Shot Multibox Detector[END_REF] allows multiple objects detection. In many applications of object detection, it is important to estimate their 3D orientation. In outdoor environments, solutions based on DL has been recently shown to outperform other monocular approaches for detecting cars and estimating their 3D orientation [START_REF] Chabot | Deep MANTA: A Coarse-to-fine Many-Task Network for joint 2D and 3D vehicle analysis from monocular image[END_REF][START_REF] Mousavian | 3D Bounding Box Estimation Using Deep Learning and Geometry[END_REF]. In indoor environments, it has been shown that using synthetic 3D models of objects to be detected in the learning process of a CNN can allow simplifying it [START_REF] Mousavian | 3D Bounding Box Estimation Using Deep Learning and Geometry[END_REF]. In [START_REF] Doll | Pedestrian Detection: An Evaluation of the State of the Art[END_REF][START_REF] Yan | Robust Multi-Resolution Pedestrian Detection in Traffic Scenes[END_REF], we can find an evaluation of the state of the art based object (pedestrian) detection which uses HOG/DPM approaches.

OBJECT DETECTION ALGORITHMS 3.1. Introduction

In order to identify the most suitable approach to our object/pedestrian detection application for autonomous vehicle, we need to make the feasibility of several scientific concepts in pattern recognition such as the KLT/RMR, SIFT/SURF, HOG/DPM but especially recent approaches related to the AI such as DL. In this paper, we will focus on pedestrian detection-based HOG/DPM approaches and how to improve them.

Classical Approaches

We started our experimentation by implementing point of interest approaches like Scale Invariant Feature Transform (SIFT) and Speeded-Up Robust Features (SURF) developed by D. Lowe [START_REF]Yolo Homepage[END_REF]. The method makes it possible to transform visual features, which are invariant to scale, rotation and illumination. Despite their robustness to perspectives changing and lighting conditions, we found that the approach is not robust for pedestrian detection. SURF is better up to twice as fast as SIFT. However, SIFT is better when scale changing or an increase in lighting is applied to the image. For pedestrian detection, SIFT and SURF therefore remain insufficient. We have experimented Kanade-Lucas Tomasi (KLT) approach [START_REF] Koen | Segmentation As Se-lective Search for Object Recognition[END_REF] for extraction of points of interest and tracking between an image taken at t-1 and image taken at t. The approach is highly accurate and is fast but not robust to perturbations. This is why we have decide to experiment the Robust Multiresolution Estimation of Parametric Motion Models (RMR) approach [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], which has very low precision but is considered as very robust. We have obtained the same results as with KLT approach. A better solution could be a hybrid approach KLT/RMR in order to have the benefits of each approach.

Pattern Recognition-based HOG/DPM

The pattern recognition algorithms calculate the image features. They use classifiers under databases of positive images (with pedestrian) and negative images (without pedestrian). They have the advantage of being accurate and gives relatively good results; however, the calculating time is high. We therefore experimented three approaches: HAAR, HOG and DPM. Pseudo-HAAR Features. HAAR classifiers use pseudo-HAAR features [START_REF] Viola | Rapid Object Detection using a Boosted Cascade of Simple Features[END_REF]. Instead of using pixel intensity values, the pseudo-HAAR features use the contrast variation between rectangular and adjacent pixel clusters. To construct a pseudo-HAAR feature, two or three adjacent clusters with relative contrast variation are required. It is possible to change the size of features by increasing or decreasing the pixel clusters. Thus, it makes possible the use of these features on objects with different sizes. HOG Algorithm. HOG is a descriptor containing image key features. These features are represented by the distribution of image gradient directions. HOG is the best-known algorithm in the field of pattern recognition. It consists of five steps: 1. Sizing the calculation window, 2. Calculation of image gradients using simple masks, 3. Image division of 64x128 into 8x8 cells. For each cell, HOG algorithm calculates the histogram, 4. Normalization of histograms by 16x16 blocks, and 5. Calculation of the size of the final descriptor. This descriptor is then given to SVM classifier. DPM Algorithm. The hardest part for object detection is that there are many variance, which could arise from illumination, viewpoint, non-rigid deformation, occlusion, and intra-class variability [START_REF] Su | State of the Art object Detection Algorithms[END_REF]. The DPM is trying to capture those variances. The detector will first find a match by coarser root filter, and then using its part models to fine-tune the result. Recently, new algorithms have been developed in order to make DPM Faster and more efficient [START_REF] Su | State of the Art object Detection Algorithms[END_REF][START_REF] Dollar | Pedestrian Detection: An Evaluation of the State of the Art[END_REF].

Pedestrian Detection-based HAAR/HOG/DPM

We carried out a wide range of experiments under 6 different databases dedicated to the pedestrian detection: ETH, INRIA, TUD Brussels, Caltech, Daimler and our own ESIGELEC dataset dedicated to the pedestrian detection. The Fig. 1 show examples of results obtained under the 3 datasets. Table 1 gives the comparative study.

Pedestrian Detection-based Deep Learning Pattern Recognition-based Deep Learning

Recently, many detection algorithms using selective search [START_REF] Su | State of the Art object Detection Algorithms[END_REF][START_REF] Koen | Segmentation As Selective Search for Object Recognition[END_REF] as region proposals, have been used to avoid exhaustive sliding window method. In addition, Deep Learning (CNN) [START_REF] Su | State of the Art object Detection Algorithms[END_REF][START_REF] Krizhevsky | Imagenet classification with deep convolutional neuralnetworks[END_REF] has proved to be successful in ImageNet classification challenge. Since the progress of DPM model is now restrictive (i.e. next session), Deep learning is trying to do detection in different way. We have implanted You Only Look Once (YOLO) as a real time object detection [START_REF]Yolo Homepage[END_REF]. Prior detection, systems repurpose classifiers or localizers to perform detection. They apply the model to an image at multiple locations and scales. High scoring regions of the image are considered detections [START_REF] Su | State of the Art object Detection Algorithms[END_REF][START_REF] Krizhevsky | Imagenet classification with deep convolutional neuralnetworks[END_REF].

Experiment Results. The whole of experiments has been carried out under 6 datasets. Constrained by pages limit number, we present results obtained on two datasets: Caltech and ESIGELEC. The object detection rate used is calculated as Intersection over Union Ratio (IoU). The IoU represents the relationship between the area of overlap and union of ground truth and predicted bounding box [START_REF]Multibox SSD Homepage[END_REF]. The results have been obtained under GPU Nvidia Quadro K4000M Machine. Fig. 2 shows some results obtained under YOLO and SSD algorithm.

PEDESTRIAN DETECTION AND TRACKING-BASED FASTER HOG/DPM ALGORITHM 4.1. Improved HOG Algorithm

We have identified 4 methods to improve HOG/DPM algorithm, which corresponds to the five algorithm HOG steps. In order to be able to make comparison, a classifier was trained from INRIA and TUD-Brussels dataset images.

The number of available images is low which has an impact on the pedestrian detection quality. The objective is to improve the quality of HOG/DPM pedestrian detection and to reduce, significantly, the computation time for pedestrian detection. The tests were carried out under the ESIGELEC dataset; 1. Gamma Correction: in order to improve the pedestrian image quality, we performed a gamma processing on the images to be trained and tested. We found fewer parasites in the processed images. 2. Image Resizing: HOG algorithm uses in its calculations images of 64x128 sizes. We performed calculation with windows of 128x256. By doubling the size of the calculation window, we have improved the accuracy but also doubled the computation time (for example from 58ms in the classic HOG to 115ms for the Faster-HOG). 3. Negative Gradients: when calculating gradients, Faster-HOG uses signed gradients (0 to 180°) and unsigned gradient (0 to 180°) like classic HOG. This allows the calculation of histogram with 18 values (9 values in classic HOG). The calculation time does not vary, however, by taking into account, the negative gradients, and we found a presence of parasites, which does not improve the classic HOG. 4. Normalization Vector: as a last step, HOG performs a standardization of 2x2 cells, i.e. 32x32 pixels with a pitch of 16x16. The object detection is degraded and the computation time doubles, which cannot be considered as a classic HOG improvement.

Faster DPM Algorithm

The DPM algorithm is applied on the entire and this is done at each iteration of the pedestrian video sequence. In order to reduce the computing time, the idea is to apply DPM algorithm only in a Region of Interest (RoI) in which the target is located. This will drastically reduce the computing time and will also isolate the object. Firstly, the DPM is applied all over the image once to locate the object. Secondly, and after obtaining a RoI surrounding the object to be detected, we a New RoI (NRoI) by providing a tolerance zone (a new rectangle which is larger than the first one). Starting from the second iteration, DPM algorithm is applied only in this new image, which is represented by NRoI. If the target to be detected is lost, the DPM algorithm is re-applied over the entire image.

Pedestrian Distance Estimated

For better detection of pedestrian, it is necessary to estimate their distance from the vehicle. Our system is based on monocular camera, which makes it very difficult to measure the distance. The law called "Inverse Squares" [START_REF]Multibox SSD Homepage[END_REF], used in astronomy to calculate the distance between stars, inspired us: "physical quantity (energy, force, etc.) is inversely proportional to the square of the distance of stars". By analogy, the physical quantity represents the area of our RoI.

We have used a parametric approach. Measurements, taken at an interval of 50cm, were taken and the object RoI surface was recorded at each time.

Experiment Results

We have carried out several tests under 6 datasets dedicated to pedestrian detection. In this section, we present the tests carried out on the ESIGELEC dataset including tests scenarios under real traffic conditions in the shopping center car park and Rouen city center. The results obtained are shown in Fig. 3 in which we can find the distance estimated on the top of each pedestrian box.

CONCLUSION

In this paper, we have presented a comparison study between different approach dedicated to pattern recognition and object detection. We have presented our contribution for improving both HOG and DPM algorithms. We have also implemented DL based Yolo and SSD algorithm for pedestrian detection. An innovative method for distance calculation of pedestrians is presented in this paper. The approach was validated within experiments and the accuracy is good with only 5% of errors (see [START_REF] Chen | Real Time Pedestrian and Object Detection and Tracking-based Deep Learning: Application to Drone Visual Tracking[END_REF] for more details).

The system detects and recognize not only pedestrian but also cars. The system is generic so that it is "applicable" on any type of platform and environment. This work aims to show the feasibility of scientific and technological concepts that affect HOG/DPM based detection and pattern recognition, but also AI approaches such as DL (like YOLO and SSD). We have validated the developments with a vehicle in real traffic conditions (Mall Center Car Park, Rouen City Center).

ACKNOWLEDGMENT

This project was co-financed by the European Union with the European regional development fund (ERDF, 18P03390/18E01750/18P02733) and by the Haute-Normandie Regional Council via the M2SINUM project.

Fig 1 .

 1 Fig 1. Comparison between HAAR (left), HOG (middle) and DPM (right) applied under three different datasets: TUD-Brussels (top row), ETH (middle row) with 640x480 image resolution, and ESIGELEC (bottom row) with 960x540 resolution.

Fig 2 .

 2 Fig 2. Pedestrian detection-based deep learning (Yolo/SSD).

Fig 3 .

 3 Fig 3. Pedestrian detection with Faster-DPM under ESIGELEC Dataset. Top row: ESIGELEC and Rouen City center, Middle row: Rouen mall center car park, Bottom row: Rouen city center pedestrian detection.

Table 1 .

 1 HAAR/HOG/DPM pedestrian detection comparison.

	Dataset	HAAR	HOG	DPM
	TUD-	Computing	Computing	Computing
	Brussels	time: 51ms,	time: 154ms,	time: 308ms,
		quality	quality	quality
		detection: +	detection: ++	detection: +++
	ETH	Time: 37ms,	Time: 108ms,	Time: 247ms,
		detection: +	detection: ++	detection: +++
	ESIGELEC	Time: 50ms,	Time: 197ms,	Time: 342ms,
		detection: +	detection: ++	detection: +++

  Many thanks to SEGULA Engineering France company for his help in the development of this work. Many thanks to Technological Resources Center (TRC) of ESIGELEC/IRSEEM for his help in testing phase.

 [START_REF] Cho | Real-time Pedestrian Detection with Deformable Part Models[END_REF]This project was co-financed by the European Union with the European regional development fund (ERDF, 18P03390/18E01750/18P02733) and by the Haute-Normandie Regional Council via the M2SINUM project.


Ararat Harutyunyan

Michael Lampis

Vadim Lozin

Jérôme Monnot

Maximum Independent Sets in Subcubic Graphs: New Results

Keywords: Independent Set, Sub-Cubic Graphs, Apple-Free Graphs

We consider the complexity of the classical Independent Set problem on classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. It is well-known that a necessary condition for Independent Set to be tractable in such a class (unless P=NP) is that the set of forbidden induced subgraphs includes a subdivided star S k,k,k , for some k. Here, S k,k,k is the graph obtained by taking three paths of length k and identifying one of their endpoints. It is an interesting open question whether this condition is also sufficient: is Independent Set tractable on all hereditary classes of subcubic graphs that exclude some S k,k,k ? A positive answer to this question would provide a complete classification of the complexity of Independent Set on all classes of subcubic graphs characterized by a finite set of forbidden induced subgraphs. The best currently known result of this type is tractability for S2,2,2-free graphs. In this paper we generalize this result by showing that the problem remains tractable on S 2,k,k -free graphs, for any fixed k. Along the way, we show that subcubic Independent Set is tractable for graphs excluding a type of graph we call an "apple with a long stem", generalizing known results for apple-free graphs.

Introduction

In a graph, an independent set is a subset of vertices no two of which are adjacent. The maximum independent set problem asks to find in a graph G an independent set of maximum size. The size of a maximum independent set in G is called the independence number of G and is denoted α(G).

The maximum independent set problem is one of the first problems that were shown to be NP-hard. Moreover, the problem remains NP-hard under substantial restrictions. In particular, it is NP-hard for graphs of vertex degree at most 3, also known as subcubic graphs. In terms of vertex degree, this is the strongest possible restriction under which the problem remains NP-hard, since for graphs of vertex degree at most 2 the problem is solvable in polynomial time. However, with respect to other parameters the restriction to subcubic graphs is not best possible, as the problem remains NP-hard for subcubic graphs of girth at least k for any fixed value of k [START_REF] Murphy | Computing independent sets in graphs with large girth[END_REF], where the girth of a graph is the size of a smallest cycle. In other words, the problem is NP-hard for (C 3 , . . . , C k )-free subcubic graphs for each value of k, where C k is a chordless cycle of length k. The idea behind this conclusion is quite simple: it is not difficult to see that a double subdivision of an edge increases the independence number of the graph by exactly one, and hence, by repeatedly subdividing the edges of a subcubic graph G we destroy all small cycles in G, i.e. we transform G into a graph of large girth.

Let us observe that by means of edge subdivisions we can also destroy small copies of some other graphs, in particular, graphs of the form H k represented in Figure 1 (left) . Therefore, the maximum independent set problem remains NP-hard for (C 3 , . . . , C k , H 1 , . . . , H k )-free subcubic graphs for each value of k.

Let us denote by S k the class of (C 3 , . . . , C k , H 1 , . . . , H k )-free subcubic graphs and by κ(G) the maximum k such that G ∈ S k . If G belongs to no class S k , then κ(G) is defined to be 0, and if G belongs to all classes S k , then κ(G) is defined to be ∞. Also, for a set of graphs M , κ(M ) is defined as κ(M ) = sup{κ(G) : G ∈ M }. With this notation, we can derive the following conclusion from the above discussion (see e.g. [START_REF] Vadim | Graphs without large apples and the maximum weight independent set problem[END_REF]).

Theorem 1. Let M be a set of graphs. If κ(M ) < ∞, then the maximum independent set problem is NP-hard in the class of M -free subcubic graphs.

This theorem suggests that, unless P = N P , the maximum independent set problem is solvable in polynomial time in the class of M -free graphs only if the parameter κ is unbounded in the set M . There are three basic ways to unbind this parameter in M :

1. include in M a graph G with κ(G) = ∞; 2. include in M graphs with arbitrarily large induced cycles; 3. include in M graphs with arbitrarily large induced subgraphs of the form H k .

To give an example of a polynomial-time result of the first type, let us observe that κ(G) = ∞ if and only if every connected component of G has the form S i,j,k represented in Figure 1 (right). We call any graph of the form S i,j,k a tripod. In other words, if the set M of forbidden induced subgraphs is finite, then M must contain a graph for which every component is a tripod for the maximum independent set problem in the class of M -free subcubic graphs to be polynomialtime solvable (assuming P =NP). In [START_REF] Vadim | From matchings to independent sets[END_REF], it was conjectured that this condition is also sufficient. Moreover, for graphs of bounded vertex degree the problem can be easily reduced to connected forbidden induced graphs, in which case the conjecture can be restated as follows.

Conjecture 1. The maximum independent set problem is polynomial-time solvable for G-free subcubic graphs if and only if G is a tripod.

One of the minimal non-trivial tripods is the claw S 1,1,1 . The problem can be solved for the claw-free graphs in polynomial time even without the restriction to bounded degree graphs [START_REF] Minty | On maximal independent sets of vertices in claw-free graphs[END_REF]. In [START_REF] Vadim | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph[END_REF], the result for claw-free graphs was extended to S 1,1,2 -free graphs, also known as fork-free graphs, and again without the restriction to bounded degree graphs. However, any further extension becomes much harder even for bounded degree graphs, and only recently a solution was found for S 2,2,2 -free subcubic graphs [START_REF] Vadim | On the maximum independent set problem in subclasses of subcubic graphs[END_REF]. Currently, this is one of the few maximal subclasses of subcubic graphs with polynomial-time solvable independent set problem. Now we turn to polynomial-time solutions of the second type, i.e. classes of graphs where forbidden induced subgraphs contain arbitrarily large chordless cycles. Clearly, in this case the set of forbidden induced subgraphs must be infinite. A typical example of this type deals with classes of bounded chordality, i.e. classes excluding all chordless cycle of length at least k for a constant k. Without a restriction to bounded degree graphs a solution of this type is known only for k = 4, i.e. for chordal graphs [START_REF] Gavril | Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph[END_REF], and is unknown for larger values of k. Together with the restriction to bounded degree graphs bounded chordality implies bounded tree-width [START_REF] Hans | Treewidth for graphs with small chordality[END_REF] and hence polynomial-time solvability of the maximum independent set problem. In other words, the problem can be solved for (C k , C k+1 , . . .)-free graphs of bounded vertex degree for each value of k ≥ 3.

An apple A k , k ≥ 4, is a graph formed of a chordless cycle C k and an additional vertex, called the stem, which has exactly one neighbour on the cycle C k . The class of (A 4 , A 5 , . . .)-free graphs generalizes both chordal graphs and claw-free graphs, and a solution for the maximum independent set problem in this class was presented in [START_REF] Brandstädt | Independent sets of maximum weight in apple-free graphs[END_REF]. In case of bounded degree graphs this solution can be extended to graphs without large apples, i.e. to (A k , A k+1 , . . .)-free graphs of bounded vertex degree for any fixed value of k [START_REF] Vadim | Graphs without large apples and the maximum weight independent set problem[END_REF].

Generalizing both the subcubic graphs without large apples and S 2,2,2 -free subcubic graphs, in the present paper we prove polynomial-time solvability of the maximum independent set problem for subcubic graphs excluding large apples with a long stem. An apple with a long stem A * k is obtained from an apple A k by adding one more vertex which is adjacent to the stem of A k only. We show that for any fixed value of k, the maximum independent set problem in the class of (A * k , A * k+1 , . . .)-free subcubic graphs can be solved in polynomial time. Observe that this class contains all S 2,p,p -free subcubic graphs for any fixed p < k (as long as k ≥ 6) and hence our result brings us much closer to the proof of Conjecture 1.

Preliminaries

All graphs in this paper are simple, i.e. undirected, without loops and multiple edges. The vertex set and the edge set of a graph G is denoted by V (G) and E(G), respectively. The neighbourhood

N (v) of a vertex v ∈ V (G) is the set of vertices of G adjacent to v. The degree of v ∈ V (G)
U ⊆ V (G) is denoted G[U ]. If G contains no induced subgraph isomorphic to a graph H, we say that G is H-free.
Outline of the proof. To prove polynomial-time solvability of the maximum independent set problem in the class of (A * k , A * k+1 , . . .)-free subcubic graphs, 1. We start by checking if the input graph G has an induced copy of S 2,2,2 . If G is S 2,2,2 -free, then the problem can be solved for G in polynomial time [START_REF] Vadim | On the maximum independent set problem in subclasses of subcubic graphs[END_REF]. Otherwise, we proceed to checking whether G has an induced cycle of length at least p = 300k. This can be done in polynomial time, as shown in Lemma 1 below. If G does not contain induced cycles of length at least p, then the tree-width of G is bounded by a function of k [START_REF] Hans | Treewidth for graphs with small chordality[END_REF] and hence the problem can be solved in polynomial time for G. 2. If G contains an induced copy of S 2,2,2 and a large induced cycle C, then in the absence of large induced apples with long stems we prove that it must contain a large extended cycle C * , which is a graph obtained from C by adding two vertices that create a C 6 together with four consecutive vertices of C (see Figure 7 in Section 4). This is shown in Section 3. An important ingredient of this proof is the assumption that the input graph G is connected and has no separating cliques, i.e. cliques whose removal disconnects the graph. A polynomial-time reduction of the maximum independent set problem to graphs without separating cliques can be found in [START_REF] Endre | Decomposition by clique separators[END_REF][START_REF] Whitesides | An algorithm for finding clique cut-sets[END_REF]. 3. After the previous two steps we can assume that our graph contains a large extended cycle. In Section 4 we show how to destroy such a large extended cycle by means of various local reductions. Each of them transforms G into a smaller graph G in the same class with a fixed difference α(G) -α(G ).

The set of reductions is described in Section 4.1 and their application to a graph G containing a large extended cycle is described in Section 4.2. By destroying the large extended cycle C * , we destroy either the cycle C or the induced copy of S 2,2,2 (or both) and return to Step 1 to check if there are other copies of a large induced cycle or an induced S 2,2,2 .

The first step of the proof outline above is rather straight-forward and relies on Lemma 1, stated below. The main difficulties lie in the second step (showing that if the graph has an S 2,2,2 and a large induced cycle, then it has a long extended cycle), which is handled in Section 3; and in the third step (showing how to deal with a large extended cycle), which is handled in Section 4. Due to space constraints, some proofs have been moved to the appendix. Lemma 1. For each p there is an algorithm running in time n O(p) which decides if a given n-vertex graph contains an induced cycle of length at least p.

From large cycles to extended large cycles

We recall that C * denotes an extended cycle, i.e. the graph obtained from a cycle C by adding two vertices that create a C 6 together with four consecutive vertices of C (see Figure 7 in Section 4). Also, A * p denotes an apple with a long stem, where p stands for the size of the cycle in the apple. An apple with a long stem consisting of a cycle C and two stem vertices x, y will be denoted C x,y .

The main goal of this section is to show that if G contains a large induced cycle and an induced copy of S 2,2,2 , then it contains either a large induced extended cycle or a large induced apple with a long stem. This will be shown in two steps in Lemmas 2 and 3. Since we are dealing with graphs which do not contain large induced apples with long stems, the result of this section is that we may assume that our graph contains a large induced extended cycle. We note that throughout this section we will assume that our graph does not contain any separating cliques; in case it does, it is known how to reduce solving Independent Set to smaller graphs that do not contain such cliques [START_REF] Endre | Decomposition by clique separators[END_REF][START_REF] Whitesides | An algorithm for finding clique cut-sets[END_REF].

Destroying large extended cycles

According to the previous section, if an (A * k , A * k+1 , . . .)-free subcubic graph G contains a large induced cycle and an induced copy of S 2,2,2 , then it must contain a large extended cycle C * . The goal of the present section is to show how to destroy large extended cycles by means of various local graph reductions. We describe these reductions in Section 4.1 and apply them to large extended cycles in Section 4.2.

Graph reductions

Φ-reduction and house-reduction We start with the Φ-reduction introduced in [START_REF] Vadim | On the maximum independent set problem in subclasses of subcubic graphs[END_REF]. It applies to a graph G containing an induced copy of the graph Φ represented on the left of Figure 2 and consists in replacing Φ by the graph on the right of Figure 2. Total struction and subgraph reduction Total struction is an operation that was introduced in [START_REF] Alexe | Struction revisited[END_REF]. Roughly speaking, this operation allows us to identify a part of the graph that can be replaced by an auxiliary graph in a way that decreases the size of the maximum independent set by a precise value. Even though this operation is quite powerful, in this paper we will only need to use two special cases of total struction, given by Corollaries 1 and 2.

Corollary 1. For any graph G = (V, E) and H ⊆ V let N [H] denote the set of vertices at distance at most 1 from H. Then, we have the following

: if α(G[H]) = α(G[N [H]]), then α(G[V \ N [H]]) = α(G) -α(G[H]).

Informally, Corollary 1 gives rise to the following transformation: if we can find a set of vertices H such that G[H] and G[N [H]] have the same maximum independent set, then we simply select an independent set of H in our solution and delete all vertices of N [H]. The deletion of N [H] in the case when α(G[H]) = α(G[N [H]]

) was called in [START_REF] Vadim | On the maximum independent set problem in subclasses of subcubic graphs[END_REF] the H-subgraph reduction. It is not difficult to check that if A 1 , A 2 , or A 3 (see Figure 6) is an induced subgraph of a subcubic graph, then we can use Corollary 1 as we have:

-α(A 1 [{2, 3, 5, 6, x, y}]) = α(A 1 ) = 3, -α(A 2 [{1, 2, 3, 5, 6, x, y}]) = α(A 2 ) = 4, -α(A 3 [{1, 2, 3, 5, 6, x, y}]) = α(A 3 ) = 4. Lemma 8. If A 1 , A 2 , or A 3 is an induced subgraph of a subcubic graph G, then α(G -A 1 ) = α(G) -3, α(G -A 2 ) = α(G) -4, α(G -A 3 ) = α(G) -4. Corollary 2. Let G = (V, E) be a subcubic graph and K ⊆ V such that G[K] induces a K 2,3 .
Then, if G is the graph obtained from G by deleting the vertices of K and introducing a new vertex z connected to N (K), we have (i) α(G ) = α(G) -2 and (ii) if G contains an apple with a long stem A * p , then G also contains an apple with a long stem A * p , with p ≥ p.

Applying graph reductions to large extended cycles

Let G be an (A * k , A * k+1 , . . .)-free subcubic graph. For ease of terminology and notation we will refer to any A * t with t ≥ k simply as a large apple with a long stem. According to Section 3, we may assume that G contains a large extended cycle C * p , i.e. a graph that consists of an induced cycle of length p, plus two extra vertices which form a C 6 together with four consecutive vertices of the cycle and have no other neighbours in C * p . We denote the vertices of an extended cycle as shown in Figure 7, where we have given labels to the vertices of the C 6 , plus some other interesting vertices. In the remainder we use simply C * to denote the extended cycle and C 6 to denote the set of vertices {1, 2, 3, 4, 5, 6}. Without loss of generality, we assume that p ≥ 3k. We will now go through a sequence of cases that covers all possible ways in which C * may be connected to the rest of the graph.

Case 0: Vertices 2 and 3 both have degree 2 in G. In this case we delete 2, 3 from the graph and add the edge connecting 1 to 4. This decreases α(G) by exactly 1. Also, it is not difficult to check that this transformation does not create any new forbidden induced subgraphs.

Because of the above we can assume that the set {2, 3} has a neighbour outside of C * . We call this vertex x. Without loss of generality we assume that x is connected to 2. Let us consider how x is connected to the rest of C * . The rest of the cases are defined as follows.

-Case 1.1:

N (x) ∩ C * = {2} -Case 1.2: N (x) ∩ C 6 = {2} and x has exactly one neighbour in C * \ C 6 -Case 1.3: N (x) ∩ C 6 = {2} and x has two neighbours in C * \ C 6
If we rule out the above cases we conclude that x has at least two neighbours in C 6 . Since the degrees of 1, 4 are already three in C * , we conclude that x has at least two neighbours in {2, 3, 5, 6}. Let us also rule out two further cases.

-Case 1.4: N (x) ∩ C 6 = {2, 3}; -Case 1.5: |N (x) ∩ C 6 | = 3
Lemma 9. If one of Cases 1.1-1.5 applies, then the instance can be simplified in polynomial time. If none of Cases 1.1-1.5 applies, then either

N (x)∩C 6 = {2, 5} or N (x) ∩ C 6 = {2, 6}.
Thus, we may suppose: N (x) ∩ C 6 = {2, 5} or N (x) ∩ C 6 = {2, 6}. We handle these two cases separately in the following subsections.

x is adjacent to 2 and 6 Lemma 10. Let x be a vertex adjacent to 2 and 6 and assume x has a neighbour y not in C * . Then G contains an induced Φ or an induced Π or an induced Γ or an induced Θ.

Proof. If y is adjacent to 3, then by Lemma 9 (and symmetry) y is also adjacent to 5 and hence vertices 1, 2, 3, 4, 5, 6, x, y induce a Θ.

If y is adjacent to c, then vertices 2, 3, 4, x, y, c create a cycle of length 6 which, together with the path 1ab . . . d gives a second large extended cycle. Therefore, by Lemma 9 applied to this extended cycle, vertex 5 must be adjacent to y and hence vertices 1, 2, x, 6, y, 5, c, 4 induce a Φ.

If y is adjacent to a, then vertices a, y, 1, 2, x, 6, 3, 4, 5 induce a Γ with a possible missing common neighbour of 3 and 5 (any neighbour of these vertices must be common by Lemma 9).

If y is adjacent to b and not adjacent to a, then vertices a, b, y, 1, 2, x, 6, 3, 4, 5 induce a Π with a possible missing common neighbour of 3 and 5 (any neighbour of these vertices must be common by Lemma 9).

From now on, we assume y has no neighbours in {3, 5, a, b, c}. If y has neighbours on C * \ C 6 , then we can distinguish at most 3 cycles containing y as shown in Figure 8 (if y has only 1 neighbour on C * \ C 6 , the cycle C 2 is missing).

We observe that at least one of the cycles C 1 , C 2 , C 3 is large, i.e. has length at least p/3. Then G contains a large apple with a long stem

b c a 4 2 1 3 x y C 1 C 3 C 2 Fig. 8. Vertex y has neighbours on C -C * ∪ {x, y} \ {5, 6} if y has no neighbours on C * \ C 6 , -C 1 ∪ {3, 4} if C 1 is large, -C 2 ∪ {x, 2} if C 2 is large, -C 3 ∪ {1, a} if C 3 is large.
A contradiction in all cases shows that y has a neighbour in {3, 5, a, b, c} and hence G contains an induced Φ or an induced Π or an induced Γ or an induced Θ.

We therefore find ourselves in the following context: N (x) ∩ C 6 = {2, 6} and N (x) \ C * = ∅. Before we proceed, let us identify another relevant vertex. If 3 has a neighbour outside C * we call that vertex y. By Lemma 9 (and appropriate symmetry) y is also connected to 5. We have also argued that x and y are not adjacent. We will in the remainder assume that the degree of x is at least as large as the degree of y. This is without loss of generality, as the two vertices can be exchanged by an appropriate automorphism of C * . In what follows, we analyze all possible adjacencies of x and y to the vertices of C * . Case 2.2: Assume x has degree 2 and y exists (therefore, y is connected to 3, 5). We have assumed without loss of generality that x has at least as high degree as y, therefore y has no other neighbour. We delete from the graph vertices 2, 3, x, y. If G is the new graph, we claim that α(G ) = α(G) -2. The inequality α(G ) ≥ α(G) -2 is clear, since no independent set can take more than two of the deleted vertices. To see that α(G) ≥ α(G )+2, take a maximum independent set in G . If it contains vertex 5, then it does not contain 4 or 6. Therefore, we can augment it with x, 3. If it contains 6, we can augment it similarly by adding y, 2. Finally, if it contains neither 5 nor 6, we augment it with x, y.

Case 2.3: If x is connected to a, {x, 1, a, 2, 6} induces a K 2,3 , we can therefore invoke Corollary 2 to simplify the graph.

Case 2.4: If x is connected to c, then x61ab . . . cx together with 3, 4 form a large apple with a long stem. Case 2.8: Assume x is connected to b, y exists and it has degree 2 (that is, y is connected only to 3, 5). We delete from the graph the vertices {x, y, 1, 2, 3, 5, 6} and add a new vertex z adjacent to a, b, 4. We claim α(G ) = α(G)-3. To see that α(G) ≥ α(G )+3 take an independent set of the new graph. If it does not include z then we augment it with {2, 6, y}; if it does include z, it does not contain any of a, b, 4, so we replace z with {1, x, 3, 5}. To see that α(G ) ≥ α(G) -3 take an independent set of G. If it contains at most three of the deleted vertices we are done. If it contains four, these must be {1, x, 3, 5}, therefore the set does not contain any of a, b, 4; in this case we replace the deleted vertices by z.

The new graph does not have a large apple with a long stem that uses z and both a, b, since that would induce a triangle. If, on the other hand, it has an apple with a long stem that uses z and at most two of its neighbours, then G also has a subdivided copy of the same subgraph if we replace z with 1, 2, 3. Case 2.9: Finally, suppose x is connected to b, y exists and y has degree 3. Since x and y have the same degree, we may exchange their roles, and by symmetry and the same case analysis that we did for x we conclude that y must be connected to d (otherwise one of the previous cases applies). We transform the graph as follows: we delete the vertices 1, 2, 3, 4, 5, 6, x, y and add two new vertices z, w such that z, w are connected to each other, z is connected to a, b, and w is connected to c, d. We claim that α(G ) = α(G) -3. First, to obtain α(G ) ≥ α(G) -3, take a maximum independent set of G. If it contains a vertex from a, b and a vertex from c, d, then it contains at most three of the deleted vertices, since the six deleted vertices which are not adjacent to a vertex of the independent set induce a cycle of length 6. In all other cases, the independent set in G contains at most four of the deleted vertices. However, if the set does not contain any of a, b, we can augment it with z in G , while if it does not contain any of c, d we can add to it w. To see that α(G) ≥ α(G ) + 3, take a maximum independent set in G . If it is using z, then it does not contain a or b. In G we replace z with 1, x, 3, 5. The situation is symmetric if the set contains w. Finally, if it does not contain either z or w, we observe that deleting the neighbours of the set among the removed vertices gives a cycle of length 6, of which we can select three vertices. The transformation does not introduce a new large apple with a long stem, since the closed neighbourhoods of z, w include a triangle, therefore if one or two of these vertices is used in the apple we can replace them with an appropriate induced path through the deleted vertices in G.

x is adjacent to 2 and 5 Lemma 11. Let x be a vertex adjacent to 2 and 5 and assume x has a neighbour y not in C * . Then G contains an induced A 1 or an induced A 2 or an induced A 3 (Figure 6).

Proof. If y is adjacent to 3 or 6, then y is adjacent to both 3 and 6 (Lemma 9) and hence G contains an induced A 1 . Assume y is adjacent to a. Then, if all three vertices 3, 6, y have degree 2 in G, then G contains an induced A 2 . If vertex 3 has degree three, it has a common neighbour with 6 (by Lemma 9), call this neighbour z. We claim that z must also be connected to y, which will give an induced A 3 . To see this, consider the set of vertices (C * \{2, 3})∪{x, y}. This set induces an extended cycle, where the C 6 is now formed by a, 1, 6, 5, x, y. Since z is connected to 6, it must be connected to one of {x, y} (Lemma 9). However, x already has three neighbours (2, 5, y), therefore, z is connected to y.

If y is adjacent to c this is symmetric to y being adjacent to a. So, we suppose that y is adjacent to none of 3, 6, a, c. The rest of the proof is similar to that of Lemma 10 with the only difference that if y is adjacent only to b this time we can find a large apple with a long stem, where the stem is {1, 6} and the cycle goes through byx234cd . . . b. Lemma 12. Let x be a vertex adjacent to 2 and 5 and assume x has a neighbour in C * \ C 6 . Then this neighbour is one of a and c.

To complete the case analysis, we prove the following lemma. Lemma 13. Let x be a vertex adjacent to 2 and 5 and suppose that if x has a neighbour in C * \ C 6 , then this neighbour is a. Then we can in polynomial time reduce our instance to a smaller instance.

Conclusion

Summarizing the discussion in the previous sections, we make the following conclusion, which extends several previously known results.

Theorem 2. Maximum independent set can be solved in polynomial time in the class of (A * k , A * k+1 , . . .)-free subcubic graphs for any fixed value of k. Since A * t contains S 2,k,k for any t > 2k + 1, we derive the following corollary Corollary 3. Maximum independent set can be solved in polynomial time in the class of S 2,k,k -free subcubic graphs for any fixed value of k.

This result brings us closer to the dichotomy of Conjecture 1. However, proving this conjecture in its whole generality remains a challenging open problem.

Fig. 1 .

 1 Fig. 1. The graphs H k (left) and S i,j,k (right)

Lemma 2 .

 2 Let G be a subcubic graph without separating cliques. If G has an induced cycle C of length p and an induced copy of S 2,2,2 , then G has an induced cycle of length at least p/12 containing the center of an induced S 2,2,2 . Lemma 3. Let G be a subcubic graph without separating cliques. If G has an induced cycle C of length p containing the center of an induced S 2,2,2 , then G has an induced extended cycle C * t or an induced apple with a long stem A * t with t ≥ p/8.

Fig. 3 .Lemma 6 .Lemma 7 .Fig. 5 .

 3675 Fig. 3. Π-reduction

Graph A 2 3 Fig. 6 .

 236 Fig. 6. Graphs A1, A2 and A3

Fig. 7 .

 7 Fig. 7. An extended cycle

Case 2 . 1 :

 21 If x has degree 2 and y does not exist (therefore 3, 5 have degree 2), then we apply the H-subgraph reduction (Corollary 1) with H = {x, 3, 5}, in which case α(G[H]) = α(G[N [H]]) = 3 and hence the removal of N [H] decreases α(G) by 3.

Case 2 . 5 :Case 2 . 6 :Case 2 . 7 :

 252627 If x is connected to d, then x21ab . . . dx together with 3, 4 form a large apple with a long stem. If x is connected to a vertex f of C * in the path from b to d (but not b or d), then: if f is closer to a than to c, we take the path xf . . . dc432x plus 1, a; otherwise we take xf . . . ba12x plus 3, 4. In both cases these form a large apple with a long stem. If x is connected to b and y does not exist, then we apply the Hsubgraph reduction with H = {x, 1, 3, 5}. It is not hard to check that α(G[H]) = α(G[N [H]]) = 4 and hence the removal of N [H] decreases α(G) by 4.

  is the number of its neighbours, i.e. |N (v)|. As usual, P n and C n denote a chordless path and a chordless cycle with n vertices, respectively, A subgraph of G induced by a subset

Acknowledgment

Vadim Lozin acknowledges support from the Russian Science Foundation Grant No. 17-11-01336.

A house is the complement of a P 5 . If a graph G contains an induced house, the house-reduction consists in removing from G the vertices that form a triangle in the house. It was shown in [START_REF] Vadim | On the maximum independent set problem in subclasses of subcubic graphs[END_REF] that if G is a subcubic graph, then the housereduction reduces α(G) by exactly 1.

Π-reduction Now we introduce the Π-reduction illustrated in Figure 3. In a graph G, an induced Π is the graph represented on the left of Figure 3. We observe that vertex f can be missing, in which case vertices a and c have no other neighbours in G. However, if f exists, that is, if one of a, c has a neighbour outside of {1, 3, e}, then f is a common neighbour of a, c. Similarly, vertex h can be missing, in which case vertices b and d have no other neighbours in G.


Luciano Da Fontoura Costa
email: luciano@ifsc.usp.br

Visualizing the 'Content of Differential Equations (CDT-16)

Many scientific models, from Newton's second law to Hodgkin and Huxley's axon model, involve differential equations. This type of model focuses on the tendency of the involved variables to change, expressed as derivatives, therefore representing an infinitesimal formulation around an operation point. Yet, despite their seeming simplicity, differential equations can hold a universe of potentially complex dynamical behaviors. It would be a major scientific advancement to be able to see what is inside differential equations. In case we restrict our attention to low orders and/or consider few equations, direction fields provide a valuable resource for visualizing all possible dynamic properties of a given ordinary differential equation or system of ordinary differential equations. This didactic text provides an introduction to this interesting approach. We start by presenting some basic principles of differential equations and then illustrate the application of direction fields to study several interesting models, including population dynamics as well as systems of ordinary differential equations corresponding to the simple and dissipative pendulum, and Lotka-Volterra's population model.

'The next great era of awakening of human intellect may well produce a method of understanding the qualitative content of equations.'

Introduction

Differential equations underlie many mathematical models in science (e.g. [START_REF] Heinz | Mathematical Modeling[END_REF][START_REF] Da | Modeling: The human approach to science[END_REF][START_REF] Kreyszig | Advanced Engineering Mathematics[END_REF][START_REF] Saff | Fundamentals of Differential Equations[END_REF]), from Newton's second law to Hodgkin and Huxley's neuronal model, not forgetting Schrdinger's equation. This type of approach, as compared to -for instance -integral ore delay equations, has been frequently adopted because it represents a local formulation, in the sense of describing the instant tendency of certain variables to change. This tends to simplify both experiments and analytic modeling. The development of a differential model typically requires only an infinitesimal (in practice a small) neighborhood around an operation point to be taken into account.

Despite the seeming simplicity of many differential equations, they often imply surprisingly complex dynamical behaviour, such as Hodgkin and Huxley's neuronal model and Schrdinger's equation. This often happens with non-linear and/or coupled differential equations, which can even lead to chaos and fractal attractors. Thus, a good deal of the importance and effectiveness of developing scientific models based on differential equations stems from these two interesting properties: compactness of representation and ability to describe substantially complex dynamics.

Figure 1: The direction field of the system of differential equations ẋ = -x and ẏ = -y (blue arrows) and some possible solutions or trajectories (orange) starting from the respective points marked by asterisks.

However, it is very difficult to infer all the dynamic, qualitative properties of a differential equation just by looking at them. Often, one has to resource to intricate mathematical methods in order to better understand the potentially implied dynamics. Even so, complete understanding can present a real challenge in some cases such as in the Hodgkin-Huxley coupled equations. This fact is probably the main motivation for Feynman's observation quoted at the beginning of this text.

Fortunately, there is a direct, simple and graphically pleasing approach that can be employed in order to visualize all the possible dynamical properties of some differential equations or systems of differential equations. This method, which is often called direction filed (or slope field ), involves obtaining graphical representations of the derivative slopes in the domain of the considered differential equation (e.g. [START_REF] Devaney | Differential Equations[END_REF][START_REF] Dobrushkin | Applied Differential Equations: The Primary Course[END_REF][START_REF] Saff | Fundamentals of Differential Equations[END_REF]).

What is particularly nice about this approach is that it can contemplate most (those comprised in the visualized domain) possible solutions, as determined by respective initial conditions. Then, just by looking at these diagrams, it is possible to infer the possible dynamical behavior of the equations with respect to diverse starting points, allowing the identification of equilibrium points (and their type), as well as increases, decays, and oscillations. Figure 1 illustrates a simple directional field corresponding to the ordinary differential equation Unfortunately, since it relies on human visualizations (which is limited to few dimensions) the direction field approach applicability is limited to ordinary differential equations of low order, typically 1 or 2. Even so, this methodology can greatly help us to understand specific differential equations, constituting and interesting additional tool to researchers.

This work initiates by presenting some basic concepts in ordinary differential equations and follows by describing the direction field approach in terms of several examples derived from population dynamics and physics. Observe that we henceforth assume ordinary differential equations of low order.

Basic Concepts of Differential Equations and Differential Modelling

Differential equations are often related to functions of time, space, as well as other variables that, frequently, corresponds to some real-world quantity. For instance, in case of the population of a given place, we could be interested in considering its values along time, giving rise to the function x(t). Now, the tendency (or speed ) of this variable to change can be conveniently expressed as

dx dt = ẋ = x = g(x, t) (1)
where g(x, t) is a function of x and/or the time t. In the particular case g(x, t) = g(x) (i.e. independent of the time t), the differential equation is said to be autonomous. The time t is said to be a free or independent variable, and x can be said to be a dependent variable. In case the differential equation involves only one free variable, it is said to be an ordinary differential equation, or ODE for short. The order of an ODE is defined by the highest involved derivative.

In differential modeling, focus is placed on deriving a possible candidate for g(x, t), e.g. by performing experiments and/or applying other known concepts and equations. For instance, in case of the above mentioned population model, one can postulate that the tendency of x(t) to grow is proportional to its current value x, which immediately leads to

dx dt = ax (2)
for some a ∈ , a > 0. Observe that this is an example of autonomous ODE.

In some cases, such as in the above example, it is possible to solve analytically the differential equation. In this case, we have:

dx dt = ax =⇒ dx = axdt =⇒ 1 x dx = adt =⇒ =⇒ ln(x) = at + b =⇒ x = e at+b =⇒ x = ce at (3)
with b being a real constant, and c = e b . Observe that, since no specific initial conditions (e.g. the value of x at some specific time t 0 ), we cannot determine the constant c.

Once the solution is obtained, it is interesting to interprete its implications. In this case, we have that the population would grow in an exceedingly fast and unbounded way, i.e. exponentially. It is interesting to observe that the hypothesis summarized in Equation 2 was indeed considered at a time, being related to the Malthusian theory of population growth. According to this theory, people would grow much faster than food, implying in big trouble for humanity.

It is often interesting to consider special cases in which the involved variable will remain constant, implying ẋ = 0. If we plug this into Equation 2, we immediately obtain x = 0. This value is said to be an equilibrium point of the differential equation.

An improved, bounded model, was developed subsequently, namely the logistic population model, developed by P. Verhulst.

dx dt = ax 1 - x N (4)
Interestingly, this equation has two equilibrium points corresponding to x = 0 and x = N . As we will discuss further in this text, this model provides better adherence to city population growth than the Malthus's approach.

Population problems involving two distinct, interacting populations or species have also been studied in the literature, including the interesting Lotka-Volterra system of ODEs:

ẋ = αx -βxy ẏ = -γy + δxy (5)
Here, x(t) and y(t) express the two considered populations along time ('prey' and 'predator', respectively), and α, β, δ, and γ are real constants. Observe that the variable y influences x negatively, while an increase of x tends have a positive effect on y. Such interrelationships appear as couplings in the system equations, hence we say that the system is coupled in that case. Because of the products xy, this system of ODE is non-linear.

This system will have its equilibrium at the point x = γ/δ and y = α/β.

Interestingly, higher order ODEs can be rewritten as systems of ODEs of order 1. In particular, if the original ODE has order P , we will need a system with P ordinary differential equations of order 1. For instance, consider the following second order differential equation, related to the simple, harmonic pendulum (e.g. [START_REF] Da | Circuits, oscillations, and the kuramoto model as visualized by phasors. Researchgate[END_REF][START_REF] Da | The Laplace transform in a nutshell[END_REF]):

ẍ = -ax (6)
we make u1 = ẋ, and u2 = ẍ, from which follows that ẋ = u 2 which, combined with the original Equation 6 yields u1 = u 2 u2 = -au 1 [START_REF] Da | Circuits, oscillations, and the kuramoto model as visualized by phasors. Researchgate[END_REF] Observe that, in principle, an ODE of order M leads to a system of M first order ODEs.

Direction Fields of ODEs

An important property of an ODE such as that in Equation 1 is that ẋ = g(x, t) can be immediately understood as providing the derivative of the solution x(t) at time t. More specifically, the value g(x, t) gives the slope of the derivative at each point (t, x), as illustrated in Figure 2. Therefore, g(x, t) allows us to associate a vector field ψ(x, t) = (g(x, t)∆t, ∆t) to each point (x, t), for some ∆t ∈ . Observe that direction fields can be obtained for specific, spatially delimited regions of the respective domain of interest. Also, for simplicity's sake, we will normalize all direction fields in this work so that the slopes are represented by vectors of unit magnitude (normalized).

Let's start by obtaining the direction field for the differential equation in Equation 2 for a = 1, which is shown in Figure 3. Since this ODE is autonomous, the orientations along each of the columns respective to t values will be identical one another. Observe also that we will not incorporate arrow heads in the slopes of direction fields representing sin-gle ODEs, as the direction of progression of the solutions (trajectories) are explicitly defined by the axis associated to the free variable t.

The ability to represent the possible qualitative dynamical behavior of this equation is evident from Figure 3. Here, we have that trajectories starting at x > 0 will grow intensely (expoenentially) in an unbound way. Trajectories starting at x < 0 will decrease steadily. Trajectories starting at x = 0 will remain null, as this corresponds to an equilibrium point. Because any small deviation from x = 0 will imply in steady increase or decrease, this equilibrium point is unstable. So, we have that the direction field provides an immediate, complete description of the dynamics of this equation within the considered domain of interest.

Figure 4 illustrates the direction field obtained from Equation 4 considering a = N = 1. A substantially more intricate organization of slopes is observed, as compared to that obtained in Figure 3. The two equilibrium points can be easily identified, corresponding to the null-slope lines obtained for x = 0 and x = 1. Because trajectories along the equilibrium x = 1 will tend to return to this value after small perturbations, we can say this equilibrium point is stable. The equilibrium point for x = 0 can immediately be verified to be unstable.

The stable equilibrium for x = 1 corresponds to the (normalized) population the modeled city will achieve after a substantial period of time, with perturbations oscillations such as those caused by diseases or emigration/immigration tending to be leveled along time. Interestingly, an impressive adherence with real-world cities have been observed in several cases.

Direction Field of ODE Systems

The direction field approach can be immediately adapted to visualize the dynamics implied by autonomous systems of two first-order ODEs. The basic idea is not to include the free variable t in the representation (or, one can imagine the t axis projecting from the plan of this text). In this way, it is possible to assign the two axes typically involved in the direction field methodology to each of the variables corresponding to the two ODE equations, respectively. One shortcoming of this approach is that it is not possible to deal with non-autonomous equations.

Observe that now we resource to arrow heads in order to indicate the direction of the derivatives, as the line segments no longer correspond to the slope of the solution, but to the tendency of variation or speed (a vector) of solutions at each point of the considered domain.

Figure 5 depicts the direction field obtained for Lotka-Volterra Equation 5, assuming α = β = δ = γ = 1. The relatively simple possible dynamics implied by this ODE system is evident from this figure: periodical trajectories are defined around the equilibrium point. Notice that it would probably be less immediate to conclude this behaviour by analysing the original ODE system. Regarding the interpretation of this result from the population point of view, we have that the two species, x and y will oscillate in such a way that when one of them is large, the other tends to be small, and so on. This would mean that an increase of predators tend to reduce the prey population, subsequently implying in a reduction of predators and increase of preys, and so on. The populations will remain constant when starting at the equilibrium point (x = 1, y = 1). It should be observe that the classification of equilibrium points in differential equations involving several dependent variables is more elaborated than that for single dependent variable, not being covered in the present text.

Let's now proceed to the ODE system in Equation 7, which is related to the motion of a simple pendulum without dissipation. The respective direction field is depicted in Figure 6. We assumed a = 1, -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1. As we can immediately infer from the obtained direction field, an even simpler dynamical behavior is obtained in this case, as compared to the previous Lotka-Volterra results. We again identify periodical solutions, which are now perfectly circular, implying in sine and cosine solutions for x(t) and y(t). A single equilibrium point is obtained at (0, 0).

As an additional example of direction field of ODE systems, let's consider the case, which is related to a simple damped pendulum (the damping being proportional, and inverse, to the angular speed):

u1 = u 2 u2 = -au 1 -bu 2 (8)
The respective direction field is shown in Figure 7, for a = 1 and b = 0.4. As a consequence of dissipation, the solutions undergo a reduction in their magnitude, defining spiraling trajectories in the direction field. Interest-ingly, perfect equilibrium is only achieved after an infinite period of time, as a consequence of the asymptotical behaviour of the trajectories toward the equilibrium point (0, 0).

Concluding Remarks

Differential equations are of paramount importance in scientific modeling, allowing an infinitesimal approach that tends to simplify both experiments and model development. Yet, despite their seeming simplicity, differential equations can give rise to surprisingly complex dynamical behaviors that are difficult to infer from the observation of the respective equation, or even by applying more systematic analytical methods.

In this text, we discussed how the direction (or slope) field method can be applied to visualize the 'content' of several ordinary differential equations, especially those with order smaller or equal to 2, being autonomous when of second order. Though restricted to some types of equations, this methodology can provide a convenient and direct way to identifying the implied dynamical behaviors. We have provided some examples of the direction field approach regarding some interesting differential models related to population dynamics and mechanics (simple pendulum with and without damping).

Costa's Didactic Texts -CDTs CDTs intend to be a halfway point between a formal scientific article and a dissemination text in the sense that they: (i) explain and illustrate concepts in a more informal, graphical and accessible way than the typical scientific article; and (ii) provide more in-depth mathematical developments than a more traditional dissemination work.

It is hoped that CDTs can also integrate new insights and analogies concerning the reported concepts and methods. We hope these characteristics will contribute to making CDTs interesting both to beginners as well as to more senior researchers.

Though CDTs are intended primarily for those who have some experience in the covered concepts, they can also be useful as summary of main topics and concepts to be learnt by other readers interested in the respective CDT theme. Observe that CDTs come with absolutely no warranty.

Each CDT focuses on a few interrelated concepts. Though attempting to be relatively self-contained, CDTs also aim at being relatively short. Links to related material are provided in order to complement the covered subjects.

The complete set of CDTs can be found at: https://www.researchgate.net/project/ Costas-Didactic-Texts-CDTs.

Figure 2 :

 2 Figure 2: The function g(x, t) provides the slope at (t, x) of any possible solution implied by the ordinary differential equation ẋ = g(x, t).

Figure 3 :

 3 Figure 3: Direction field obtained for the differential equation ẋ = x (Eq. 2, with a = 1), considering the domain -1 ≤ t ≤ 1 and -1 ≤ x ≤ 1. The slopes of possible solutions are represented by blue line segments, while some possible solutions (trajectories), starting at specific points (t = -1, x(-1)) are represented in orange. The negative portion of x has been included for generality. Observe that the trajectories never go across any arrow, as the latter are tangent to the former.

Figure 4 :

 4 Figure 4: Direction field obtained for the differential equation ẋ = x -x 2 (Eq. 2, with a = N = 1), considering the domain -1 ≤ t ≤ 1 and -1 ≤ x ≤ 2. Some possible solutions, starting at points (t = -1, x(-1)), are represented by respective trajectories in orange. The negative portion of x has been included for generality.

Figure 5 :

 5 Figure 5: The direction field obtained for the Lotka-Volterra equation assuming α = β = δ = γ = 1. Some possible solutions, starting at respective green asterisks, are represented in orange.

Figure 6 :

 6 Figure 6: Direction field obtained for Equation 7 assuming a = 1, -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1. Some possible solutions (trajectories), starting from respective initial conditions indicated by green asterisks, are shown in orange.

Figure 7 :

 7 Figure 7: Direction field obtained for Equation 8 assuming a = 1, b = 0.4, -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1. The initial portions of some possible solutions (spiraling trajectories), starting from respective initial conditions indicated by green asterisks, are shown in orange.

Acknowledgments.

Luciano da F. Costa thanks CNPq (grant no. 307085/2018-0) for sponsorship. This work has benefited from FAPESP grant 15/22308-2.