;;;; This is an implementation of the basic AQ algorithm for learning from
;;;; exmples which uses the version-space algorithm to compute stars. The 
;;;; file VERSION-SPACE must also be loaded with appropriate language
;;;; specification functions.

;;;; Copyright (c) 1988 by Raymond Joseph Mooney. This program may be freely 
;;;; copied, used, or modified provided that this copyright notice is included
;;;; in each copy of this code and parts thereof.

;;;; This version of AQ assumes that events are represented as ordered lists
;;;; of feature values. Complexes are assumed to also be represented in the
;;;; same manner where ? is used as a fetaure value if no restriction is made
;;;; on the value of this feature, i.e. it is not a selector in the complex.
;;;; The files FIGURE-DATA and WEATHER-DATA contain sample datasets.

(defparameter *trace-aq* nil) ; AQ produces a trace if this flag is set to T
                              ; One may also want to turn on *trace-vs*


(defun aq (examples)
  ;;; AQ takes a list of examples where an example is a list of either + or -
  ;;; (indicating the class) and an event description. It returns a cover
  ;;; (a list of complexes) which covers all of the postive events and none
  ;;; of the negative ones.

  (let ((pos-instances nil) (neg-instances nil)
	(cover nil)(seed nil)(best-complex nil)(delta 0))
    ;;; Separate instances into positive and negative ones
    (dolist (example examples)
      (cond ((eq (first example) '+)
	     (push (second example) pos-instances))
	    ((eq (first example) '-)
	     (push (second example) neg-instances))))
    ;; Use seeds which are not covered by any previous star until there
    ;; are no more such seeds.
    (do ((seed-instances pos-instances))
	((null seed-instances))
      (setf seed (pop seed-instances))      ; select a seed from available set
      (trace-print *trace-aq* "~%~%Seed: ~A" seed)
      ;; use version-space to generate a star covering this seed but none
      ;; of the negative examples
      (version-space (make-examples (list seed) neg-instances))
      ;; Pick the best complex in this star and put it in the cover
      (setf best-complex (select-complex *g* pos-instances))
      (trace-print *trace-aq* "~%Best complex: ~A" (format-generalization best-complex))
      (push best-complex cover)
      ;; Remove from the set of possible seeds those which are covered by any
      ;; complex in the star
      (setf seed-instances (remove-if #'(lambda (instance)
					 (dolist (complex *g*)
					   (when (match complex instance)
					     (return t))))
				      seed-instances))
      ;; Remove from the set of positive events those covered by the chosen
      ;; complex
      (setf pos-instances (remove-if #'(lambda (instance)
					 (match best-complex instance))
				     pos-instances)))
    ;; Pick seeds and generate stars until all + events are covered
    (do nil
	((null pos-instances))
      (setf seed (first pos-instances))
      (trace-print *trace-aq* "~%~%Seed: ~A" seed)
      (version-space (make-examples (list seed) neg-instances))
      (setf best-complex (select-complex *g* pos-instances))
      (trace-print *trace-aq* "~%Best complex: ~A" (format-generalization best-complex))
      (push best-complex cover)
      (setf pos-instances (remove-if #'(lambda (instance)
					 (match best-complex instance))
				     pos-instances))
      (incf delta))                 ; delta is an estimate of distance from
                                    ; the minimal # of complexes
    (trace-print *trace-aq* "~%~%Cover minimal within ~D complexes" delta)
    cover))


(defun select-complex (complexes pos-instances)
  ;;; From a set of complexes select that one which maximizes the number of
  ;;; positive examples covered and break ties by trying to minimize the
  ;;; number of selectors in the complex

  (let ((best-complex nil)(max-matches -1)(match-count 0))
    (trace-print *trace-aq* "~%")
    (dolist (complex complexes best-complex)
      (setf match-count 0)
      ;; Count the number of + events the complex covers
      (dolist (pos-instance pos-instances)
	(if (match complex pos-instance)
	    (incf match-count)))
      (trace-print *trace-aq* "~%~A matches ~D instance~:P"
		   (format-generalization complex) match-count)
      ;; if complex is better than current best complex then make it the new
      ;; best complex
      (when (or (> match-count max-matches)
		(and (= match-count max-matches)
		     (<= (count-selectors complex)
			(count-selectors best-complex))))
	(setf max-matches match-count)
	(setf best-complex complex)))))


(defun count-selectors (complex)
  ;;; Counts the number of selectors (i.e. non-?'s in the complex)

  (let ((selector-count 0))
    (dolist (feature complex selector-count)
      (unless (eq feature '?) (incf selector-count)))))