Tech Report on Regularized Least Squares
An MIT tech report with things everyone ought to know about (dense) regularized least squares is available in the publications section. It includes all the goodies on how finding a good a regularization parameter via leave-one-out cross-validation is essentially free, with a couple of different proofs.
I’m not trying to have this published at the conference or journal level because I don’t think it contains (enough) “new” material, but I certainly haven’t seen these results usefully collected together like this before. I hope people find this useful.
1221 days ago | machine-learning |
AIStats 2007 Paper on AClass
My AIStats 2007 paper on AClass, an online Bayesian classification algorithm, is available in the publications section.
1237 days ago | machine-learning |
Fenchel Page Added
I’ve added a page on my Fenchel duality and value regularization work.
1253 days ago | machine-learning |
Publications Section Added
I added a publications section to the site. This should be the most up-to-date location for my published work. I just added all three versions of my work on infinite-sigma limits of Gaussian kernels for Tikhonov regularization (the initial tech report, the NIPS paper, and the JMLR paper), and my ICSLP 2006 paper on discriminating speech from non-speech using Shamma’s “cortical” features.
1379 days ago | |
The national character of apes
From Bertrand Russell 1927, speaking about American and German primate research, quoted in Owen Flanagan’s “The Science of the Mind”:
One may say broadly that all the animals that have been carefully observed have behaved so as to confirm the philosophy in which the observer believed before his observations began. Nay, more, they have all displayed the national characteristics of the observer. Animals studied by Americans rush about frantically, with an incredible display of hustle and pep, and at last achieve the desired result by chance. Animals observed by Germans sit still and think, and at last evolve the solution out of their inner consciousness. To the plain man such as the present writer, this situation is discouraging.
1384 days ago | quotes |
CL-BLAPACK alpha release
NOTE: I have received reports that this code no longer installs/works easily. I do not have time or ability to offer support. I will accept patches.
I am releasing an alpha version of cl-blapack, a Common Lisp library for making Fortran-style calls to BLAS and LAPACK. To try it, you will need
cl-blapack-alpha.tar.gz
fnv-alpha-2.tar.gz
I include the README for cl-blapack:
This is an alpha release of cl-blapack, a wrapper around the Fortran BLAS and LAPACK libraries for dense linear algebra.
The software relies on org.middle-angle.foreign-numeric-vector for foreign (non-Lisp heap) storage, and CFFI.
The software generates CFFI interfaces by parsing the Fortran reference implementation of LAPACK (available at www.netlib.org/LAPACK). I include files blas-cffi.lisp and lapack-cffi.lisp which are the results of this parsing. If you want to regenerate your own, download LAPACK, load the org.middleangle.cl-blapack-gen system, and run
(generate-blapack-interface:generate-blapack-files #p”/path/to/LAPACK”)
In general, users should not need to do this—- the supplied interface files should work fine. To load the interface, load org.middleangle.cl-blapack system.
To see an example, load the org.middleangle.cl-blapack-examples system, and execute
(blapack-examples:simple-example)
The cl-blapack library allows one to write Fortran-style code to call BLAS and LAPACK. There is one convenience—- scalar arguments are automatically packaged by the system into foreign-numeric-vectors of length 1 (see blapack-cffi-types.lisp); this may possibly be a source of inefficiency if we are making frequent small calls to the libraries.
NOTE: As of this writing, the code is only sure to work with SBCL. We need to make sure that floating-point traps are turned off. To add support for another implementation, write the appropriate version of with-blapack in cl-blapack.lisp (it’s a NOOP for non-SBCL right now). The code has been tested (the example runs) under recent SBCLs on both x86 and x86-64 machines.
NOTE: We assume that BLAS/LAPACK have been compiled so that all integers (representing indexes into arrays) are 32-bit. This seems to be the case currently even on 64-bit machines, but we need to monitor this as it could change in the future.
This software is released under the modified-BSD license (no advertising clause), see LICENSE for details.
As of 04 November 2006, this code is available at http://middleangle.com/rif/software/cl-blapack-alpha.tar.gz
All comments, suggestions, performance reports, and assistance should be sent to
rif
rif@mit.edu
1402 days ago | common-lisp |
This is a test of MathML capabilities.
1427 days ago | |
with-open-files
A useful macro for opening multiple files simultaneously. Takes a list of filenames (can be pathnames), returns a function that takes a filename and provides the (open) stream for the associated file, and wraps the whole thing in an unwind-protect for safety. All the files have to take the same open args (for instance, they’re all going to be input or all going to be output).
(defmacro with-open-files ((file-seq
&optional open-args (getter 'get-handle))
&body body)
(let ((failed? (gensym "failed?"))
(handle-seq (gensym "handle-seq")))
`(let ((,handle-seq (mapcar
(lambda (file-name)
(cons file-name (open file-name ,@open-args)))
,file-seq))
(,failed? t))
(flet ((,getter (file-name)
(cdr (assoc file-name ,handle-seq))))
(unwind-protect
(multiple-value-prog1
(progn ,@body)
(setq ,failed? nil))
(mapcar (lambda (handle)
(close (cdr handle) :abort ,failed?))
,handle-seq)))))))
1601 days ago | common-lisp |
Sorts and Partial Orderings
Yesterday, Kenny posted a interesting question on comp.lang.lisp. Essentially, the question comes down to the behavior of SORT when the predicate provided is only a partial ordering, rather than a complete ordering.
As a quick review, a total ordering is an operator O which is anti-symmetric (a O b -> NOT b O a), transitive (a O b and b O C -> a O C), and total (a O b OR b o a). An example is the > operator over the reals (multiple instances of a single number are “the same object”.) A partial ordering is still anti-symmetric and transitive, but may not be total. The classic example is the operator that checks for ancestry in a directed acyclic graph (DAG).
Kenny seemed to be experiencing a “bug” where he passed a partial ordering predicate to SORT, and the returned sequence didn’t respect the partial ordering—continuing the DAG analogy, there was an instance where A was ancestor of B but B occurred before A in the resulting sequence.
Is it a bug? Quoting the Hyperspec on SORT:
If the key and predicate always return, then the sorting operation will always terminate, producing a sequence containing the same elements as sequence (that is, the result is a permutation of sequence). This is guaranteed even if the predicate does not really consistently represent a total order (in which case the elements will be scrambled in some unpredictable way, but no element will be lost). If the key consistently returns meaningful keys, and the predicate does reflect some total ordering criterion on those keys, then the elements of the sorted-sequence will be properly sorted according to that ordering.We see that if we pass a predicate which doesn’t represent a total order, the only thing we’re guaranteed is that the returned sequence contains the same elements as the original. So the behavior Kenny’s seeing is “conformant.”
Is it a “bug” in the spec? Should SORT return sequences which respect partial orderings? I don’t think so. In the comparison model of sorting, the only thing the sorter can do is compare two elements of the sequence at once, and then shuffle elements around. Now imagine that we pass a partial order where the first element is bigger than the second, and the remaining elements are all incommensurate, with both each other and the first two elements. (As a graph, this is a single chain of length 2, and n-2 isolated nodes.) The only way we’re going to be able to guarantee we return a sequence that puts elements one and two in the right order is if we compare them, and to guarantee we compare them, we have to compare everything to everything else—O(n^2) comparisons.
A partial ordering is transitive over pairs on which its defined. But if we make a predicate that returns true if A is an ancestor of B, and false if B is an ancestor of A or they’re incommensurate, this predicate is not transitive. The O(n log n) sorting algorithms assume that the predicate is transitive, and the argument above shows that this will necessarily lead to wrong results for partial order predicates for at least some input sequences.
What’s the answer? In the comparison model, we’re basically screwed. If all we can do is compare two elements, it will take O(n^2) time to order a sequence to respect an arbitrary partial order. On the other hand, if our ordering is ancestors in a DAG, and we can enumerate the children of a node, we can sort into a partial order in O(n) time, using a topological sort. This is hopefully the answer to Kenny’s problem, although it’s not yet entirely clear.
1653 days ago | common-lisp | Comment