Piotr Koniusz

Anoop Cherian

Dictionary Learning and Sparse Coding for Third-order Super-symmetric Tensors

. However, the size of these tensors are exponential in the data dimensionality, which is a significant concern. In this paper, we study third-order super-symmetric tensor descriptors in the context of dictionary learning and sparse coding. Our goal is to approximate these tensors as sparse conic combinations of atoms from a learned dictionary, where each atom is a symmetric positive semi-definite matrix. Apart from the significant benefits to tensor compression that this framework provides, our experiments demonstrate that the sparse coefficients produced by the scheme lead to better aggregation of high-dimensional data, and showcases superior performance on two common computer vision tasks compared to the state-of-the-art.

Introduction

Recent times have seen an increasing trend in several machine learning and computer vision applications to use rich data representations that capture the inherent structure or statistics of data. A few notable such representations are histograms, strings, covariances, trees, and graphs. The goal of this paper is to study a new class of structured data descriptors -third-order super-symmetric tensorsin the context of sparse coding and dictionary learning.

Tensors are often used to capture higher-order moments of data distributions such as the covariance, skewness or kurtosis and have been used as data descriptors in several computer vision applications. In region covariances [START_REF] Tuzel | Region covariance: A fast descriptor for detection and classification[END_REF], a covariance matrix -computed over multi-modal features from image regions -is used as descriptors for the regions and is seen to demonstrate superior performance in object tracking, retrieval, and video understanding. Given bag-of-words histograms of data vectors from an image, a second-order co-occurrence pooling of these histograms captures the occurrences of two features together in an image and is recently shown to provide superior performance to problems such as semantic segmentation of images, compared to their first-order counterparts [START_REF] Carreira | Semantic Segmentation with Second-Order Pooling[END_REF]. A natural extension of the idea is to use higher-order pooling operators, an extensive experimental analysis of which is provided in [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF]. Their paper shows that pooling using third-order supersymmetric tensors can significantly improve upon the second-order descriptors, e.g., by more than 5% MAP on the challenging PASCAL VOC07 dataset.

However, given that the size of the tensors increases exponentially against the dimensionality of their first-order counterpart, efficient representations are extremely important for applications that use these higher-order descriptors. To this end, the goal of this paper is to study these descriptors in the classical dictionary learning and sparse coding setting [START_REF] Olshausen | Sparse coding with an overcomplete basis set: A strategy employed by v1?[END_REF]. Using the properties of super-symmetric tensors, we formulate a novel optimization objective (Sections 4, 5) in which each third-order data tensor is approximated by a sparse non-negative linear combination of positive semi-definite ma-1 arXiv:1509.02970v1 [cs.CV] 9 Sep 2015 trices. Although our objective is non-convex -typical to several dictionary learning algorithmswe show that our objective is convex in each variable, thus allowing a block-coordinate descent scheme for the optimization. Experiments (presented in Section 6) on the PASCAL VOC07 dataset show that the compressed coefficient vectors produced by our sparse coding scheme preserves the discriminative properties of the original tensors and leads to performances competitive to the stateof-the-art, while providing superior tensor compression and aggregation. Inspired by the merits of third-order pooling techniques proposed in [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF], we further introduce a novel tensor descriptor for texture recognition via the linearization of explicitly defined RBF kernels, and show that sparse coding of these novel tensors using our proposed framework provides better performance than the state of the art descriptors used for texture recognition.

Related Work

Dictionary learning and sparse coding [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF][START_REF] Olshausen | Sparse coding with an overcomplete basis set: A strategy employed by v1?[END_REF] methods have significantly contributed to improving the performance of numerous applications in computer vision and image processing. While these algorithms assume a Euclidean vectorial representation of the data, there have been extensions to other data descriptors such as tensors, especially symmetric positive definite matrices [START_REF] Cherian | Riemannian sparse coding for positive definite matrices[END_REF][START_REF] Harandi | Sparse coding and dictionary learning for symmetric positive definite matrices: A kernel approach[END_REF][START_REF] Sivalingam | Tensor sparse coding for region covariances[END_REF]. These extensions typically use non-Euclidean geometries defined by a similarity metric that they use for comparing the second-order tensors. Popular choices for comparisons of positive definite matrices are the log-determinant divergence [START_REF] Sivalingam | Tensor sparse coding for region covariances[END_REF], the log-euclidean metric [START_REF] Arsigny | Log-euclidean metrics for fast and simple calculus on diffusion tensors[END_REF], and the affine invariant Riemannian metric [START_REF] Pennec | A riemannian framework for tensor computing[END_REF]. Alas, the third-order tensors considered in this paper are neither positive definite nor there are any standard similarity metrics known apart from the Euclidean distance. Thus, extending these prior methods to our setting is infeasible, demanding novel formulations.

Third-order tensors have been used for various tasks. Spatio-temporal third-order tensor on video data for activity analysis and gesture recognition is proposed in [START_REF] Kim | Tensor canonical correlation analysis for action classification[END_REF] . Non-negative factorization is applied to third-order tensors in [START_REF] Shashua | Non-negative tensor factorization with applications to statistics and computer vision[END_REF] for image denoising. Multi-linear algebraic methods for tensor subspace learning are surveyed in [START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF]. Tensor textures are used in the context of texture rendering in computer vision applications in [START_REF] Vasilescu | Tensortextures: multilinear image-based rendering[END_REF]. Similar to eigenfaces for face recognition, multi-linear algebra based techniques for face recognition use third-order tensors in [START_REF] Vasilescu | Multilinear analysis of image ensembles: Tensorfaces[END_REF]. However, while these applications generally work with a single tensor, the objective of this paper is to learn the underlying structure of a large collection of such tensors generated from visual data using the framework of dictionary learning and sparse coding, which to the best of our knowledge is a novel proposition.

In addition to the dictionary learning framework, we also introduce an image descriptor for textures. While we are not aware of any previous works that propose third-order tensors as image region descriptors, the most similar methods to our approach are i) third-order probability matrices for image splicing detection [START_REF] Zhao | A comprehensive study on third order statistical features for image splicing detection[END_REF] and ii) third-order global image descriptors which aggregate SIFT into the autocorrelation tensor [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF]. In contrast, our descriptor, is assembled from elementary signals such as luminance and its first-and second-order derivatives, analogous to covariance descriptors [START_REF] Tuzel | Region covariance: A fast descriptor for detection and classification[END_REF], but demonstrating superior accuracy. The formulation chosen by us for texture recognition also differs from prior works such as kernel descriptors [START_REF] Bo | Object recognition with hierarchical kernel descriptors[END_REF] and convolutional kernel networks [START_REF] Mairal | Convolutional kernel networks[END_REF].

Notations

Before we proceed, we will briefly review our notations next. We use bold-face upper-case letters for third-order tensors, bold-face lower-case letters for vectors, and normal fonts for scalars. Each second-order tensor along the third mode of a third-order tensor is called a slice. Using Matlab style notation, the s-th slice of X is given by X :,:,s . The operation ↑ ⊗ stands for an outer product of a second-order tensor with a vector. For example, Y = Y ↑ ⊗ y produces a third-order tensor Y ∈ R d1×d2×d3 from a matrix Y ∈ R d1×d2 and a vector y ∈ R d3 , where the s-th slice of Y is given by Yy s , y s being the s-th dimension of y. Let I N stand for an index set of the first N integers. We use S d + to denote the space of d × d positive semi-definite matrices and S d to denote the space of super-symmetric tensors of dimensions d × d × d.

Going by the standard terminology in higher-order tensor factorization literature [START_REF] Comon | Tensors: a brief introduction[END_REF], we define a core tensor as the analogous of the singular value matrix in the second-order case. However, unless some specific decompositions are enforced, a core tensor need not be diagonal as in the second-order case.

To this end, we assume the CP decomposition [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF] in this paper, which generates a diagonal core tensor.

Background

In this section, we will review super-symmetric tensors and their properties, followed by a brief exposition of the method described in [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] for generating tensor descriptors for an image. The latter will come useful when introducing our new texture descriptors.

Third-order Super-symmetric Tensors

We define a super-symmetric tensor descriptor as follows: Definition 1. Suppose x n ∈ R d + , ∀n ∈ I N represents data vectors from an image, then a thirdorder super-symmetric tensor (TOSST) descriptor X ∈ R d×d×d of these data vectors is given by:

X = 1 N N n=1 (x n x T n ) ↑ ⊗ x n . (1)
In object recognition setting, the data vectors are typically SIFT descriptors extracted from the image, while the tensor descriptor is obtained as the third-order autocorrelation tensor via applying [START_REF] Arsigny | Log-euclidean metrics for fast and simple calculus on diffusion tensors[END_REF].

The following properties of the TOSST descriptor are useful in the sequel. Proposition 1. For a TOSST descriptor X ∈ R d×d×d , we have:

1. Super-Symmetry: X i,j,k = X Π(i,j,k) for indexes i, j, k and their permutation given by Π.

2. Every slice is positive semi-definite, that is, X :,:,s ∈ S d + , for s ∈ I d . 3. Indefiniteness, i.e., it can have positive, negative, or zero eigenvalues in its core-tensor (assuming a CP decomposition [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF]). Proof. The first two properties can be proved directly from [START_REF] Arsigny | Log-euclidean metrics for fast and simple calculus on diffusion tensors[END_REF]. To prove the last property, note that for a TOSST tensor X and some z ∈ R d , z = 0, we have

((X ⊗ 1 z) ⊗ 2 z) ⊗ 3 z = d s=1 z s (z T X s z)
where X s is the s-th slice of X . While z T X s z ≥ 0, the tensor product could be negative for z < 0. In the above, ⊗ i denotes tensor product in the i-th mode [START_REF] Kolda | Tensor decompositions and applications[END_REF].

Due to the indefiniteness of the tensors, we cannot use some of the well-known distances on the manifold of SPD matrices [START_REF] Arsigny | Log-euclidean metrics for fast and simple calculus on diffusion tensors[END_REF][START_REF] Pennec | A riemannian framework for tensor computing[END_REF]. Thus, we restrict to using the Euclidean distance for the derivations and experiments in this paper.

Among several properties of tensors, one that is important and is typically preserved by tensor decompositions is the tensor rank defined as: Definition 2 (Tensor Rank). Given a tensor X ∈ R d×d×d , its tensor rank TRank(X ) is defined as the minimum p such that X :,:,s ∈ Span (M 1 , M 2 , ..., M p ) for all s ∈ I d , where M i ∈ S d + are rank-one.

Problem Formulation

Suppose we are given data tensors X n , n ∈ I N , each X n ∈ S d . We want to learn a tensor dictionary B with atoms B 1 , B 2 , ..., B K , where each B k ∈ S d consists of d-slices. Let the sth slice of the k-th atom is given by B s k where s

∈ I d , k ∈ I K . Each slice B s k ∈ S d + .
Then, the problem of dictionary learning and sparse coding can be formulated as follows: for sparse coefficient vectors

α n ∈ R K , n ∈ I N , arg min B α 1 ,...,α N N n=1 X n - K k=1 B k α n k 2 F + λ α n 1 . (2)
Note that in the above formulation, third-order dictionary atoms B k are multiplied by single scalars α n k . For K atoms, each of size d 3 , there are Kd 3 parameters to be learned in the dictionary learning process. An obvious consequence of this reconstruction process is that we require N K to prevent overfitting. To circumvent this bottleneck and work in regime N S K, the reconstruction process is amended such that every dictionary atom is represented by an outer product of a second-order symmetric positive semi-definite matrix B k and a vector b k . Such a decomposition/approximation will reduce the number of parameters from Kd 3 to K(d 2 + d). Using this strategy, we re-define dictionary B to be represented by atom pairs Using this idea, we can rewrite (2) as follows:

B ≡ {(B k , b k )} K k=1 such that B k = B k ↑ ⊗ b k . Note that
arg min B α 1 ,...,α N N n=1 X n - K k=1 (B k ↑ ⊗ b k ) α n k 2 F + λ α n 1 . (3)
Introducing optimization variables β n k and rewriting the loss function by taking the slices out, we can further rewrite (3) as:

arg min B α 1 ,...,α N N n=1 S s=1 X s n - K k=1 B k β s,n k 2 F + λ α n 1 , subject to β n k = b k α n k , ∀k ∈ I K and n ∈ I N . (4)
We may rewrite the equality constraints in (4) as a proximity constraint in the objective function (using a regularization parameter γ), and constrain the sparse coefficients in α n to be non-negative, as each slice is positive semi-definite. This is a standard technique used in optimization, commonly referred to as variable splitting. We can also normalize the dictionary atoms B k to be positive semi-definite and of unit-trace for better numerical stability. In that case, vector atoms b k can be constrained to be non-negative (or even better, β n k ≥ 0 instead of α n ≥ 0 and b k ≥ 0). Introducing chosen constraints, we can rewrite our tensor dictionary learning and sparse coding formulation:

arg min B α 1 ,...,α N ≥0 N n=1 S s=1 X s n - K k=1 B k β s,n k 2 F + γ β s,n -b s α n 2 2 + λ α n 1 , subject to B k 0, Tr(B k ) ≤ 1, b k 1 ≤ 1, k = 1, ..., K. (5)
In the above equation, operator is an element-wise multiplication between vectors. Coefficients γ and λ control the quality of the proximity and sparsity of α n , respectively. We might replace the loss function using a loss based on Riemannian geometry of positive definite matrices [START_REF] Cherian | Riemannian sparse coding for positive definite matrices[END_REF], in which case the convexity would be lost and thus convergence cannot be guaranteed. The formulation ( 5) is convex in each variable and can be solved efficiently using the block coordinate descend.

Remark 1 (Non-symmetric Tensors). Note that non-symmetric X n ∈ R d1×d2×d3 can be coded if the positive semi-definite constraint on B k is dropped, B k ∈ R d1×d2 and b k ∈ R d3 . Other nonnegative constraints can also be then removed. While this case is a straightforward extension of our formulation, a thorough investigation into it is left as future work.

Optimization

We propose a block-coordinate descent scheme to solve [START_REF] Carreira | Semantic Segmentation with Second-Order Pooling[END_REF], in which each variable in the formulation is solved separately, while keeping the other variables fixed. As each sub-problem is convex, we are guaranteed to converge to a local minimum. Initial values of B k , b k , and α n are chosen randomly from the uniform distribution within a prespecified range. Vectors β s,n are initialized with the Lasso algorithm. Next, we solve four separate convex sub-problems resulting in updates of B k , b k , β s,n , α n . For learning second-order matrices B k , we employ the PQN solver [START_REF] Schmidt | Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm[END_REF] which enables us to implement and apply projections into the SPD cone, handle the trace norm or even the rank of matrices (if this constraint is used). Similarly, the projected gradient is used to keep b k inside the simplex b k 1 ≤ 1. For the remaining sub-problems, we use the L-BFGS-B solver [START_REF] Byrd | A limited memory algorithm for bound constrained optimization[END_REF] which enables us to handle simple box constraints e.g., we split coding for α n into two non-negative sub-problems α n + and α n -by applying box constraints α n + ≥ 0 and α n -≥ 0. Finally, we obtain α n = α n + -α n -after minimization. Moreover, for the coding phase (no dictionary learning), we fix

{(B k , b k )} K k=1 .
The algorithm proceeds as above, but without updates of B k and b k . Algorithm 1 shows the important steps of our algorithm; this includes both the dictionary learning and the sparse coding sub-parts.

Algorithm 1: Third-order Sparse Dictionary Learning and Coding.

Data: N data tensors X ≡ {X 1 , ..., X N }, proximity and sparsity constants γ and λ, stepsize η, K

dictionary atoms B ≡ {(B k , b k )} K k=1 if coding, otherwise LearnDict = true Result: N sparse coeffs. α ≡ {α 1 , ..., α N }, K atoms B ≡ {(B k , b k )} K k=1 if LearnDict = true Initialization: if LearnDict then • Uniformly
• B (t+1) k = Π SP D B (t) k -η ∂f ∂ B k B (t) k
, ∀k ∈ I K , where f is the cost from (5) and t) , α (t) , where B (t) and b (t) are K matrix and vector atoms

projection Π SP D (B) = B * Tr(B * ) , B * = U max(λ * , 0)V T for (U , λ * , V ) = SV D(B) • b (t+1) k = Π + b (t) k -η ∂f ∂ b k b (t) k , ∀k ∈ I K , and Π + (b) = max(b, 0) if Π + is used end • β s,n,(t+1) = Π + β s,n,(t) -η ∂f ∂ β β s,n,(t) k , ∀s ∈ I S , ∀n ∈ I N , use of Π + is optional • α (t+1) n = Π + α (t) n -η ∂f ∂ α α (t) n , ∀n ∈ I N , use of Π + is optional • Objective (t) = f X , B (t) , b (
• Converged = EvaluateStopingCriteria t, Objective (t) , Objective (t-1)
end 5 Theory

In this section, we analyze some of the theoretical properties of our sparse coding formulation. We establish that under an approximation setting, a sparse coding of the data tensor exist in some dictionary for every data point. We also provide bounds on the quality of this approximation and its tensor rank. The following lemma comes useful in the sequel.

Lemma 1 ([30]

). Let Y = m i=1 φ i φ T i , where each φ i ∈ R d and m = Ω(d 2 ). Then, there exist an α ∈ R m + and ∈ (0, 1) such that:

Y m i=1 α i φ i φ T i (1 + )Y, (6)
where α has O(d log(d)/ 2 ) non-zeros.

Theorem 1. Let X = m i=1 (φ i φ T i ) ↑ ⊗ φ i ,
then there exist a second-order dictionary B with md atoms and a sparse coefficient vector β ∈ R md + with O(d 2 log(d)/ 2 ) non-zeros, such that for ∈ (0, 1),

I) X = m i=1 (φ i φ T i ) ↑ ⊗ βi and II) X -X F ≤ d s=1 X s F ,
where X s is the s-th slice of X and βi ∈ R d .

Proof. To prove I: each slice

X s = m i=1 (φ i φ T i )φ s i , where φ s i is the s-th dimension of φ i . Let φ i = φ i φ s i , then X s = m i=1 φ i φ T i .
If the slices are to be treated independently (as in ( 5)), then to each slice we can apply Lemma 1 that results in sparse coefficient vectors βi having O(d log(d)/ 2 ) non-zeros. Extending this result to all the d-slices, we obtain the result. To prove II: substituting X with its sparse approximation and using the upper-bound in [START_REF] Cherian | Riemannian sparse coding for positive definite matrices[END_REF] for each slice, the result follows.

Theorem 2 (Approximation quality via Tensor Rank). Let X be the sparse approximation to X obtained by solving (4) using a dictionary B and if Rank(B) represent the maximum of the rank of any atom, then

TRank( X ) ≤ d s=1 Supp(X s ) Rank(B), (7)
where Supp(X s ) is the support set produced by (4) for slice X s .

Proof. Rewriting X in terms of its sparse tensor approximation, followed by applying Theorem 2 and the definition in (2), the proof directly follows.

Theorem 2 gives a bound on the rank of approximation of a tensor X by X (which is a linear combination of atoms). Knowing rank of X and X helps check how good the approximation is over measuring the simple Euclidean norm between them. This is useful in experiments where we impose rank-r (r=1,2,...) constraints on atoms B k and measures how rank constraints on B k impacts the quality of approximation.

Experiments

In this section, we present experiments demonstrating the usefulness of our framework. As secondorder region covariance descriptors (RCD) are the most similar tensor descriptors to our TOSST descriptor, we decided to evaluate our performance on applications of RCDs, specifically for texture recognition. In the sequel, we propose a novel TOSST texture descriptor. This will follow experiments evaluating this new descriptor to state-of-the-art on two texture benchmarks, namely the Brodatz textures [START_REF] Ojala | A comparative study of texture measures with classification based on featured distributions[END_REF] and the UIUC materials [START_REF] Liao | Non-parametric filtering for geometric detail extraction and material representation[END_REF]. Moreover, experiments illustrating behaviour of our dictionary learning are provided. We also demonstrate the adequacy of our framework to compression of third-order global image descriptors [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] on the challenging PASCAL VOC07 set.

TOSST Texture Descriptors

Many region descriptors for the texture recognition are described in the literature [START_REF] Carreira | Semantic Segmentation with Second-Order Pooling[END_REF][START_REF] Li | Local log-euclidean covariance matrix (l 2 ecm) for image representation and its applications[END_REF][START_REF] Tuzel | Region covariance: A fast descriptor for detection and classification[END_REF]. Their construction generally consists of the following steps: i) For an image I and a region in it R, extract feature statistics from the region: if (x i , y i ) represent pixel coordinates in R, then, a feature vector from R will be:

φ xy (I) = x -x 0 w -1 , y -y 0 h -1 , I xy , ∂I xy ∂x , ∂I xy ∂y , ∂ 2 I xy ∂x 2 , ∂ 2 I xy ∂y 2 T , (8)
where (x 0 , y 0 ) and (w, h) are the coordinate origin, width, and height of R, respectively.

ii) Compute a covariance matrix

Φ(I, R) = 1 |R|-1 (x,y)∈R φ xy (I) -φ φ xy (I) -φ T , where
φ is the mean over φ xy (I) from that region [START_REF] Tuzel | Region covariance: A fast descriptor for detection and classification[END_REF][START_REF] Li | Local log-euclidean covariance matrix (l 2 ecm) for image representation and its applications[END_REF]. Alternatively, one can simply compute an

autocorrelation matrix Φ(I, R) = 1 |R| (x,y)∈R
φ xy (I)φ xy (I) T as described in [START_REF] Carreira | Semantic Segmentation with Second-Order Pooling[END_REF][START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF].

In this work, we make modifications to the steps listed above to work with RBF kernels which are known to improve the classification performance of descriptor representations over linear methods. The concatenated statistics in step (i) can be seen as linear features forming linear kernel K lin :

K lin ((x, y, I a ), (x , y , I b )) = φ xy (I a ) T φ x y (I b ). (9)
We go a step further and define the following sum kernel K rbf composed of several RBF kernels G:

K rbf (x, y, I a ) , x , y , I b = 7 i=1 G i σi (φ i xy (I a ) -φ i x y (I b )), (10)
where φ i xy (I) is the i-th feature in [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF] and

G i σi (u -u ) = exp(-u -u 2 2
/2σ 2 i ), represents socalled relative compatibility kernel that measures the compatibility between the features in each of the image regions.

The next step involves linearization of Gaussian kernels G i

σ for i = 1, ..., τ to obtain feature maps that expresses the kernel K rbf by the dot-product. In what follows, we use a fast approximation method based on probability product kernels [START_REF] Jebara | Probability product kernels[END_REF]. Specifically, we employ the inner product for the d -dimensional isotropic Gaussian distribution:

G σ u -u = 2 πσ 2 d 2 ζ∈R d G σ/ √ 2 (u -ζ) G σ/ √ 2 u -ζ dζ. (11)
Equation ( 11) is then approximated by replacing the integral with the sum over Z pivots ζ 1 , ..., ζ Z :

G σ (u -u ) ≈ √ wφ(u), √ wφ(u ) , φ(u) = G σ/ √ 2 (u -ζ 1 ), ..., G σ/ √ 2 (u -ζ Z ) T . (12)
A weighting constant w relates to the width of the rectangle in the numerical integration and is factored out by the 2 normalization:

G σ (u-u ) = G σ (u-u ) G σ (u-u)G σ (u -u ) ≈ √ wφ(u) √ wφ(u) 2 , √ wφ(u ) √ wφ(u ) 2 = φ(u) φ(u) 2 , φ(u ) φ(u ) 2 . ( 13
)
The task of linearization of each G i σi in [START_REF] Jebara | Probability product kernels[END_REF] becomes trivial as these kernels operate on onedimensional variables (d = 1). Therefore, we sample uniformly domains of each variable and use Z = 5. With this tool at hand, we rewrite kernel K rbf as:

K rbf ((x, y, I a ), (x , y , I b )) ≈ v a xy , v b x y , (14)
where vector v a xy is composed by τ sub-vectors

φ i xy,σ i φ i
xy,σ i 2 and each sub-vector i = 1, ..., τ is a result of linearization by equations [START_REF] Jégou | On the Burstiness of Visual Elements[END_REF][START_REF] Kim | Tensor canonical correlation analysis for action classification[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF]. We use a third-order aggregation of v according to equation ( 1) to generate our TOSST descriptor for textures. For comparisons, we also aggregate φ from equation ( 8) into a third-order linear descriptor. See our supplementary material for the definition of the third-order global image descriptors [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] followed by the derivation of the thirdorder aggregation procedure based on kernel exponentiation.

Datasets

The Brodatz dataset contains 111 different textures each one represented by a single 640×640 image. We follow the standard protocol, i.e., each texture image is subdivided into 49 overlapping blocks of size 160×160. For training, 24 randomly selected blocks are used per class, while the rest is used for testing. We use 10 data splits. The UIUC materials dataset contains 18 subcategories of materials taken in the wild from four general categories e.g., bark, fabric, construction materials, and outer coat of animals. Each subcategory contains 12 images taken at various scales. We apply a leaveone-out evaluation protocol [START_REF] Liao | Non-parametric filtering for geometric detail extraction and material representation[END_REF]. The PASCAL VOC07 set consists of 5011 images for training and 4952 for testing, 20 classes of objects of varied nature e.g., human, cat, chair, train, bottle.

Experimental Setup TOSST descriptors.

In what follows, we evaluate the following variants of the TOSST descriptor on the Brodatz dataset: linear descriptor with first-and -second order derivatives as in (8, 9) (i) but without luminance, and ii) with luminance. RBF descriptor as in (8, 10) (iii) without luminance, and iv) with luminance. Moreover, v) is a variant based on (iv) that uses the opponent color cues for evaluations on the UIUC materials set [START_REF] Liao | Non-parametric filtering for geometric detail extraction and material representation[END_REF]. Removing luminance for (i) and (iii) helps emphasize the benefit of RBF over linear formulation. First though, we investigate our dictionary learning. Dictionary learning. We evaluate several variants of our dictionary learning approach on the Brodatz dataset. We use the RBF descriptor without the luminance cue (iii) to prevent saturation in performance. We apply patch size 40 with stride 20 to further lower computational complexity, sacrificing performance slightly. This results in 49 TOSST descriptors per block. We do not apply any whitening, thus preserving the SPD structure of the TOSST slices. Figures 1(a) and 1(b) plot the accuracy and the dictionary learning objective against an increasing size K of the dictionary. We analyze three different regularization schemes on the second-order dictionary atoms in [START_REF] Carreira | Semantic Segmentation with Second-Order Pooling[END_REF], namely (1) with only SPD constraints, (2) with SPD and low-rank constraints, and (3) without SPD or low-rank constraints. When we enforce Rank(B k ) ≤ R < d for k = 1, ..., K to obtain low-rank atoms B k by scheme (2), the convexity w.r.t. B k is lost because the optimization domain in this case is the non-convex boundary of the PD cone. However, the formulation (5) for schemes (1) and ( 3) is convex w.r.t. B k . The plots highlight that for lower dictionary sizes, variants (1) and ( 2) perform worse than (3) which exhibits the best performance due to a very low objective. However, the effects of overfitting start emerging for larger K. The SPD constraint appears to offer the best trade-off resulting in a good performance for both small and large K. In Figure 1(c), we further evaluate the performance for a Rank-R constraint given K = 20 atoms. The plot highlights that imposing the low-rank constraint on atoms may benefit classification. Note that for 15 ≤ R ≤ 30, the classification accuracy fluctuates up to 2%, which is beyond the error standard deviation (≤ 0.4%) despite any significant fluctuation to the objective in this range. This suggests that imposing some structural constraints on dictionary atoms is an important step in dictionary learning. Lastly, Figure 1

Comparison to State-of-the-Art on Textures

In this experiment, descriptor variants were whitened per block as in [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF]. In each block, we extract 225 TOSST descriptors with patch size 20 and stride 10, apply our dictionary learning given K = 2000 followed by the sparse coding and perform pooling as in [START_REF] Koniusz | Comparison of Mid-Level Feature Coding Approaches And Pooling Strategies in Visual Concept Detection[END_REF] prior to classification with SVM. Table 1 demonstrates our results which highlight that the RBF variant outperforms the linear descriptor. This is even more notable when the luminance cue is deliberately removed from descriptors to degrade their expressiveness. Table 1 also demonstrates state-of-the-art results. With 99.9 ± 0.08% accuracy, our method is the strongest performer. Additionally, Table 1 provides our results on the UIUC materials obtained with descriptor variant (v) (described above) and K = 4000 dictionary atoms. We used TOSST descriptors with patch size 40, stride 20 and obtained 58.0±4.3% which outperforms other methods.

Signature Compression on PASCAL VOC07

In this section, we evaluate our method on the PASCAL VOC07 dataset, which is larger and more challenging than the textures. To this end, we use the setup in [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] to generate third-order global image descriptors (also detailed in our supp. material) with the goal of compressing them using our sparse coding framework. In detail, we use SIFT extracted from gray-scale images with radii 12, 16, 24, 32 and stride 4, 6, 8, 10, reduce SIFT size to 90D, append SPM codes of size 11D [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] and obtain the global image signatures which yield baseline score of 61.3% MAP as indicated in Table 2 (last column). Next, we learn dictionaries using our setup as in equation ( 5) and apply our sparse coding to reduce signature dimensionality from 176851 (upper simplex of third-order tensor) to sizes from 2K to 25K. The goal is to regain the baseline score. Table 2 shows that a learned dictionary (DL) of size 25K yields 61.2% MAP at 7× compression rate, which demonstrates how to limit redundancy in third-order tensors. For comparison, a random dictionary is about 4.3% worse. In Figure 2 plots the impact of the number of atoms (K) against signature compression on this dataset. Complexity. It takes about 3.2s to code a third-order tensor of size d = 30 using a dictionary with 2000 atoms. Note that our current implementation is in MATLAB and the performance is measured on a 4-core CPU. Our dictionary learning formulation converges in approximately 50 iterations.

Conclusions

We presented a novel formulation and an efficient algorithm for sparse coding third-order tensors using a learned dictionary consisting of second-order positive semi-definite atoms. Our experiments demonstrate that our scheme leads to significant compression of the input descriptors, while not sacrificing the classification performance of the respective application. Further, we proposed a novel tensor descriptor for texture recognition, which when sparse-coded by our approach, achieves stateof-the-art performance on two standard benchmark datasets for this task. performed on the eigenvalues from so-called core tensor. The following steps from [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] are used:

V i = ⊗ r v i , ∀i ∈ I (15) V = Avg i∈I (V i ) (16)
(E; A) = HOSVD( V) (17) Ê = Sgn(E) |E| γe (18) V = Ê × 1 A...× r A (19)
X = Sgn( V) | V| γc (20)
Equations (15, 16) assemble a higher-order autocorrelation tensor V per image I. First, the outer product ⊗ r of order r [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF][START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] is applied to the local image descriptors v i ∈ R d from I. This results in |I| autocorrelation matrices or third-order tensors V i ∈ R d r of rank 1 for r = 2 and r = 3, respectively. Rank-1 tensors are then averaged by Avg resulting in tensor V ∈ R d r that represents the contents of image I and could be used as a training sample. However, the practical image representations have to deal with so-called burstiness which is "the property that a given visual element appears more times in an image than a statistically independent model would predict" [START_REF] Jégou | On the Burstiness of Visual Elements[END_REF]. Corrective functions such as Power Normalization are known to suppress the burstiness [START_REF] Boughorbel | Generalized Histogram Intersection Kernel for Image Recognition[END_REF][START_REF] Perronnin | Improving the Fisher Kernel for Large-Scale Image Classification[END_REF][START_REF] Jégou | On the Burstiness of Visual Elements[END_REF]. Therefore, equations [START_REF] Li | Local log-euclidean covariance matrix (l 2 ecm) for image representation and its applications[END_REF][START_REF] Liao | Non-parametric filtering for geometric detail extraction and material representation[END_REF][START_REF] Lowe | Object Recognition from Local Scale-Invariant Features[END_REF] and [START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF] apply two-stage pooling with eigenvalue-and coefficientwise Power Normalization, respectively. In Equation [START_REF] Li | Local log-euclidean covariance matrix (l 2 ecm) for image representation and its applications[END_REF], operator HOSVD : R d r → R d r ; R d×d decomposes tensor V into a core tensor E of eigenvalues and an orthonormal factor matrix A, which can be interpreted as the principal components in r modes. Element-wise Power Normalization is then applied by equation [START_REF] Liao | Non-parametric filtering for geometric detail extraction and material representation[END_REF] to eigenvalues E to even out their contributions. Tensor V ∈ R d r is then assembled in equation ( 19) by the r-mode product × r detailed in [START_REF] Kolda | Tensor decompositions and applications[END_REF]. Lastly, coefficient-wise Power Normalization acting on V produces tensor X ∈ R d r in equation [START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF]. In our experiments, we use r = 3 and: i) X = V when Power Normalization is disabled, e.g., γ e = γ c = 1 or ii) apply the above HOSVD approach if 0 < γ e < 1 ∧ 0 < γ c ≤ 1. Therefore, the final descriptor X in equation [START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF] represents an image by a super-symmetric third-order tensor which is guaranteed to contain SPD matrix slices if no Power Normalization is used.

B Derivation of the Third-order Aggregation.

Simple operations such as rising K rbf to the power of r and applying outer product of order r to v xy form a higher-order tensor of rank-1 denoted as V xy : K r rbf ((x, y, I a ), (x , y , I b )) ≈ V a xy , V b x y , where V a xy = ⊗ r v a xy .

The higher-order rank-1 tensors V xy are aggregated over image regions R a and R b , respectively:

where (x , y ) ∈ R b : x = xx a 0 + x b 0 ∧ y = yy a 0 + y b 0 .

The aggregation step in equation ( 22) provides analogy to both equation ( 16) and step (ii) which outlines the second-order aggregation step. Equation [START_REF] Olshausen | Sparse coding with an overcomplete basis set: A strategy employed by v1?[END_REF] highlights that the sum kernel is computed over locations (x, y) ∈ R a and corresponding to them locations (x , y ) ∈ R b . For instance, we subtract region origin a a 0 and replace with origin a b 0 to obtain x from R b that corresponds to x from R a . The higher-order autocorrelation tensors V are formed and can be then whitened by applying equations [START_REF] Li | Local log-euclidean covariance matrix (l 2 ecm) for image representation and its applications[END_REF][START_REF] Liao | Non-parametric filtering for geometric detail extraction and material representation[END_REF][START_REF] Lowe | Object Recognition from Local Scale-Invariant Features[END_REF][START_REF] Lu | A survey of multilinear subspace learning for tensor data[END_REF]. In our experiments, we assume the choice of r = 3. Thus, the thirdorder dictionary learning and sparse coding is applied to form so-called mid-level features (one per region). Given an image and a set of overlapping regions, we apply pooling [START_REF] Koniusz | Comparison of Mid-Level Feature Coding Approaches And Pooling Strategies in Visual Concept Detection[END_REF] over the mid-level features and obtain the final image signature that is used as a data sample to learn a classifier.

*Bibliography

  the tensor rank of B k under this new representation is equal to the Rank(B k ) as formally stated below. Proposition 2 (Atom Rank). Let B = B ↑ ⊗ b and b 1 = 0, then TRank(B) = Rank(B). Proof. Rank of B is the smallest p satisfying (B↑ ⊗b) :,:,s = B • b s ∈ Span (M 1 , M 2 , ..., M p ) , ∀s = 1, ..., d, where M i ∈ S d + are rank-one. The smallest p satisfying B ∈ Span (M 1 , M 2 , ..., M p ) is equivalent as multiplication of matrix by any non-zero scalar (B•b s , b s = 0) does not change eigenvectors of this matrix which compose the spanning set.

  sample slices from X and fill B k , ∀k ∈ I K • Uniformly sample values from -1/K to 1/K and initialize b k , ∀k ∈ I K end • Vectorize inputs X s n and atoms B k , ∀s ∈ I S , ∀n ∈ I N , ∀k ∈ I K solve Lasso problem and fill β s,n , ∀s ∈ I S , ∀n ∈ I N • Uniformly sample values from -1/Kλ to 1/Kλ and fill α n , ∀n ∈ I N • Objective (0) = 0, t = 1 Main loop: while ¬ Converged do if LearnDict then

Figure 1 :

 1 Parameter sensitivity on Brodatz textures: 1(a) and 1(b) show classification accuracy and objective values against various dictionary sizes respectively, 1(c) and 1(d) show accuracy with fixed K = 20, but varying the atom rank R, and sparsity regularization λ.

(

  x,y)∈R a K r rbf ((x, y, I a ), (x , y , I b )) ≈ Va , Vb , Va = Avg (x,y)∈R a V a xy , V a xy = ⊗ r v a xy ,

Table 1 :

 1 (d) shows the classification accuracy for the coding and pooling steps w.r.t. λ controlling sparsity and suggests that the texture classification favors low sparsity. Evaluations of the proposed TOSST descriptor and comparisons to the state-of-the-art.

		(i) linear, no lum. (ii) linear, lum. (iii) RBF, no lum. (iv) RBF, lum. (v) RBF, lum., opp.
	dataset	Brodatz	Brodatz	Brodatz	Brodatz	UIUC materials
	ten. size d	6		7	30	35	45
	accuracy	93.9±0.2%	99.4±0.1%	99.4±0.2% 99.9±0.08%	58.0±4.3%
	Brodatz	ELBCM 98.72% [26]	L 2 ECM 97.9% [17]	RC 97.7% [31]
	UIUC materials	SD 43.5% [18]	CDL 52.3±4.3% [34] RSR 52.8±5.1% [9]

Table 2 :

 2 This plot illustrates the impact of K on the signature compression on PASCAL VOC07. Dictionary learning (DL) performs better than (Random Dict.) formed by sampling atoms from a distribution of DL. Evaluations of the compression w.r.t. K on third-order global descriptors and PASCAL VOC07.

	K

Acknowledgements. We thank several anonymous reviewers for their very positive reviews and insightful questions that helped improve this paper.

Appendices

A Third-order Global Image Descriptor [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] In what follows, we outline a global image descriptor from [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] used in our experiments on the PascalVOC07 dataset. Third-order Global Image Descriptor is based on SIFT [START_REF] Lowe | Object Recognition from Local Scale-Invariant Features[END_REF] aggregated into a third-order autocorrelation tensor followed by Higher Order Singular Value Decomposition [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF][START_REF] Kolda | Tensor decompositions and applications[END_REF] used for the purpose of signal whitening. This is achieved by Power Normalisation [START_REF] Koniusz | Higher-order Occurrence Pooling on Mid-and Low-level Features: Visual Concept Detection[END_REF] which is


Meltem Öztürk
email: ozturk@lamsade.dauphine.fr

Alexis Tsoukiàs
email: tsoukias@lamsade.dauphine.fr

New results on interval comparison

Keywords: preference modelling, intransitivity, interval representation

come

Introduction

The comparison of objects is an important issue in the modelling of real life situations. In decision aiding, such comparisons are done through the use of binary relations defined on the set of alternatives (A) and the set of these relations is called preference structure. A common way is to consider two relations, P and I, called respectively strict preference and indifference. There exist in the literature other types of preference structures having more than two relations. An interested reader can find more details about such structures in [START_REF] Doignon | On realizable biorders and the biorder dimension of a relation[END_REF][START_REF] Roubens | On families of semiorders and interval orders imbedded in a valued structure of preference: a survey[END_REF][START_REF] Roy | Méthodologie multicritère d'aide à la décision[END_REF][START_REF] Ph | I preference structures[END_REF][START_REF] Tsoukiàs | A new axiomatic foundation of partial comparability[END_REF][START_REF] Tsoukiàs | Double threshold orders: A new axiomatization[END_REF].

In this paper we are interested in complete preference structures having two binary relations (P is an asymmetric relation, I is the symmetric complement of P , the relation P ∪ I is complete and the relation P ∩ I is empty). Using complete structures we suppose that the decision maker is able to compare the alternatives (we can have aP b, bP a or aIb).

Let us remember that there exist also a number of studies done on partial orders where a third symmetric and irreflexive relation J, (aJb ⇐⇒ not(aP b), not(bP a), not(aIb)) called incomparability, is used ([DM41, [START_REF] Fishburn | Interval Orders and Interval Graphs[END_REF][START_REF] Tsoukiàs | Extended preference structures in MCDA[END_REF]).

Linear orders and weak orders are the most elementary complete structures. A linear order consists of a ranking of alternatives from the best one to the worst one without any ex aequo while a weak order defines indifference is an equivalence relation. A weak order is indeed a total order of the equivalence (indifference) classes of A. Following the wellknown works of Luce ([Luc56]), a new line of research appeared in preference modelling with the introduction of an intransitive indifference relation. A number of studies have shown that the transitivity of the indifference can be empirically falsifiable in some context. Undoubtedly the most famous example on this subject is that of [START_REF] Luce | Semiorders and a theory of utility discrimination[END_REF], with a cup of sweetened coffee. Before him, some authors have already suggested this phenomenon (see [START_REF] Armstrong | The determinateness of the utility function[END_REF][START_REF] Georgescu-Roegen | The pure theory of consumer's behavior[END_REF][START_REF] Fechner | Elemente der Psychophysik[END_REF][START_REF] Halphen | La notion de vraisemblance[END_REF][START_REF] Poincaré | La Valeur de la Science[END_REF]) and Fishburn and Monjardet ([FM92]) have presented some historical comments on the subject. Relaxing the property of transitivity of indifference results in different structures. It results that the semiorders are the simplest ones and there exist other ordered sets generalizing semiorders. Fishburn, in [START_REF] Fishburn | Generalisations of semiorders: a review note[END_REF], distinguishes ten nonequivalent ordered sets having an intransitive indifference relation. These are semiorders, interval orders, split semiorders, split interval orders, tolerance orders, bitolerance orders, unit tolerance orders, bisemiorders, semitransitive orders and subsemitransitive orders.

In real life situation intransitivity of indifference is generally related to the presence of threshold as it can be seen in the following example:

Example 1 Suppose that we have to define preference relations between three alternatives a, b and c which are evaluated with respect to their performance such that:

-the performance of a: 1000 -the performance of b: 1020 -the performance of c: 1040.

Let us imagine that the decision maker gives some additional information such that: he prefers one alternative to another one if the first one is greater than the second one and if the difference between their performance is greater than thirty (threshold); otherwise he is indifferent between them. It is easy to see that he is indifferent between a and b and between b and c while he prefers c to a for a maximization problem.

The presence of a threshold can be represented by an interval. It is sufficient to note that associating a value g(x) (evaluation of the alternative) and a strictly positive value q (threshold) to each element x of A is equivalent to associating two values: f 1 (x) = g(x) (representing the left extreme of an interval) and f 2 (x) = g(x) + q (representing the right extreme of the interval; obviously: f 2 (x) > f 1 (x) always holds). In the example 1, the alternative x will be preferred to the alternative y if and only if the interval associated to x is completely to the right (no intersection) of the interval associated to y.

As this small example shows, intervals appear as appropriate tools for the representation of intransitivity, thus Fishburn showed that the majority of the ten classes presented in his paper [START_REF] Fishburn | Generalisations of semiorders: a review note[END_REF] has an interval representation.

Although there exists a large literature on the preference modelling and intransitivity, a unification of representation for such structures is missing. For that reason in this paper we propose a general framework where a special interval representation is proposed. The aim of our framework is to propose a common language for the study of preference structures having an interval representation (defining a mapping to a class of preference structures through a function from the set of objects to the set of intervals) and to find some new results about these structures.

Basic Notions

Let us consider a countable finite set A of objects. Each object x of A is represented by an interval and we associate to each interval a finite number n of ordered points. We call such an object a n-points interval. If not otherwise mentioned, we will use indifferently the notation x for the object x and its associated interval. We denote a n-points interval x by a vector of n elements: f 1 (x), • • • , f n (x) , with for all x in A and i in {1, . . . , n -1}, f i (x) < f i+1 (x). Let us remark that elements f i are not necessarily equi-distanced. Figure 1 illustrates the graphical representation of a n-points interval.

f 1 (x) f 2 (x) f 3 (x) f n-1 (x) f n (x) Figure 1: n-points interval representation
We call a "relative position" and denote by ϕ(x, y) the position of the interval x with respect to the interval y (ϕ(x, y) = ϕ(y, x)). We define this notion by the help of a n-tuple as in the following: Definition 1 (Relative position) The relative position ϕ(x, y) is a n-tuple (ϕ 1 (x, y), . . . , ϕ n (x, y)) where ϕ i (x, y) represents the number of j such that f i (x) ≤ f j (y).

Intuitively, ϕ represents to what extend the position of two intervals is close to the case of two disjoint intervals, case which guaranties a strict preference.

Example 2 Let x and y be two 3-points intervals represented in figure 2, then ϕ(x, y) = (1, 0, 0) since there is only f 3 (y) being greater than f 1 (x), and f 2 (x) and f 3 (x) are greater than all the points of y. It is easy to see that the relative position shows the closest points of one interval with respect to the points of another one: ∀i,

f 1 (x) f 2 (x) f 3 (x) f 1 (y) f 2 (y) f 3 (y)
f n-ϕ i (x,y) (y) < f i (x) < f n+1-ϕ i (x,y) (y).
The number of all possible relative positions depends on n: the biggest n, the biggest the number of relative positions.

Proposition 1 [TV04] Let x and y be two n-points intervals then the number of possible relative positions

ϕ(x, y) is m = (2n)! (n!) 2 .
For example in the case of 2-points intervals, we get: m = (2 * 2)!/(2!) 2 = 6; which means that two 2-points intervals can have 6 different situations: the interval x completely to the right of the interval y, the intervals x and y have a non empty intersection (x being to the right of y), the interval x included in the interval y and the symmetric cases of these three situations.

The table 1 shows the number of possible relative positions depending on the number n. The relative position of x with respect to y can be calculated by using the relative

n = 2 n = 3 n = 4 n Relative positions 6 20 70 (2n)! (n!) 2
Table 1: Number of relative positions depending on n position of y with respect to x (we use the notation ϕ T (x, y) = ϕ(y, x)).

Proposition 2 Let ϕ(x, y) be the relative position of n-points interval x with respect to the n-points interval y then

∀i, ϕ T i (x, y) = n -|j, ϕ j ≥ (n + 1 -i)|
Example 3 Let us retake example 2. We already showed that the relative position of x with respect to y is (1, 0, 0). We calculate now the n-tuple associated to its converse:

ϕ T 1 (x, y) = 3 -|{j, ϕ j ≥ (4 -1)}| = 3 -0 = 3, ϕ T 2 (x, y) = 3 -|{j, ϕ j ≥ (4 -2)}| = 3 -0 = 3, ϕ T 3 (x, y) = 3 -|{j, ϕ j ≥ (4 -3)}| = 3 -1 = 2.
Hence we get ϕ T (x, y) = (3, 3, 2), which means that the relative position of y with respect to x is ϕ(y, x) = (3, 3, 2).

We will use the notion of relative position in order to characterize preference structures. We analyze first of all the relation between different relative positions since one relative position may give more argument for a preference relation than another one. For example, for the representation of a strict preference the case of two disjoint intervals may be more suitable than a case with two intervals, one included in the other. For that reason we introduce a new binary relation, called "stronger than", on the set of relative positions.

Definition 2 ("Stronger than" relation) Let ϕ and ϕ ′ be two relative positions, then we say that ϕ is "stronger than" ϕ ′ and note

ϕ £ ϕ ′ if ∀i ∈ {1, . . . , n}, ϕ i ≤ ϕ ′ i .
We present an example showing how we define a 'stronger than" relation.

Example 4 Let ϕ(x, y) and ϕ(x, t) be two relative positions of the figure 3. We have ϕ(x, y) = (1, 1, 0), ϕ(x, t) = (2, 1, 0). We get "ϕ(x, y) is stronger than ϕ(x, t)" since 1 ≤ 2, 1 ≤ 1 and 0 ≤ 0.

f 1 (t) f 2 (t) f 3 (t) f 1 (y)f 2 (y) f 3 (y) f 1 (x)f 2 (x) f 3 (x) Figure 3: Example: (1, 1, 0) £ (2, 1, 0)
The "stronger than" relation characterised as in definition 2 satisfies some classical properties: Proposition 3 The "stronger than" relation is a partial order (reflexive, antisymmetric and transitive) defining a lattice on the set of possible relative positions.

Proof. £ is a partial order since it is induced from the relation "<" which is reflexive, antisymmetric and transitive.

Let us remark that the relation £ is not complete. We present in figure 4 the graph of the relation £ associated to 3-points intervals. It is easy to see, for example, that we have

(2, 0, 0) ⋫ (1, 1, 0) and (1, 1, 0) ⋫ (2, 0, 0). (0, 0, 0) (1, 0, 0) (2, 0, 0) (1, 1, 0) (3, 0, 0) (2, 1, 0) (1, 1, 1) (3, 1, 0) (2, 2, 0) (2, 1, 1) (3, 2, 0) (3, 1, 1) (2, 2, 1) (3, 3, 0) (3, 2, 1) (2, 2, 2) (3, 3, 1) (3, 2, 2) (3, 3, 2) (3, 3, 3)

Preference structures with n-points intervals

We are ready now to define preference structure with a strict preference relation P and an indifference relation I, and having an n-points interval representation. Intuitively, we will define P as a set of relative positions satisfying some constraints, and construct I as the complement of P . In order to define the constraints of the construction, we do an axiomatization:

Axiom 1 The relation P ∪ I is complete and I is the complement of P (i.e. I(x, y) ⇐⇒ ¬P (x, y) ∧ ¬P (y, x) ).

Axiom 2 The relations P (x, y) and I(x, y) depends only on the relative position of x and y.

Axiom 3 If a relative position ϕ is in the set of the strict preference P then all the relative positions which are stronger than ϕ are also in the set of P .

Axiom 4 If forall i, f i (x) < f i (y) then P (x, y) is not satisfied.

Axiom 5 The set of relative positions forming P has one and only one weakest relative position (the relative position which is dominated in the sense of "stronger than" relation by all the relative positions of the set of P ).

Axiom 1 shows that P and I are exhaustive and exclusive, axiom 2 presents the comparison parameters and axiom 3 guaranties the monotonicity. Every relative position is not a good candidate to represent a strict preference. Axiom 4 eliminates some undesired situations for the relation P . The role of the weakest relative position of a set of P is very important since we can determine all the other elements of the set by the help of the weakest one (axiom 3). Using this reasoning, the axiom 5 guarantees a unique representation for the strict preference relations by forbidding the existence of more than one weakest relative positions in their set (each set of P can be represented by its weakest relative position).

According to this axiomatisation each relative position, excepts the one violating the axiom 4, will be once and only once the weakest relative position of the set of relative positions forming the strict preference relation. This remark helps us to calculate the number of sets satisfying our five axioms.

Proposition 4 The number of sets satisfying axioms 1-5 for n-points intervals is

(2n)! (n!) 2 - 1 n+1 2n n .
It means that there are respectively 4, 15 and 56 sets satisfying our axiomatisation when 2-points, 3-points and 4-points intervals are used for the representation.

We can present now the n-points interval representation of a preference structure satisfying axioms 1-5. In this representation we denote by P ≤ϕ the preference relation having the relative position ϕ as the weakest one. In the same way we denote by I ≤ϕ the symmetric complement of the relation P ≤ϕ .

Definition 3 Let ϕ = (ϕ 1 , . . . , ϕ n ) be a n-tuple in {0, 1, . . . , n}, and x and y two npoints intervals. The preference relations P ≤ϕ , I ≤ϕ associated to ϕ where ϕ ⋫ (n, n -1, n -2, . . . , 1) is defined as

P ≤ϕ (x, y) ⇐⇒ ϕ(x, y) £ ϕ I ≤ϕ (x, y) ⇐⇒ ¬P ≤ϕ (x, y) ∧ ¬P ≤ϕ (y, x)
It is easy to verify that the preference structure associated to a n-tuple ϕ characterised as in definition 3 verifies the axioms 1, 2, 3, 4, 5 and satisfies the conditions that we defined in the beginning of the paper, i.e. P is an asymmetric relation, I is the symmetric complement of P , the relation P ∪ I is complete and the relation P ∩ I is empty. Now, consider the strict preference relation, presented in figure 3, having the relative position (2,0,0) as the weakest relative position.

f 1 (y) f 2 (y) f 3 (y) f 1 (x) f 2 (x) f 3 (x)
P ≤(2,0,0) : (0, 0, 0) ∪ (1, 0, 0) ∪ (2, 0, 0)

Then P ≤(2,0,0) (x, y) iff f 1 (y) < f 1 (x), f 2 (y) < f 2 (x), f 3 (y) < f 2 (x)
and f 3 (y) < f 3 (x). We can remark that the second and the last inequalities are redundant. In order to avoid such redundancies we introduce a new notion that we call the component set of a n-tuple ϕ.

Definition 4 Let ϕ = (ϕ 1 , . . . , ϕ n ) be a n-tuple in {0, 1, . . . , n} the component set Cp ≤ϕ associated to ϕ is the set of couples (nϕ i , i) such that there is no i ′ < i with ϕ i ′ ≤ ϕ i .

For instance Cp ≤(2,0,0) = {(1, 1)(3, 2)}. Hence, Cp ≤ϕ represents the set of couples of points that are necessary and sufficient to be compared. Conditions on the elements of Cp ≤ϕ guarantee the minimality of the representation. The set Cp ≤ϕ contains all the information concerning the preference structure. The relations between different component sets give information about relation between different preference relation.

Proposition 5 if Cp ≤ϕ ⊆ Cp ≤ϕ ′ then P ≤ϕ ′ ⊆ P ≤ϕ and I ≤ϕ ⊆ I ≤ϕ ′ .

Following the definition 4, one can also say that the axiom 4 is verified by P ≤ϕ iff Cp ≤ϕ contains at least one (i, j) with i ≥ j.

Some results

In this section we present some results on the definition of some classical properties of binary relations in our framework. We will then show the use of these results for the characterisation of different preference structures having an n-points interval representation.

We begin by the property of transitivity. The transitivity of the strict preference relation is required for the majority of preference structures. However some preference structures having an intransitive strict preference relation are also studied by some researchers.

For instance, Abbas proposed in its PhD thesis ( [START_REF] Abbas | Contribution au rapprochement de la théorie des graphes et de l'aide à la décision: graphes parfaits et modèles de préférence[END_REF]) a new structure, called tangential circle orders, having an intransitive preference relation. He showed that it is possible to characterise these structures with a geometrical representation in such a way that every object is presented by a circle and when two circles have an empty intersection the preference relation P is verified, otherwise the indifference relation I is verified. The way that we define the preference structure associated to a n-tuple ϕ (definition 3) does not necessarily provide a transitive strict preference. We present in the following the condition that a preference structure associated to a ϕ must satisfy in order to have a transitive P ≤ϕ .

Proposition 6 P ≤ϕ is transitive if and only if ∀(i, j) ∈ Cp ≤ϕ i ≥ j.

Proof.

-If ∀(i, j) ∈ Cp ≤ϕ i ≥ j then P ≤ϕ is transitive: obvious.

-If P ≤ϕ is transitive then ∀(i, j) ∈ Cp ≤ϕ i ≥ j: We prove this result by showing that if ∃(i, j) ∈ Cp ≤ϕ i < j then ∃x, y, z, P ≤ϕ (x, y) ∧ P ≤ϕ (y, z) and¬P ≤ϕ (x, z).

We present now an example of intransitive strict preference relation which satisfies the definition 3.

Example 5 Let P 3 ≤(3,2,0) be a strict preference relation (P 3 ≤(3,2,0) (x, y) ⇐⇒ (f 3 (y) < f 3 (x)) ∧ (f 1 (y) < f 2 (x)) and Cp ≤ϕ = {(2, 1)(3, 3)}). Consider three 3-points intervals, x, y and z such that:

f 1 (x) < f 1 (y) < f 2 (x) < f 1 (z) < f 2 (y) < f 2 (z) < f 3 (z) < f 3 (y) < f 3 (x)
It is easy to see that we have P 3 ≤(3,2,0) (x, y) and P 3 ≤(3,2,0) (y, z) but not P 3 ≤(3,2,0) (x, z) (see figure 5). We called intransitive set an order having an intransitive preference relation P .

f 1 (z) f 2 (z) f 3 (z) f 1 (y) f 2 (y) f 3 (y) f 1 (x) f 2 (x) f 3 (x)

Definition 5

The relation P ≤ϕ ∪I ≤ϕ on a finite set A, is an intransitive set if its asymmetric part P ≤ϕ is intransitive.

We showed that there is a number of preference structures which do not have a transitive indifference. We present now the conditions that a preference structure associated to a ϕ must satisfy in order to have a transitive indifference relation.

Proposition 7 I ≤ϕ is transitive if and only if ∃i ∈ {1, . . . , n}, Cp ≤ϕ = {(i, i)}.

Proof.

-If Cp ≤ϕ = {(i, i)} then I ≤ϕ is transitive: obvious.

-If I ≤ϕ is transitive then Cp ≤ϕ = {(i, i)}: We prove this result by contradiction. Supposing that I ≤ϕ is transitive we analyse two cases: ∃(i, j) ∈ Cp ≤ϕ , i = j and ∀(i, j) ∈ Cp ≤ϕ , i = j and |Cp ≤ϕ | > 1. We show that these two cases are contradictory with the transitivity of I ≤ϕ .

This result shows that, the only structures having transitive indifference are the ones where two points of the same level are compared (intuitively it means that we do not really need intervals for the representation, points are sufficient. Let us remark that it is the case for linear orders and weak orders). Such a result is coherent with the use of interval representation for intransitive indifference since we need more than one point to represent intransitivity (I ≤ϕ is intransitive if and only if ∃i ∈ {1, . . . , n}, Cp ≤ϕ = {(i, j)} where i = j or |Cp ≤ϕ | > 1).

Such a result allows us to determine the representation of weak orders with our approach.

Corollary 1 P ≤ϕ ∪ I ≤ϕ is a weak order if and only if ∃i ∈ {1, . . . , n}, Cp ≤ϕ = {(i, i)}.

Proof.

-obvious. Such a result allows the existence of different representations for weak orders when n-points intervals are used. It is easy to verify the following assertion.

Proposition 8 Let ϕ be a relative position of two n-points intervals. The number of Cp ≤ϕ representing a weak order is n.

For example with 2-points intervals, there exist two ways to characterize weak orders:

P ≤(1,1) (x, y) ⇐⇒ f 1 (y) < f 1 (x) (Cp ≤ϕ = ((1, 1))) and P ≤(2,0) (x, y) ⇐⇒ f 2 (y) < f 2 (x) (Cp ≤ϕ = ((2, 2))).
We can generalise the result of the corollary 1 on the characterisation of d-weak orders. A d-weak order is defined as the intersection of d weak orders. It is shown that these structures have an interval representation. Proposition 9 ([ Özt05]) P ∪ I is a d-weak order if and only if there exists d real-valued functions g i (i ∈ {1, . . . , d}) defined on A such that ∀x, y ∈ A, xP y ⇐⇒ ∀i ∈ {1, . . . , d}, g i (x) > g i (y); ∀x, ∀i ∈ {1, . . . , d -1}, g i+1 (x) ≥ g i (x).

(1) Such a representation corresponds to the use of d-points intervals with our approach. We generalize this result to the case of n-points intervals where n can be greater than or equal to d.

Corollary 2 P ≤ϕ ∪ I ≤ϕ is a d-weak order if and only if |Cp ≤ϕ | = d and ∀(i, j) ∈ Cp ≤ϕ , i = j.
Let us remind that a 2-weak order corresponds to what Fishburn calls a biweak order (let us remind that a biweak order is equivalent to a bilinear order (see [START_REF] Fishburn | Generalisations of semiorders: a review note[END_REF]). We present in the following one of the 4-points interval representation of a 3-weak order.

Example 6

The relation P ≤(3,3,1,0) ∪ I ≤(3,3,1,0) is a 3-weak order (we have Cp ≤(3,3,1,0) = ((1, 1)(3, 3)(4, 4))).

As it can be seen in the previous example, when n-points intervals (n > d) are used, there exist more than one representation for d-weak orders. The number of all possible representations depends on n and is calculated easily as in the following proposition. It is shown that for a complete preference structure where P and I are exhaustive and exclusive, the relation P ∪ I is Ferrers if and only if P.I.P ⊆ P (i.e. ∀x, y, z, w ∈ A, (xP y ∧ yIw ∧ wP z) =⇒ xP w).

Using this remark we present now the condition of a Ferrers relation in our approach.

Proposition 11 P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ if and only if Cp ≤ϕ = {(i, j)} with i ≥ j.

Proof.

-If Cp ≤ϕ = {(i, j)} where i ≥ j then P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ : obvious.

-If P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ then Cp ≤ϕ = {(i, j)} where i ≥ j: We do our analysis in two parts.

• first of all if Cp = (i, j) with i < j then P ≤ϕ is not transitive. Since I ≤ϕ is reflexive P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ is not satisfied when P ≤ϕ is not transitive.

• Here we analyze two cases where |Cp ≤ϕ | > 1: ∃(i, j) ∈ Cp ≤ϕ , i < j and ∀(i, j) ∈ Cp ≤ϕ , i ≥ j.

-The first one provides an intransitive P ≤ϕ .

-The key point of the analysis of the second case is the definition of I ≤ϕ when |Cp ≤ϕ | > 1: let (i, j), (l, m) be two elements of Cp ≤ϕ . Thus, we have f i (x) ≥ f j (y)∧f l (y) ≥ f m (x) with (i, j) = (l, m) =⇒ I ≤ϕ (x, y). In this case we have one point of x greater than one point of y and one point of y greater than one point of x. In such a case one can always find four elements w, x, y, z such that P ≤ϕ (w, x), I ≤ϕ (x, y), P ≤ϕ (y, z) and ¬P ≤ϕ (w, z).

It is easy to see that the proposition 11 is equivalent to the following assertion because of the axiom 4.

Proposition 12 P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ if and only if |Cp ≤ϕ | = 1.

We are able now to characterize an interval order by the help of our approach:

Corollary 3 P ≤ϕ ∪ I ≤ϕ is an interval order if and only if |Cp ≤ϕ | = 1.
Proof.

-If Cp ≤ϕ = {(i, j)} where i ≥ j then P ≤ϕ ∪ I ≤ϕ is an interval order: We prove that P ≤ϕ ∪ I ≤ϕ is reflexive and complete and P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ .

-If P ≤ϕ ∪ I ≤ϕ is an interval order then Cp ≤ϕ = (i, j) where i ≥ j: if P ≤ϕ ∪ I ≤ϕ is an interval order then P ≤ϕ .I ≤ϕ .P ≤ϕ ⊆ P ≤ϕ which implies |Cp ≤ϕ | = 1.

In the following proposition we give the number of possible representations of interval orders when n-points intervals are used.

Proposition 13 Let ϕ be a relative position of two n-points intervals. The number of Cp ≤ϕ representing an interval order is n(n-1) 2 .

For instance there is only one representation of interval order when 2-points intervals are used while there are three representations when 3-points intervals are used.

Like for the case of weak orders we generalise the result of the corollary 3 to the case of d-interval orders. A d-interval order is defined as the intersection of d intervals orders and we showed in [ Özt05] that they have an interval representation.

(2k-1) (x) > g (2k) (y), ∀x, ∀i ∈ {1, . . . , d -1}, g i+1 (x) ≥ g i (x).
Similar to the case of d-weak order, the interval representation that we suggested in proposition 14 for d-interval orders makes use of 2d functions g i defined on disjoint sets. Such a representation corresponds to the use of 2d-points intervals with our approach. In addition with such a representation every ordered index belonging to Cp ≤ϕ is formed by two consecutive points g i and g i+1 . We generalize this result to the case of n-points intervals where n can be greater than or equal to 2d. The number of all possible n-points interval representation for bitolerance orders is given in the following.

Proposition 15 Let ϕ be a relative position of two n-points intervals. The number of Cp ≤ϕ representing a bitolerance order is 2 n 4 + n 3 .

structures have a 3-points interval representation.

It is easy to remark that 3-points intervals propose a mininal representation for threeweak orders, split interval orders, triangle orders and intransitive orders.

Conclusion

In this paper, we proposed a framework for the interval comparison. This framework is general in the sense that it generates all the possible comparisons respecting certain axioms that we judge natural and not very restrictive. It allowed us to generalize the definitions of certain properties such as transitivity, Ferrers relation etc. and it provided an exhaustive view of the comparison with 2-points and 3-points intervals. It results that 2-points intervals may be used in the simplest representation of bilinear orders and interval orders while 3-points intervals provide the simplest representation for three-weak orders, split interval orders, triangle orders and intransitive orders. We showed that certain structures may have more than one representation even if these ones are minimal (like in the case of triangle orders). Our framework showed also that there exist an easiest way to represent some structures. For instance, the classical representation of triangle orders and intransitive orders make use of geometric figures (dimension two). As a result they have more complicated comparison rules (for example the comparison of circles is done by a quadratic function). By proposing a 3-points interval representation we facilitate the comparison rules and the preference representation. Some possible interesting extensions of this paper would be the exhaustive study of 4points interval comparison (let us remark that in this case there are 56 sets of P satisfying our axiomatisation and some of them are already known thanks to the propositions that we presented in this paper) and the integration of some coherence condition.

Figure 2 :

 2 Figure 2: Relative position ϕ(x, y) = (1, 0, 0)

Figure 4 :

 4 Figure 4: Graph of "stronger than" relation for n = 3

Figure 5 :

 5 Figure 5: P 3 ≤(3,2,0) (x, y), P 3 ≤(3,2,0) (y, z) and not P 3 ≤(3,2,0) (x, z)

Proposition 10

 10 Let ϕ be a relative position of two n-points intervals. The number of Cp ≤ϕ representing a d-weak order is n d . For example, bilinear orders have one (resp. three) representation when 2-points intervals (resp. 3-points intervals) are used. Another class of preference structures is the one of interval orders where the indifference is not transitive. The relation P ∪ I is an interval order if and only if it is reflexive, complete and a Ferrers relation. Let us give first of all the definition of a Ferrers relation: Definition 6 Let R be a binary relation defined on the set A × A. R is a Ferrers relation iff ∀x, y, z, w ∈ A, (xRy ∧ zRw) =⇒ (xRw ∨ zRy).

Corollary 4 P

 4 ≤ϕ ∪ I ≤ϕ is a d-interval order if and only if |Cp ≤ϕ | = d and ∀(i, j) ∈ Cp ≤ϕ , i ≥ j. Let us remind that a special class of d-interval orders is the class of 2-interval orders which is identical to the class of trapezoid orders and to the class of bitolerance orders ([Fis85]). Corollary 5 P ≤ϕ ∪ I ≤ϕ is a bitolerance order if and only if it is a d-interval order and |Cp ≤ϕ | = 2.

Proposition 14 ([ Özt05])

  P ∪I is d-interval order if and only if there exist 2d real-valued functions g i (i ∈ {1, . . . , 2d}) defined on A, such that , ∀x, y ∈ A, xP y ⇐⇒ ∀k ∈ {1, . . . , d}, g

When 3-points intervals are used, there is just one representation for bitolerance orders which is the one of split interval orders.

Finally we are interested in a preference structure which is defined as the intersection of a weak order and an interval order. We called such a structure a triangle order. Like in the case of d-weak orders and d-interval orders, these structures have an interval representation.

Proposition 16 ([ Özt05]) P ∪I is a triangle order if and only if there exists 3 real-valued functions

(2)

We generalize this result to the case of n-points intervals where n ≥ 3.

Proposition 17 P ≤ϕ ∪ I ≤ϕ is a triangle order if and only if Cp ≤ϕ = {(l, l), (i, j)}, where i ≥ j.

Let us remark that if the index l of the ordered index of the weak order is smaller then the indexes of interval order (l < j) then the resulting triangle is oriented to the left, otherwise it is oriented to the right.

The number of all the possible n-points interval representations that a triangle order can have is given hereafter.

Proposition 18 Let ϕ be a relative position of two n-points intervals. The number of Cp ≤ϕ representing a triangle order is 2 n 3 .

Triangle orders have two representations when 3-points intervals are used.

We recapitulate in table 2 the number of n-points interval representations of some preference structures for 2, 3, 4 and n-points intervals.

The results of this section provide an exhaustive view of the comparison of 2-points and 3-points intervals.

2-points intervals and 3-points intervals

We present in this section all the preference structures having a 2-points and 3-points interval representation.

2-points intervals

The 2-points intervals are the simplest intervals that our approach makes use of since only the extreme points of intervals are considered. Let us remind that four of six different relative positions of 2-points intervals satisfy our axiomatisation. We show in this subsection that three different preference structures can be represented with the help of these four relative positions: weak orders, bilinear orders and interval orders. Table 3 recapitulates all these preference structures.

Preference Structure P ≤ϕ , I ≤ϕ interval representation

Table 3: Preference structures with 2-points interval representation

It is easy to remark that 2-points intervals propose a minimal representation for a bilinear order and an interval order since for both of them we need two different points. However each representation of weak orders makes use of only one point of 2-points intervals. The other point does not have any role for the construction of the ordered set. This is the reason for which the simplest representation of weak orders with our approach is obtained with 1-point intervals which is equivalent to the classical numerical representation of weak orders where every object is evaluated by one function. The use of n-points intervals (n > 1) for the representation of weak orders can be correct but will be more complicated than its classical numerical representation.

3-points intervals

In this section we present the results of the analysis of the fifteen sets of P which satisfy our axiomatisation. Our study shows that from the fifteen sets of P , seven different preference structures can be defined, some of them having more than one 3-points interval representation: weak orders and bi-weak orders have three different 3-points interval representations while three-weak orders have one, interval orders have three, split interval orders have one, triangle orders have two and intransitive orders have two. Let us remark that the classical representation of the majority of these structures do not make use of intervals (intervals can be seen as vectors of some ordered points). For instance, weak orders use simple numbers while bi-weak orders (resp. three-weak orders) utilize two (resp. three), not necessarily ordered numbers. Triangle orders are represented by triangles and intransitive orders by circles. Our study shows that all these seven