The Boolean SATisfiability Problem and the orthogonal group O(n) [full text: .pdf (156 kB)]Last updated: 5 April 2019 at 16:00:14 CEST
Abstract - The convex hull of any subset of vertices of an n-dimensional hypercube contains no other vertex of the hypercube. This result permits the application of some theorems of n-dimensional geometry to digital feed-forward neural networks. Also, the construction of the convex hull is proposed as an alternative to more traditional learning algorithms. Some preliminary simulation results are reported.
Abstract - The classical Cover results on linear separability of points in R^d are a milestone in neural network theory. Nevertheless they are not valid for digital input networks because in this case the points are not in general position being vertices of a d-dimensional hypercube. I show here that for large d all Cover findings can be extended to this case. It is also shown that for n < O((d + 1)^(3/2)) the number of linear separations of n random hypercube vertices tends to that of n points in general position.
Abstract - In his seminal paper Cover used geometrical arguments to compute the probability of separating two sets of patterns with a perceptron. We extend these ideas to feedforward networks with hidden layers. There are intrinsic limitations to the number of patterns that a net of this kind can separate and we find quantitative bounds valid far any net with d input and h hidden neurons.
Abstract - We extend the geometrical approach to the Perceptron and show that, given n examples, learning is of maximal difficulty when the number of inputs d is such that n = 5d. We then present a new Perceptron algorithm that takes advantage of the peculiarities of the cost function. In our tests it is more than two times faster that the standard algorithm. More importantly it does not have fixed parameters, like the usual learning constant \eta, but it adapts them to the cost function. We show that there exist an optimal choice for \beta, the steepness of the transfer function. We present also a brief systematic study of the parameters \eta and \beta of the standard Perceptron algorithm.
Abstract - We present a geometrical interpretation of ordering in self-organizing feature maps. This view provides simpler proofs of Kohonen ordering theorem and of convergence to an ordered state in the one dimensional case. At the same time it explains intuitively the origin of the problems in higher dimensional cases. Furthermore it provides a geometrical view of the known characteristics of learning in self-organising nets.
Abstract - Unsupervised learning applied to an unstructured neural network can give approximate solutions to the travelling salesman problem. For 50 cities in the plane this algorithm performs like the elastic net of Durbin and Willshaw [Durbin 1987] and it improves when increasing the number of cities to get better than simulated annealing for problems with more than 500 cities. In all the tests this algorithm requires a fraction of the time taken by simulated annealing.
Abstract - We present and analyze a Self Organizing Feature Map (SOFM) for the NP-complete problem of the travelling salesman (TSP): finding the shortest closed path joining N cities. Since the SOFM has discrete input patterns (the cities of the TSP) one can examine its dynamics analytically. We show that, with a particular choice of the distance function for the net, the energy associated to the SOFM has its absolute minimum at the shortest TSP path. Numerical simulations confirm that this distance augments performances. It is curious that the distance function having this property combines the distances of the neuron and of the weight spaces.
Abstract - A self-organising feature map sorts n real numbers in O(n) time apparently violating the O(n log n) bound. Detailed analysis shows that the net takes advantage of the uniform distribution of the numbers and, in this case, sorting in O(n) is possible. There are, however, an exponentially small fraction of pathological distributions producing O(n^2) sorting time. It is interesting to observe that standard learning produced a smart sorting algorithm.
Abstract - Combinatorial optimization is an active field of research in Neural Networks. Since the first attempts to solve the travelling salesman problem with Hopfield nets several progresses have been made. I will present some Neural Network approximate solutions for NP-complete problems that have a sound mathematical foundation and that, beside their theoretical interest, are also numerically encouraging. These algorithms easily deal with problems with thousands of instances taking Neural Network approaches out of the "toy-problem" era.
Abstract - In this paper we present two methods for non-uniformity correction of imaging array detectors based on neural networks, both of them exploit image properties to supply lack of calibrations while maximizing the entropy of the output. The first method uses a self-organizing net that produces a linear correction of the raw data with coefficients that adapt continuously. The second method employs a kind of contrast equalization curve to match pixel distributions. Our work originates from Silicon detectors but the treatment is general enough to be applicable to many kinds of array detectors like those used in Infrared imaging or in high energy physics.
Abstract - The maximum clique problem is a classical problem in combinatorial optimization which finds important applications in different domains. In this paper we try to give a survey of results concerning algorithms, complexity, and applications of this problem, and also provide an updated bibliography. Of course, we build upon precursory works with similar goals.
Abstract - In this paper, a new heuristic for approximating the maximum clique problem is proposed, based on a detailed analysis of a class of continuous optimization models which provide a complete characterization of solutions to this NP-hard combinatorial problem. The idea is to alter a regularization parameter iteratively in such a way that an iterative procedure with the updated parameter value would avoid unwanted, inefficient local solutions, i.e., maximal cliques which contain less than the maximum possible number of vertices. The local search procedure is performed with the help of the replicator dynamics, and the regularization parameter is chosen deliberately as to render dynamical instability of the (formerly) stable solutions which we want to discard in order to get an improvement. In this respect, the proposed procedure differs from usual simulated annealing approaches. To demonstrate the validity of this approach, we report on the performance applied to selected DIMACS benchmark graphs.
The paper reviews some of the existing exact bounds to the maximum clique of a graph and successively presents a new upper and a new lower bound. The new upper bound is n - rank(AC)/2, where AC is the adjacency matrix of the complementary graph, and derives from a formulation of the maximum clique problem in complex space. The new lower bound (see text for details) improves strictly the present best lower bound published by Wilf in 1986. Throughout the paper an eye is kept on the computational complexity of actually calculating the bounds. At the end, the various bounds are compared on 700 random graphs.
We present a new formulation of the maximum clique problem of a graph in complex space. We start observing that the adjacency matrix A of a graph can always be written in the form A = B B where B is a complex, symmetric matrix formed by vectors of zero length (null vectors) and the maximum clique problem can be transformed in a geometrical problem for these vectors. This problem, in turn, is translated in spinorial language and we show that each graph uniquely identifies a set of pure spinors, that is vectors of the endomorphism space of Clifford algebras, and the maximum clique problem is formalized in this setting so that, this much studied problem, may take advantage from recent progresses of pure spinor geometry.
Delineiamo le attivita' sviluppate negli ultimi anni dal Corso di Laurea in Fisica dell'Universita' di Trieste per l'orientamento dei ragazzi delle scuole secondarie. Ci concentriamo sull'impianto generale e sugli obbiettivi che ci siamo proposti di ottenere con queste iniziative.
We present a formulation of the Maximum Clique problem of a graph as a geometrical problem of null vectors in complex space. This problem is then translated in spinorial language.
Since some time the extension of neural networks to the complex field C has received considerable attention for possible applications to phenomena in which the variables contain also phase information. In this paper we focus the attention on the complex transfer function. In compliance to Liouville's theorem, that forbids entire bounded analytic functions, a frequent choice has been to separate real and imaginary part of the output of a neuron. We show that this choice corresponds to throwing the baby with the water since these kind of complex neurons are identical to 2 purely real ones thus losing any possible complex advantage. On the contrary we show that a neuron with an analytic transfer function provides an output that is not approximable by 2 real neurons, like in the previous case, thus indirectly proving the superior computing power of truly complex neurons.
Scopo dell'iniziativa di far avvicinare i giovani alla scienza e in particolare alla Fisica tramite il naturale connubio della fisica con lo sport. L'abbinamento "Fisica e Sport" dettato dalla consapelovezza che spesso trascuriamo il fatto che la Fisica alla base di molte delle attivit comuni di ogni giorno. Lo sport solo una delle applicazioni pratiche della fisica che coinvolge tutta la popolazione.
After a brief discussion of the computational complexity of Clifford algebras, we present a new basis or even Clifford algebra Cl(2 m) that simplifies greatly the actual calculations and, without resorting to the conventional matrix isomorphism formulation, obtains the same complexity. In the last part we apply these results to the Clifford algebra formulation of the NP-complete problem of the maximum clique of a graph introduced in a previous paper.[Full text courtesy of: Journal of Mathematical Physics. Copyright (2009) American Institute of Physics. This article may be downloaded for personal use only. Any other use requires prior permission of the author and the American Institute of Physics.]
We investigate the properties of the Extended Fock Basis (EFB) of Clifford algebras [1] with which one can replace the traditional multivector expansion of Cl(g) with an expansion in terms of simple (also: pure) spinors. We show that a Clifford algebra with 2m generators is the direct sum of 2m spinor subspaces S characterized as being left eigenvectors of \Gamma; furthermore we prove that the well known isomorphism between simple spinors and totally null planes holds only within one of these spinor subspaces. We also show a new symmetry between spinor and vector spaces: similarly to a vector space of dimension 2m that contains totally null planes of maximal dimension m, also a spinor space of dimension 2m contains "totally simple planes", sub-spaces made entirely of simple spinors, of maximal dimension m.
Abstract - We present an algorithm for data preprocessing of an associative memory inspired to an electrostatic problem that turns out to have intimate relations with information maximization.
Abstract - We investigate the relations between spinors and null vectors in Clifford algebra of any dimension with particular emphasis on the conditions that a spinor must satisfy to be simple (also: pure). In particular we prove: i) a new property for null vectors: each of them bisects spinor space into two subspaces of equal size; ii) that simple spinors form one-dimensional subspaces of spinor space; iii) a necessary and sufficient condition for a spinor to be simple that generalizes a theorem of Cartan and Chevalley which becomes a corollary of this result. We also show how to write down easily the most general spinor with a given associated totally null plane.
Abstract - We present a necessary and sufficient condition for a spinor $\omega$ to be of nullity zero, i.e. such that for any null vector $v$, $v \omega \ne 0$. This dives deeply in the subtle relations between a spinor $\omega$ and $\omega_c$, the (complex) conjugate of $\omega$ belonging to the same spinor space.
Abstract - We begin showing that for even dimensional vector spaces $V$ all automorphisms of their
Clifford algebras are inner. So all orthogonal transformations of $V$ are restrictions to $V$ of
inner automorphisms of the algebra. Thus under orthogonal transformations $P$ and $T$ --- space and
time reversal --- all algebra elements, including vectors $v$ and spinors $\varphi$, transform as
$v \to x v x^{-1}$ and $\varphi \to x \varphi x^{-1}$ for some algebra element $x$. We show that
while under combined $PT$ spinor $\varphi \to x \varphi x^{-1}$ remain in its spinor space, under
$P$ or $T$ separately $\varphi$ goes to a \emph{different} spinor space and may have opposite
chirality. We conclude with a preliminary characterization of inner automorphisms with respect to
their property to change, or not, spinor spaces.
Abstract - We show that the binary representation of the integers has a role to play in many aspects of Clifford algebras.
Abstract - We present a formulation of the Boolean Satisfiability Problem in spinor language that allows to give a necessary and sufficient condition for unsatisfiability. With this result we outline an algorithm to test for unsatisfiability with possibly interesting theoretical properties.
Abstract - We begin showing that for even dimensional vector spaces $V$ all automorphisms of their
Clifford algebras are inner. So all orthogonal transformations of $V$ are restrictions to $V$ of
inner automorphisms of the algebra. Thus under orthogonal transformations $P$ and $T$ --- space and
time reversal --- all algebra elements, including vectors $v$ and spinors $\varphi$, transform as
$v \to x v x^{-1}$ and $\varphi \to x \varphi x^{-1}$ for some algebra element $x$. We show that
while under combined $PT$ spinor $\varphi \to x \varphi x^{-1}$ remain in its spinor space, under
$P$ or $T$ separately $\varphi$ goes to a \emph{different} spinor space and may have opposite
chirality. We conclude with a preliminary characterization of inner automorphisms with respect to
their property to change, or not, spinor spaces.
Abstract - There are several topics of Clifford algebra where discrete and continuous worlds are deeply intertwined, one for all the Cartan theorem that expresses continuous automorphisms by a succession of reflections, but they thrive separately an do not fit in a comprehensive picture. We will focus on some cases where Clifford algebra manifestly shows discrete features with the hope that shedding light on some details may help a more complete scenario to come out of darkness. In particular we will tackle two themes: the first is the ubiquitous role played by the base two expansion of integers in Clifford algebra: for example the interplay between the signature of the vector space and the 'spinorial chessboard' or the determination of row and column indices of the isomorphic matrix algebra. The second theme is the contribution that could give the Abelian subalgebra of the idempotents to the solution of the SATisfiability problem, the mother of all combinatorial problems.
Abstract - We show that complex representations of Clifford algebra can always be reduced either to a real or to a quaternionic algebra depending on signature of complex space thus showing that complex spinors are unavoidably either real Majorana spinors or quaternionic spinors. We use this result to support (1,3) signature for Minkowski space.
Abstract - The Boolean SATisfiability Problem (SAT) is the archetypical combinatorial problem and more than 20 years ago the problem was formulated in the language of statistical mechanics. This brought both theoretical insights and competitive solution algorithms in some instances. In this work we present a completely different SAT formulation in the language of spinors - Clifford algebra - that yields a purely geometrical necessary and sufficient condition for unsatisfiability. With this result we outline an algorithm to test for unsatisfiability with possibly interesting theoretical properties. In this form the problem has some similarity with the Onsager solution of the two dimensional Ising model and we discuss possible interchanges.
The Boolean SATisfiability Problem and the orthogonal group O(n) [full text: .pdf (156 kB)]Abstract - We explore the relations between the Boolean Satisfiability Problem with n literals and the orthogonal group O(n) and show that all 2^n possible solutions lie in the compact and disconnected real manifold of dimension n(n-1)/2 of this group.
Back to: M. Budinich's home page or publications page