nips nips2007 nips2007-188 knowledge-graph by maker-knowledge-mining

188 nips-2007-Subspace-Based Face Recognition in Analog VLSI

Source: pdf

Author: Gonzalo Carvajal, Waldo Valenzuela, Miguel Figueroa

Abstract: We describe an analog-VLSI neural network for face recognition based on subspace methods. The system uses a dimensionality-reduction network whose coeﬃcients can be either programmed or learned on-chip to perform PCA, or programmed to perform LDA. A second network with userprogrammed coeﬃcients performs classiﬁcation with Manhattan distances. The system uses on-chip compensation techniques to reduce the eﬀects of device mismatch. Using the ORL database with 12x12-pixel images, our circuit achieves up to 85% classiﬁcation performance (98% of an equivalent software implementation). 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 cl Abstract We describe an analog-VLSI neural network for face recognition based on subspace methods. [sent-3, score-0.385]

2 The system uses a dimensionality-reduction network whose coeﬃcients can be either programmed or learned on-chip to perform PCA, or programmed to perform LDA. [sent-4, score-0.194]

3 The system uses on-chip compensation techniques to reduce the eﬀects of device mismatch. [sent-6, score-0.132]

4 Using the ORL database with 12x12-pixel images, our circuit achieves up to 85% classiﬁcation performance (98% of an equivalent software implementation). [sent-7, score-0.415]

5 However, most techniques for dimensionality reduction require a high computational throughput to transform images from the large input data space to the feature subspace. [sent-10, score-0.281]

6 Therefore, software [3] even dedicated digital hardware implementations [4, 5] are too large and power-hungry to be used in highly portable systems. [sent-11, score-0.394]

7 Traditional circuit-design techniques can reduce these eﬀects, but they increase power and area, rendering analog solutions less attractive. [sent-13, score-0.196]

8 In this paper, we present a neural network for face recognition which implements Principal Components Analysis (PCA) and Linear Discriminant Analysis (LDA) for dimensionality reduction, and Manhattan distances and a loser-take-all (LTA) circuit for classiﬁcation. [sent-14, score-0.669]

9 We can download the network weights in a chip-in-the loop conﬁguration, or use on-chip learning to compute PCA coeﬃcients. [sent-15, score-0.162]

10 We use local adaptation to achieve good classiﬁcation performance in the presence of device mismatch. [sent-16, score-0.174]

11 Using PCA reduction and a hard classiﬁer, our network achieves up to 83% accuracy on the Olivetti Research Labs (ORL) face database [6] using 12x12-pixel images, which corresponds to 99% of the accuracy of a software implementation of the algorithm. [sent-20, score-0.685]

12 Using LDA projections and a software Radial Basis Function (RBF) network on the hardware-computed distances yields 85% accuracy (98% of the software performance). [sent-21, score-0.558]

13 1 2 Eigenspace based face recognition methods The problem of face recognition consists of assigning an identity to an unknown face by comparing it to a database of labeled faces. [sent-22, score-0.678]

14 However, the dimensionality of the input images is usually so high that performing the classiﬁcation on the original data becomes prohibitively expensive. [sent-23, score-0.195]

15 In particular, the Eigenfaces [1] method performs dimensionality reduction using PCA, and classiﬁcation by choosing the stored face with the lowest distance to the input data. [sent-26, score-0.516]

16 , xN } represent a set of N images, such as the image database available for a face recognition task. [sent-32, score-0.353]

17 PCA computes a new matrix Ym×N , with m < n: Y = W*T X (1) The columns of Y are the lower-dimensional projections of the original images in the feature space. [sent-33, score-0.176]

18 Upon presentation of a new face image, the Eigenfaces method ﬁrst transforms this image into the feature space using the transformation matrix W∗ , and then computes the distance between the reduced image and each image class in the reference database. [sent-35, score-0.474]

19 Fisherfaces [2] performs dimensionality reduction using Linear Discriminant Analysis (LDA). [sent-37, score-0.179]

20 Fisherfaces can perform classiﬁcation using a hard classiﬁer on the computed distances between the test data and stored patterns in the LDA subspace, as in Eigenfaces, or it can use a Radial Basis Function (RBF) network. [sent-46, score-0.132]

21 However, our experiments show that, as long as the dimensionality reduction preserves enough distance between classes, less computationally expensive distance metrics such as Manhattan distance are equally eﬀective for classiﬁcation. [sent-49, score-0.35]

22 yn ] is given by: n |xi − yi | d= i=1 2 (4) distances 1 n test data y dimensionality reduction 2 . [sent-56, score-0.235]

23 input image x database m LTA face ID k (a) Architecture y1 . [sent-59, score-0.338]

24 + f1,i data f 2,i base _ abs () _ abs () + dist i . [sent-71, score-0.195]

25 xn ym _ fn,i Wn,m (b) Projection network abs () (c) Distance computation Figure 1: Face-recognition hardware. [sent-77, score-0.169]

26 A dimensionality-reduction network projects a n-dimensional image onto m dimensions, and loser-take-all (LTA) circuit labels the image by choosing the nearest stored face in the reduced space. [sent-79, score-0.648]

27 (b) The dimensionality reduction network is an array of linear combiners with weights that have been pre-computed or learned on chip. [sent-80, score-0.415]

28 (c) The distance circuit computes the Manhattan distance between the m projections of the test image and the stored face database. [sent-81, score-0.704]

29 It follows the signal ﬂow described in Section 2, where the n-dimensional test image x is ﬁrst projected onto the mdimensional feature space (test data y) using an array of m n-input analog linear combiners, shown in Fig. [sent-85, score-0.251]

30 The constant input c is a bias used to compensate for the oﬀset introduced by the analog multipliers. [sent-87, score-0.33]

31 The network also stores the m projections of the database face set (the training set) in an array of analog memories. [sent-88, score-0.628]

32 1(c), computes the Manhattan distance between each labeled element in the stored training set and the reduced test data y. [sent-90, score-0.178]

33 The linear combiners are based on the synapse shown in Fig. [sent-92, score-0.157]

34 An analog Gilbert multiplier computes the product of each pixel of the input image, represented as a diﬀerential voltage, and the local synaptic weight. [sent-94, score-0.401]

35 An accurate transformation requires a multiplier response that is linear in the pixel value, therefore we designed the multipliers to maximize the linearity of that input. [sent-95, score-0.286]

36 Device mismatch introduces oﬀsets and gain variance across different multipliers in the network; we describe the calibration techniques used to compensate for these eﬀects in Section 4. [sent-96, score-0.526]

37 The multipliers provide a diﬀerential current output, therefore we can add them across a single neuron by connecting them to common wires. [sent-97, score-0.169]

38 Each synaptic weight is stored in an analog nonvolatile memory cell [7] based on ﬂoatinggate transistors, shown also in Fig. [sent-98, score-0.414]

39 The cell features linear weight-updates based on digital pulses applied to the terminals inc and dec. [sent-100, score-0.191]

40 sum weight Iy- sum (a) Hardware synapse (b) Distance circuit Figure 2: (a) The synapse is comprised by a Gilbert multiplier and a nonvolatile analog memory cell with local calibration. [sent-102, score-0.802]

41 (b) Each component of the Manhattan distance is computed as the subtraction of the corresponding principal components and an optional inversion based on the sign of the result. [sent-104, score-0.162]

42 2(b) depicts the circuit used to compute the Manhattan distance between the test data and the stored patterns. [sent-110, score-0.314]

43 Each projection of the training set is stored as a current in an analog memory cell, simpler and smaller than the cell used in the dimensionality reduction network, and written using a self-limiting write process. [sent-111, score-0.6]

44 As stated in Section 5, our current implementation considers 12×12-pixel images (n = 144 in Fig. [sent-114, score-0.143]

45 The next section analyzes the eﬀects of device mismatch on the dimensionality-reduction network. [sent-117, score-0.303]

46 In order to achieve good performance, we must calibrate the network to compensate for the eﬀect of these limitations. [sent-119, score-0.248]

47 In both cases, we design mechanisms that use local on-chip adaptation to compensate for the oﬀsets and gain variances introduced by device mismatch, thus improving classiﬁcation performance. [sent-123, score-0.31]

48 Thus, our analysis uses a simpliﬁed model of the analog multipliers given by: o = (ax x + γx )(aw w + γw ) (5) where o is the multiplier output, x and w are the inputs, γx and γw represent the input oﬀsets, and ax and aw are the multiplier gains associated with each input. [sent-127, score-0.998]

49 These parameters vary across diﬀerent multipliers due to device mismatch and are unknown at design time, and diﬃcult to determine even after circuit fabrication. [sent-128, score-0.653]

50 1 Dimensionality reduction with precomputed weights Let us consider an analog linear combiner such as the one depicted in Fig. [sent-130, score-0.456]

51 1(b), which computes the ﬁrst projection y of x, using the ﬁrst column w∗ of the software precomputed optimal transformation W∗ of Eqn. [sent-131, score-0.283]

52 (5), the linear combiner computes the ﬁrst projection as: y = xT (Ax Aw w∗ + Ax γ w ) + γ T (Aw w∗ + γw ) (6) x where Ax = diag([ax1 . [sent-134, score-0.182]

53 (6) shows that device mismatch has two eﬀects on the output: the ﬁrst term modiﬁes the eﬀective weight value of the network, and the second term represents an oﬀset added to the output (w∗ is a constant). [sent-148, score-0.362]

54 Replacing w∗ with an adaptive version wk , the structure becomes a classic adaptive linear combiner which, using the optimal weights to generate a reference output signal, can be trained using the well known Least-Mean Squares (LMS) algorithm. [sent-149, score-0.394]

55 Adding a bias synapse b with constant input c and training the network with LMS, the weights converge to [7]: w∗ ∗ = (Ax Aw )−1 (w∗ − Ax γ w ) −(γ T (Aw w∗ x (7) −1 + γw ) + cγb )(cab ) (8) b = where ab and γb are the gain and oﬀset of the analog multiplier associated to the bias input c. [sent-150, score-0.689]

56 These weight values fully compensate for the eﬀects of gain mismatch and oﬀsets. [sent-151, score-0.307]

57 In our hardware implementation, we use m adaptive linear combiners to compute every projection in the feature space, and calibrate these circuits using on-chip LMS local adaptation to compute and store the optimal weight values of Eqns. [sent-152, score-0.381]

58 We train the weight values in the memory cells by providing inputs and a reference output to each linear combiner, and use an on-chip pulse-based compact implementation of the LMS learning rule. [sent-156, score-0.277]

59 Thus, the performance of the dimensionality reduction network is ultimately limited by the resolution of the memory cells, the reference noise, the learning rate of the LMS training stage and linearity of the multipliers. [sent-158, score-0.395]

60 To measure the accuracy of our implementation, we computed (in software) the ﬁrst 10 principal components of one half the Olivetti Research Labs (ORL) face database, reduced to 12x12 pixels, and used our on-chip implementation of LMS to train the hardware network to learn the coeﬃcients. [sent-160, score-0.612]

61 We then measured the output of the circuit on the other half of the database. [sent-161, score-0.24]

62 3(b) plots the RMS value of the error between the circuit output and the software results, normalized to the RMS value of each principal component. [sent-163, score-0.5]

63 The ﬁgure also shows the error when we wrote the coeﬃcients onto the circuit in open-loop, without using LMS. [sent-164, score-0.181]

64 In this case, oﬀset and gain mismatch completely obscure the information present in the signal. [sent-165, score-0.216]

65 2 On-chip PCA computation In some cases, such as when the face-recognition network is integrated with a camera on a single chip, it may be necessary to train the face database on-chip. [sent-170, score-0.36]

66 It is not practical for the chip to include the hardware resources to compute the optimal weights from the eigenvalue analysis of the training set’s covariance matrix, therefore we compute them on chip using the standard Generalized Hebbian Algorithm (GHA). [sent-171, score-0.382]

67 The computation of the ﬁrst principal component and the learning rule to update the weights at time k are: yk = xT wk (9) k ∆wk = µyk (xk − x k ) (10) x k = yk wk (11) 5 Norm. [sent-172, score-0.606]

68 A pulse-based implementation of the LMS learning rule updates the memory cells. [sent-176, score-0.169]

69 where µ is the learning rate of the algorithm and x k is the reconstruction of the input xk from the ﬁrst principal component. [sent-178, score-0.187]

70 The distortion introduced to the output by gain mismatch and oﬀsets in Eqn. [sent-179, score-0.275]

71 Similarly to LMS, it is easy to show that a bias input c connected to a synapse b with an anti-Hebbian learning rule ∆bk = µb cyk removes the constant oﬀset added to the output. [sent-182, score-0.161]

72 (7) and (8), which compensate for the eﬀects of gain mismatch and oﬀset. [sent-194, score-0.307]

73 Note that this will only be the case if we use the same hardware multipliers to compute yk and x k . [sent-196, score-0.369]

74 The multiplexer shares the analog multipliers between the computation of yk and x k , and is controlled by a digital signal that alternates its value during the computation and adaptation phases of the algorithm. [sent-200, score-0.52]

75 4(b) shows the normalized RMS value of the output error for the ﬁrst 10 principal components. [sent-203, score-0.164]

76 However, as Section 5 shows, this error does not translate into a large degradation in the face classiﬁcation performance. [sent-207, score-0.161]

77 (a) We reuse the multiplier to compute x k and use a pulse-based implementation of the GHA rule. [sent-210, score-0.201]

78 35µm CMOS process, including analog memory cells, multipliers, and weight-update rules for LMS and GHA. [sent-213, score-0.246]

79 We characterized these circuits in the lab and built a software emulator that allows us to test the static performance of diﬀerent network conﬁgurations with less than 0. [sent-214, score-0.373]

80 Using the emulator, we tested the performance of the face-recognition network on the Olivetti Research Labs (ORL) database, consisting on 10 photos of each of 40 total subjects. [sent-217, score-0.157]

81 Limitations in our circuit emulator forced us to reduce the images to 12 × 12 pixels. [sent-219, score-0.296]

82 The estimated power consumption of the circuit with these 144 inputs and 39 projections is 18mW (540nJ per classiﬁcation with 30µs settling time), and the layout area is 2. [sent-220, score-0.291]

83 These numbers represent a 2–5x reduction in area and more than 100x reduction in power compated to standard cell-based digital implementations [4, 5]. [sent-222, score-0.269]

84 5(a) shows the classiﬁcation performance of the network using PCA for dimensionality reduction, versus the number of principal components in the subspace. [sent-224, score-0.318]

85 First, we tested the network using PCA for dimensionality reduction. [sent-225, score-0.213]

86 The ﬁgure shows the performance of a software implementation of PCA with Euclidean distances, hardware PCA trained with LMS and software-computed weights, and hardware PCA trained with on-chip GHA. [sent-226, score-0.523]

87 Both hardware implementations use Manhattan distances and a software LTA. [sent-227, score-0.395]

88 The software implementation peaks at 84% classiﬁcation accuracy, while the hardware LMS and GHA implementations peak at 83% and 79%, respectively. [sent-230, score-0.423]

89 Using an uncalibrated network brings the performance below 5%, mainly due to the oﬀsets in the multipliers which change the PCA projection and take the signals outside of their nominal operating range. [sent-233, score-0.333]

90 5(a) shows the classiﬁcation results using the LDA in the dimensionality reduction network. [sent-235, score-0.179]

91 The performance of the software implementation of LDA and an a hard-classiﬁer based on Euclidean distances is 83%. [sent-237, score-0.295]

92 The LMS-trained hardware network with Manhattan distances and a software LTA yields 82%. [sent-238, score-0.473]

93 Replacing the LTA with a software RBF classiﬁer, the chip achieves 85% classiﬁcation performance, while the software implementation (not shown) peaks at 87%. [sent-239, score-0.493]

94 Using 40x40-pixel images and 39 projections, the software LDA network with RBF achieves more than 98% classiﬁcation accuracy. [sent-240, score-0.334]

95 This represents 98%-99% of the performance of a software implementation. [sent-252, score-0.155]

96 6 Conclusions We presented an analog-VLSI network for face-recognition using subspace methods. [sent-253, score-0.166]

97 We analyzed the eﬀects of device mismatch on the performance of the dimensionality-reduction network and tested two techniques based on local adaptation which compensate for gain mismatch and oﬀsets. [sent-254, score-0.772]

98 We showed that using LMS to train the network on precomputed coeﬃcients to perform PCA or LDA performs better than using GHA to learn PCA coeﬃcients on chip. [sent-255, score-0.159]

99 Ultimately, both techniques perform similarly in the face-classiﬁcation task with the ORL database, achieving a classiﬁcation performance of 83%-85% (98%-99% of a software implementation of the algorithms). [sent-256, score-0.239]

100 A DSP-Based approach for the implementation of face recognition algorithms. [sent-282, score-0.303]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('lms', 0.34), ('lda', 0.208), ('pca', 0.208), ('aw', 0.207), ('gha', 0.205), ('analog', 0.196), ('lta', 0.186), ('manhattan', 0.186), ('circuit', 0.181), ('mismatch', 0.171), ('multipliers', 0.169), ('face', 0.161), ('software', 0.155), ('wk', 0.154), ('hardware', 0.142), ('device', 0.132), ('network', 0.12), ('multiplier', 0.117), ('ax', 0.11), ('coe', 0.107), ('principal', 0.105), ('chip', 0.099), ('dist', 0.097), ('dimensionality', 0.093), ('combiner', 0.093), ('rms', 0.093), ('compensate', 0.091), ('sw', 0.089), ('reduction', 0.086), ('implementation', 0.084), ('synapse', 0.083), ('ay', 0.083), ('orl', 0.083), ('classi', 0.083), ('inc', 0.081), ('database', 0.079), ('stored', 0.076), ('combiners', 0.074), ('fisherfaces', 0.074), ('eigenfaces', 0.074), ('projections', 0.072), ('ects', 0.067), ('rbf', 0.066), ('di', 0.065), ('vlsi', 0.062), ('images', 0.059), ('hw', 0.059), ('output', 0.059), ('yk', 0.058), ('recognition', 0.058), ('distance', 0.057), ('distances', 0.056), ('emulator', 0.056), ('olivetti', 0.056), ('cell', 0.055), ('erent', 0.055), ('digital', 0.055), ('image', 0.055), ('dec', 0.052), ('memory', 0.05), ('calibration', 0.05), ('gilbert', 0.049), ('abs', 0.049), ('subspace', 0.046), ('reference', 0.046), ('computes', 0.045), ('gain', 0.045), ('cmos', 0.044), ('projection', 0.044), ('input', 0.043), ('circuits', 0.042), ('implementations', 0.042), ('weights', 0.042), ('adaptation', 0.042), ('ective', 0.041), ('ni', 0.041), ('mi', 0.041), ('cation', 0.041), ('precomputed', 0.039), ('xk', 0.039), ('gains', 0.039), ('inputs', 0.038), ('adder', 0.037), ('calibrate', 0.037), ('carvajal', 0.037), ('concepci', 0.037), ('crossbar', 0.037), ('figueroa', 0.037), ('gonzalo', 0.037), ('iabs', 0.037), ('nonvolatile', 0.037), ('photos', 0.037), ('programmed', 0.037), ('sb', 0.037), ('cients', 0.037), ('labs', 0.036), ('rule', 0.035), ('seth', 0.032), ('arithmetic', 0.032), ('die', 0.032)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999917 188 nips-2007-Subspace-Based Face Recognition in Analog VLSI

Author: Gonzalo Carvajal, Waldo Valenzuela, Miguel Figueroa

2 0.13820478 73 nips-2007-Distributed Inference for Latent Dirichlet Allocation

Author: David Newman, Padhraic Smyth, Max Welling, Arthur U. Asuncion

Abstract: We investigate the problem of learning a widely-used latent-variable model – the Latent Dirichlet Allocation (LDA) or “topic” model – using distributed computation, where each of processors only sees of the total data set. We propose two distributed inference schemes that are motivated from different perspectives. The ﬁrst scheme uses local Gibbs sampling on each processor with periodic updates—it is simple to implement and can be viewed as an approximation to a single processor implementation of Gibbs sampling. The second scheme relies on a hierarchical Bayesian extension of the standard LDA model to directly account for the fact that data are distributed across processors—it has a theoretical guarantee of convergence but is more complex to implement than the approximate method. Using ﬁve real-world text corpora we show that distributed learning works very well for LDA models, i.e., perplexity and precision-recall scores for distributed learning are indistinguishable from those obtained with single-processor learning. Our extensive experimental results include large-scale distributed computation on 1000 virtual processors; and speedup experiments of learning topics in a 100-million word corpus using 16 processors. ¢ ¤ ¦¥£ ¢ ¢

3 0.12658283 117 nips-2007-Learning to classify complex patterns using a VLSI network of spiking neurons

Author: Srinjoy Mitra, Giacomo Indiveri, Stefano Fusi

Abstract: We propose a compact, low power VLSI network of spiking neurons which can learn to classify complex patterns of mean ﬁring rates on–line and in real–time. The network of integrate-and-ﬁre neurons is connected by bistable synapses that can change their weight using a local spike–based plasticity mechanism. Learning is supervised by a teacher which provides an extra input to the output neurons during training. The synaptic weights are updated only if the current generated by the plastic synapses does not match the output desired by the teacher (as in the perceptron learning rule). We present experimental results that demonstrate how this VLSI network is able to robustly classify uncorrelated linearly separable spatial patterns of mean ﬁring rates.

4 0.09997955 183 nips-2007-Spatial Latent Dirichlet Allocation

Author: Xiaogang Wang, Eric Grimson

Abstract: In recent years, the language model Latent Dirichlet Allocation (LDA), which clusters co-occurring words into topics, has been widely applied in the computer vision ﬁeld. However, many of these applications have difﬁculty with modeling the spatial and temporal structure among visual words, since LDA assumes that a document is a “bag-of-words”. It is also critical to properly design “words” and “documents” when using a language model to solve vision problems. In this paper, we propose a topic model Spatial Latent Dirichlet Allocation (SLDA), which better encodes spatial structures among visual words that are essential for solving many vision problems. The spatial information is not encoded in the values of visual words but in the design of documents. Instead of knowing the partition of words into documents a priori, the word-document assignment becomes a random hidden variable in SLDA. There is a generative procedure, where knowledge of spatial structure can be ﬂexibly added as a prior, grouping visual words which are close in space into the same document. We use SLDA to discover objects from a collection of images, and show it achieves better performance than LDA. 1

5 0.092307344 18 nips-2007-A probabilistic model for generating realistic lip movements from speech

Author: Gwenn Englebienne, Tim Cootes, Magnus Rattray

Abstract: The present work aims to model the correspondence between facial motion and speech. The face and sound are modelled separately, with phonemes being the link between both. We propose a sequential model and evaluate its suitability for the generation of the facial animation from a sequence of phonemes, which we obtain from speech. We evaluate the results both by computing the error between generated sequences and real video, as well as with a rigorous double-blind test with human subjects. Experiments show that our model compares favourably to other existing methods and that the sequences generated are comparable to real video sequences. 1

6 0.08850643 177 nips-2007-Simplified Rules and Theoretical Analysis for Information Bottleneck Optimization and PCA with Spiking Neurons

7 0.086619459 116 nips-2007-Learning the structure of manifolds using random projections

8 0.084416091 161 nips-2007-Random Projections for Manifold Learning

9 0.084224083 14 nips-2007-A configurable analog VLSI neural network with spiking neurons and self-regulating plastic synapses

10 0.080249064 155 nips-2007-Predicting human gaze using low-level saliency combined with face detection

11 0.076762989 109 nips-2007-Kernels on Attributed Pointsets with Applications

12 0.072343558 106 nips-2007-Invariant Common Spatial Patterns: Alleviating Nonstationarities in Brain-Computer Interfacing

13 0.070105642 193 nips-2007-The Distribution Family of Similarity Distances

14 0.069125995 189 nips-2007-Supervised Topic Models

15 0.066459268 115 nips-2007-Learning the 2-D Topology of Images

16 0.060402766 60 nips-2007-Contraction Properties of VLSI Cooperative Competitive Neural Networks of Spiking Neurons

17 0.058144066 137 nips-2007-Multiple-Instance Pruning For Learning Efficient Cascade Detectors

18 0.057655722 129 nips-2007-Mining Internet-Scale Software Repositories

19 0.056733787 70 nips-2007-Discriminative K-means for Clustering

20 0.053033523 111 nips-2007-Learning Horizontal Connections in a Sparse Coding Model of Natural Images

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.188), (1, 0.096), (2, 0.043), (3, -0.062), (4, 0.021), (5, 0.061), (6, 0.107), (7, 0.066), (8, 0.012), (9, 0.144), (10, -0.013), (11, 0.085), (12, -0.078), (13, 0.109), (14, -0.043), (15, 0.028), (16, -0.025), (17, -0.15), (18, -0.11), (19, -0.106), (20, 0.082), (21, 0.034), (22, -0.03), (23, 0.036), (24, -0.029), (25, -0.045), (26, -0.039), (27, 0.045), (28, -0.042), (29, -0.02), (30, -0.07), (31, -0.051), (32, 0.03), (33, 0.001), (34, -0.055), (35, 0.043), (36, 0.058), (37, -0.13), (38, -0.105), (39, 0.014), (40, 0.0), (41, -0.012), (42, 0.111), (43, -0.015), (44, 0.113), (45, -0.113), (46, 0.033), (47, 0.116), (48, -0.016), (49, -0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94969553 188 nips-2007-Subspace-Based Face Recognition in Analog VLSI

Author: Gonzalo Carvajal, Waldo Valenzuela, Miguel Figueroa

2 0.50141138 73 nips-2007-Distributed Inference for Latent Dirichlet Allocation

Author: David Newman, Padhraic Smyth, Max Welling, Arthur U. Asuncion

3 0.50062066 18 nips-2007-A probabilistic model for generating realistic lip movements from speech

Author: Gwenn Englebienne, Tim Cootes, Magnus Rattray

4 0.47736874 117 nips-2007-Learning to classify complex patterns using a VLSI network of spiking neurons

Author: Srinjoy Mitra, Giacomo Indiveri, Stefano Fusi

5 0.46946812 109 nips-2007-Kernels on Attributed Pointsets with Applications

Author: Mehul Parsana, Sourangshu Bhattacharya, Chiru Bhattacharya, K. Ramakrishnan

Abstract: This paper introduces kernels on attributed pointsets, which are sets of vectors embedded in an euclidean space. The embedding gives the notion of neighborhood, which is used to deﬁne positive semideﬁnite kernels on pointsets. Two novel kernels on neighborhoods are proposed, one evaluating the attribute similarity and the other evaluating shape similarity. Shape similarity function is motivated from spectral graph matching techniques. The kernels are tested on three real life applications: face recognition, photo album tagging, and shot annotation in video sequences, with encouraging results. 1

6 0.46198592 45 nips-2007-Classification via Minimum Incremental Coding Length (MICL)

7 0.42515409 152 nips-2007-Parallelizing Support Vector Machines on Distributed Computers

8 0.42004454 14 nips-2007-A configurable analog VLSI neural network with spiking neurons and self-regulating plastic synapses

9 0.40567583 209 nips-2007-Ultrafast Monte Carlo for Statistical Summations

10 0.40501872 183 nips-2007-Spatial Latent Dirichlet Allocation

11 0.37800464 60 nips-2007-Contraction Properties of VLSI Cooperative Competitive Neural Networks of Spiking Neurons

12 0.37364706 177 nips-2007-Simplified Rules and Theoretical Analysis for Information Bottleneck Optimization and PCA with Spiking Neurons

13 0.37320176 137 nips-2007-Multiple-Instance Pruning For Learning Efficient Cascade Detectors

14 0.37174213 116 nips-2007-Learning the structure of manifolds using random projections

15 0.36416939 115 nips-2007-Learning the 2-D Topology of Images

16 0.35812753 210 nips-2007-Unconstrained On-line Handwriting Recognition with Recurrent Neural Networks

17 0.3537862 16 nips-2007-A learning framework for nearest neighbor search

18 0.34967071 189 nips-2007-Supervised Topic Models

19 0.33940268 139 nips-2007-Nearest-Neighbor-Based Active Learning for Rare Category Detection

20 0.33931601 161 nips-2007-Random Projections for Manifold Learning

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(5, 0.02), (13, 0.025), (16, 0.024), (19, 0.025), (21, 0.036), (34, 0.024), (35, 0.014), (47, 0.58), (83, 0.091), (86, 0.013), (87, 0.027), (90, 0.028)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97357756 114 nips-2007-Learning and using relational theories

Author: Charles Kemp, Noah Goodman, Joshua B. Tenenbaum

Abstract: Much of human knowledge is organized into sophisticated systems that are often called intuitive theories. We propose that intuitive theories are mentally represented in a logical language, and that the subjective complexity of a theory is determined by the length of its representation in this language. This complexity measure helps to explain how theories are learned from relational data, and how they support inductive inferences about unobserved relations. We describe two experiments that test our approach, and show that it provides a better account of human learning and reasoning than an approach developed by Goodman [1]. What is a theory, and what makes one theory better than another? Questions like these are of obvious interest to philosophers of science but are also discussed by psychologists, who have argued that everyday knowledge is organized into rich and complex systems that are similar in many respects to scientiﬁc theories. Even young children, for instance, have systematic beliefs about domains including folk physics, folk biology, and folk psychology [2]. Intuitive theories like these play many of the same roles as scientiﬁc theories: in particular, both kinds of theories are used to explain and encode observations of the world, and to predict future observations. This paper explores the nature, use and acquisition of simple theories. Consider, for instance, an anthropologist who has just begun to study the social structure of a remote tribe, and observes that certain words are used to indicate relationships between selected pairs of individuals. Suppose that term T1(·, ·) can be glossed as ancestor(·, ·), and that T2(·, ·) can be glossed as friend(·, ·). The anthropologist might discover that the ﬁrst term is transitive, and that the second term is symmetric with a few exceptions. Suppose that term T3(·, ·) can be glossed as defers to(·, ·), and that the tribe divides into two castes such that members of the second caste defer to members of the ﬁrst caste. In this case the anthropologist might discover two latent concepts (caste 1(·) and caste 2(·)) along with the relationship between these concepts. As these examples suggest, a theory can be deﬁned as a system of laws and concepts that specify the relationships between the elements in some domain [2]. We will consider how these theories are learned, how they are used to encode relational data, and how they support predictions about unobserved relations. Our approach to all three problems relies on the notion of subjective complexity. We propose that theory learners prefer simple theories, that people remember relational data in terms of the simplest underlying theory, and that people extend a partially observed data set according to the simplest theory that is consistent with their observations. There is no guarantee that a single measure of subjective complexity can do all of the work that we require [3]. This paper, however, explores the strong hypothesis that a single measure will sufﬁce. Our formal treatment of subjective complexity begins with the question of how theories are mentally represented. We suggest that theories are represented in some logical language, and propose a speciﬁc ﬁrst-order language that serves as a hypothesis about the “language of thought.” We then pursue the idea that the subjective complexity of a theory corresponds to the length of its representation in this language. Our approach therefore builds on the work of Feldman [4], and is related to other psychological applications of the notion of Kolmogorov complexity [5]. The complexity measure we describe can be used to deﬁne a probability distribution over a space of theories, and we develop a model of theory acquisition by using this distribution as the prior for a Bayesian learner. We also 1 (a) Star 11 (b) Bipartite (c) Exception 22 33 44 55 66 77 88 16 26 36 46 56 21 31 41 51 61 71 81 11 17 27 37 47 57 18 28 38 48 58 R(X, X). T(6). T(7). T(8). R(X, Y) ← ¯(X), T(Y). T R(X, 1). (d) Symmetric (e) Transitive 11 22 33 44 55 66 77 13 31 12 21 24 42 56 65 26 36 46 56 17 27 37 47 57 18 28 38 48 58 T(6). T(7). T(8). R(X, Y) ← ¯(X), T(Y). T ¯ R(1, 1). R(1, 6). (f) Random 12 21 13 23 14 24 34 13 32 14 24 34 15 25 35 45 16 26 36 46 56 51 52 35 54 61 26 63 46 56 R(1, 2). R(1, 3). R(2, 4). R(5, 6). R(1, 2). R(2, 3). R(3, 4). R(5, X). R(X, 4). R(X, Y) ← R(Y, X). R(X, X). R(4, 5). R(5, 6). R(X, Z) ← R(X, Y), R(Y, Z). R(2, 1). R(1, 3). R(6, 1). R(3, 2). R(2, 6). R(3, 5). R(6, 3). R(4, 6). ¯ ¯ ¯ R(X, X). R(6, 4). R(5, 3). Figure 1: Six possible extensions for a binary predicate R(·, ·). In each case, the objects in the domain are represented as digits, and a pair such as 16 indicates that R(1, 6) is true. Below each set of pairs, the simplest theory according to our complexity measure is shown. show how the same Bayesian approach helps to explain how theories support inductive generalization: given a set of observations, future observations (e.g. whether one individual defers to another) can be predicted using the posterior distribution over the space of theories. We test our approach by developing two experiments where people learn and make predictions about binary and ternary relations. As far as we know, the approach of Goodman [1] is the only other measure of theory complexity that has previously been tested as a psychological model [6]. We show that our experiments support our approach and raise challenges for this alternative model. 1 Theory complexity: a representation length approach Intuitive theories correspond to mental representations of some sort, and our ﬁrst task is to characterize the elements used to build these representations. We explore the idea that a theory is a system of statements in a logical language, and six examples are shown in Fig. 1. The theory in Fig. 1b is related to the defers to(·, ·) example already described. Here we are interested in a domain including 9 elements, and a two place predicate R(·, ·) that is true of all and only the 15 pairs shown. R is deﬁned using a unary predicate T which is true of only three elements: 6, 7, and 8. The theory includes a clause which states that R(X, Y) is true for all pairs XY such that T(X) is false and T(Y) is true. The theory in Fig. 1c is very similar, but includes an additional clause which speciﬁes that R(1, 1) is true, and an exception which speciﬁes that R(1, 6) is false. Formally, each theory we consider is a collection of function-free deﬁnite clauses. All variables are universally quantiﬁed: for instance, the clause R(X, Z) ← R(X, Y), R(Y, Z) is equivalent to the logical formula ∀x ∀y ∀z (R(x, z) ← R(x, y) ∧ R(y, z)). For readability, the theories in Fig. 1 include parentheses and arrows, but note that these symbols are unnecessary and can be removed. Our proposed language includes only predicate symbols, variable symbols, constant symbols, and a period that indicates when one clause ﬁnishes and another begins. Each theory in Fig. 1 speciﬁes the extension of one or more predicates. The extension of predicate P is deﬁned in terms of predicate P+ (which captures the basic rules that lead to membership in P) and predicate P− (which captures exceptions to these rules). The resulting extension of P is deﬁned 2 as P+ \ P− , or the set difference of P+ and P− .1 Once P has been deﬁned, later clauses in the theory may refer to P or its negation ¯. To ensure that our semantics is well-deﬁned, the predicates P in any valid theory must permit an ordering so that the deﬁnition of any predicate does not refer to predicates that follow it in the order. Formally, the deﬁnition of each predicate P+ or P− can refer only to itself (recursive deﬁnitions are allowed) and to any predicate M or ¯ where M < P. M Once we have committed to a speciﬁc language, the subjective complexity of a theory is assumed to correspond to the number of symbols in its representation. We have chosen a language where there is one symbol for each position in a theory where a predicate, variable or constant appears, and one symbol to indicate when each clause ends. Given this language, the subjective complexity c(T ) of theory T is equal to the sum of the number of clauses in the theory and the number of positions in the theory where a predicate, variable or constant appears: c(T ) = #clauses(T ) + #pred slots(T ) + #var slots(T ) + #const slots(T ). (1) For instance, the clause R(X, Z) ← R(X, Y), R(Y, Z). contributes ten symbols towards the complexity of a theory (three predicate symbols, six variable symbols, and one period). Other languages might be considered: for instance, we could use a language which uses ﬁve symbols (e.g. ﬁve bits) to represent each predicate, variable and constant, and one symbol (e.g. one bit) to indicate the end of a clause. Our approach to subjective complexity depends critically on the representation language, but once a language has been chosen the complexity measure is uniquely speciﬁed. Although our approach is closely related to the notion of Kolmogorov complexity and to Minimum Message Length (MML) and Minimum Description Length (MDL) approaches, we refer to it as a Representation Length (RL) approach. A RL approach includes a commitment to a speciﬁc language that is proposed as a psychological hypothesis, but these other approaches aspire towards results that do not depend on the language chosen.2 It is sometimes suggested that the notion of Kolmogorov complexity provides a more suitable framework for psychological research than the RL approach, precisely because it allows for results that do not depend on a speciﬁc description language [8]. We subscribe to the opposite view. Mental representations presumably rely on some particular language, and identifying this language is a central challenge for psychological research. The language we described should be considered as a tentative approximation of the language of thought. Other languages can and should be explored, but our language has several appealing properties. Feldman [4] has argued that deﬁnite clauses are psychologically natural, and working with these representations allows our approach to account for several classic results from the concept learning literature. For instance, our language leads to the prediction that conjunctive concepts are easier to learn than disjunctive concepts [9].3 Working with deﬁnite clauses also ensures that each of our theories has a unique minimal model, which means that the extension of a theory can be deﬁned in a particularly simple way. Finally, human learners deal gracefully with noise and exceptions, and our language provides a simple way to handle exceptions. Any concrete proposal about the language of thought should make predictions about memory, learning and reasoning. Suppose that data set D lists the extensions of one or more predicates, and that a theory is a “candidate theory” for D if it correctly deﬁnes the extensions of all predicates in D. Note that a candidate theory may well include latent predicates—predicates that do not appear in D, but are useful for deﬁning the predicates that have been observed. We will assume that humans encode D in terms of the simplest candidate theory for D, and that the difﬁculty of memorizing D is determined by the subjective complexity of this theory. Our approach can and should be tested against classic results from the memory literature. Unlike some other approaches to complexity [10], for instance, our model predicts that a sequence of k items is about equally easy to remember regardless of whether the items are drawn from a set of size 2, a set of size 10, or a set of size 1000 [11]. 1 The extension of P+ is the smallest set that satisﬁes all of the clauses that deﬁne P+ , and the extension of P is deﬁned similarly. To simplify our notation, Fig. 1 uses P to refer to both P and P+ , and ¯ to refer to ¯ and P P P− . Any instance of P that appears in a clause deﬁning P is really an instance of P+ , and any instance of ¯ that P appears in a clause deﬁning ¯ is really an instance of P− . P 2 MDL approaches also commit to a speciﬁc language, but this language is often intended to be as general as possible. See, for instance, the discussion of universal codes in Gr¨ nwald et al. [7]. u 3 A conjunctive concept C(·) can be deﬁned using a single clause: C(X) ← A(X), B(X). The shortest deﬁnition of a disjunctive concept requires two clauses: D(X) ← A(X). D(X) ← B(X). − 3 To develop a model of inductive learning and reasoning, we take a Bayesian approach, and use our complexity measure to deﬁne a prior distribution over a hypothesis space of theories: P (T ) ∝ 2−c(T ) .4 Given this prior distribution, we can use Bayesian inference to make predictions about unobserved relations and to discover the theory T that best accounts for the observations in data set D [12, 13]. Suppose that we have a likelihood function P (D|T ) which speciﬁes how the examples in D were generated from some underlying theory T . The best explanation for the data D is the theory that maximizes the posterior distribution P (T |D) ∝ P (D|T )P (T ). If we need to predict whether ground term g is likely to be true, 5 we can sum over the space of theories: P (g|D) = P (g|T )P (T |D) = T 1 P (D) P (D|T )P (T ) (2) T :g∈T where the ﬁnal sum is over all theories T that make ground term g true. 1.1 Related work The theories we consider are closely related to logic programs, and methods for Inductive Logic Programming (ILP) explore how these programs can be learned from examples [14]. ILP algorithms are often inspired by the idea of searching for the shortest theory that accounts for the available data, and ILP is occasionally cast as the problem of minimizing an explicit MDL criterion [10]. Although ILP algorithms are rarely considered as cognitive models, the RL approach has a long psychological history, and is proposed by Chomsky [15] and Leeuwenberg [16] among others. Formal measures of complexity have been developed in many ﬁelds [17], and there is at least one other psychological account of theory complexity. Goodman [1] developed a complexity measure that was originally a philosophical proposal about scientiﬁc theories, but was later tested as a model of subjective complexity [6]. A detailed description of this measure is not possible here, but we attempt to give a ﬂavor of the approach. Suppose that a basis is a set of predicates. The starting point for Goodman’s model is the intuition that basis B1 is at least as complex as basis B2 if B1 can be used to deﬁne B2. Goodman argues that this intuition is ﬂawed, but his model is founded on a reﬁnement of this intuition. For instance, since the binary predicate in Fig. 1b can be deﬁned in terms of two unary predicates, Goodman’s approach requires that the complexity of the binary predicate is no more than the sum of the complexities of the two unary predicates. We will use Goodman’s model as a baseline for evaluating our own approach, and a comparison between these two models should be informed by both theoretical and empirical considerations. On the theoretical side, our approach relies on a simple principle for deciding which structural properties are relevant to the measurement of complexity: the relevant properties are those with short logical representations. Goodman’s approach incorporates no such principle, and he proposes somewhat arbitrarily that reﬂexivity and symmetry are among the relevant structural properties but that transitivity is not. A second reason for preferring our model is that it makes contact with a general principle—the idea that simplicity is related to representation length—that has found many applications across psychology, machine learning, and philosophy. 2 Experimental results We designed two experiments to explore settings where people learn, remember, and make inductive inferences about relational data. Although theories often consist of systems of many interlocking relations, we keep our experiments simple by asking subjects to learn and reason about a single relation at a time. Despite this restriction, our experiments still make contact with several issues raised by systems of relations. As the defers to(·, ·) example suggests, a single relation may be best explained as the observable tip of a system involving several latent predicates (e.g. caste 1(·) and caste 2(·)). 4 To ensure that this distribution can be normalized, we assume that there is some upper bound on the number of predicate symbols, variable symbols, and constants, and on the length of the theories we will consider. There will therefore be a ﬁnite number of possible theories, and our prior will be a valid probability distribution. 5 A ground term is a term such as R(8, 9) that does not include any variables. 4 Learning time Complexity (RL) Complexity (Human) 6 300 Complexity (Goodman) 4 20 0 0 0 star bprt excp sym trans rand 2 0 star bprt excp sym trans rand 2 star bprt excp sym trans rand 100 200 star bprt excp sym trans rand 4 40 Figure 2: (a) Average time in seconds to learn the six sets in Fig. 1. (b) Average ratings of set complexity. (c) Complexity scores according to our representation length (RL) model. (d) Complexity scores according to Goodman’s model. 2.1 Experiment 1: memory and induction In our ﬁrst experiment, we studied the subjective complexity of six binary relations that display a range of structural properties, including reﬂexivity, symmetry, and transitivity. Materials and Methods. 18 adults participated in this experiment. Subjects were required to learn the 6 sets shown in Fig. 1, and to make inductive inferences about each set. Although Fig. 1 shows pairs of digits, the experiment used letter pairs, and the letters for each condition and the order in which these conditions were presented were randomized across subjects. The pairs for each condition were initially laid out randomly on screen, and subjects could drag them around and organize them to help them understand the structure of the set. At any stage, subjects could enter a test phase where they were asked to list the 15 pairs belonging to the current set. Subjects who made an error on the test were returned to the learning phase. After 9 minutes had elapsed, subjects were allowed to pass the test regardless of how many errors they made. After passing the test, subjects were asked to rate the complexity of the set compared to other sets with 15 pairs. Ratings were provided on a 7 point scale. Subjects were then asked to imagine that a new letter (e.g. letter 9) had belonged to the current alphabet, and were given two inductive tasks. First they were asked to enter between 1 and 10 novel pairs that they might have expected to see (each novel pair was required to include the new letter). Next they were told about a novel pair that belonged to the set (e.g. pair 91), and were again asked to enter up to 10 additional pairs that they might have expected to see. Results. The average time needed to learn each set is shown in Fig. 2a, and ratings of set complexity are shown in Fig. 2b. It is encouraging that these measures yield converging results, but they may be confounded since subjects rated the complexity of a set immediately after learning it. The complexities plotted in Fig. 2c are the complexities of the theories shown in Fig. 1, which we believe to be the simplest theories according to our complexity measure. The ﬁnal plot in Fig. 2 shows complexities according to Goodman’s model, which assigns each binary relation an integer between 0 and 4. There are several differences between these models: for instance, Goodman’s account incorrectly predicts that the exception case is the hardest of the six, but our model acknowledges that a simple theory remains simple if a handful of exceptions are added. Goodman’s account also predicts that transitivity is not an important structural regularity, but our model correctly predicts that the transitive set is simpler than the same set with some of the pairs reversed (the random set). Results for the inductive task are shown in Fig. 3. The ﬁrst two columns show the number of subjects who listed each novel pair. The remaining two columns show the probability of set membership predicted by our model. To generate these predictions, we applied Equation 2 and summed over a set of theories created by systematically extending the theories shown in Fig. 1. Each extended theory includes up to one additional clause for each predicate in the base theory, and each additional clause includes at most two predicate slots. For instance, each extended theory for the bipartite case is created by choosing whether or not to add the clause T(9), and adding up to one clause for predicate R.6 For the ﬁrst inductive task, the likelihood term P (D|T ) (see Equation 2) is set to 0 for all theories that are not consistent with the pairs observed during training, and to a constant for all remaining theories. For the second task we assumed in addition that the novel pair observed is 6 R(9, X), ¯(2, 9), and R(X, 9) ← R(X, 2) are three possible additions. R 5 18 9 9 0.5 trans symm excep bipart 0 91 random r=0.99 1 star 18 99 19 0 91 89 99 19 89 0.5 0 91 18 18 1 9 9 99 19 r=0.96 89 0.5 0 91 99 19 0 91 89 99 19 89 18 9 1 99 19 89 r=0.98 1 9 0.5 0 91 99 19 0 91 89 99 19 89 18 9 99 19 89 0.5 0 81 88 18 0 78 81 88 18 78 0 18 18 9 0 0 71 77 17 67 71 77 17 67 18 18 81 9 88 18 r=0.62 78 71 77 17 67 Human (no examples) 0 71 77 17 67 Human (1 example) 0 0 91 99 19 89 r=0.99 0 81 88 18 78 71 77 17 67 1 71 77 17 67 r=0.38 0.5 0 89 r=0.93 0.5 1 9 99 19 r=0.99 1 0.5 0 89 r=0.99 0.5 1 9 0 91 1 r=0.88 1 9 99 19 0.5 0 91 18 0 91 0.5 0 91 18 r=0.99 1 0 r=0.74 1 0.5 71 77 17 67 RL (no examples) 0 71 77 17 67 RL (one example) Figure 3: Data and model predictions for the induction task in Experiment 1. Columns 1 and 3 show predictions before any pairs involving the new letter are observed. Columns 2 and 4 show predictions after a single novel pair (marked with a gray bar) is observed to belong to the set. The model plots for each condition include correlations with the human data. sampled at random from all pairs involving the new letter.7 All model predictions were computed using Mace4 [18] to generate the extension of each theory considered. The supporting material includes predictions for a model based on the Goodman complexity measure and an exemplar model which assumes that the new letter will be just like one of the old letters.8 The exemplar model outperforms our model in the random condition, and makes accurate predictions about three other conditions. Overall, however, our model performs better than the two baselines. Here we focus on two important predictions that are not well handled by the exemplar model. In the symmetry condition, almost all subjects predict that 78 belongs to the set after learning that 87 belongs to the set, suggesting that they have learned an abstract rule. In the transitive condition, most subjects predict that pairs 72 through 76 belong to the set after learning that 71 belongs to the set. Our model accounts for this result, but the exemplar model has no basis for making predictions about letter 7, since this letter is now known to be unlike any of the others. 2.2 Experiment 2: learning from positive examples During the learning phase of our ﬁrst experiment, subjects learned a theory based on positive examples (the theory included all pairs they had seen) and negative examples (the theory ruled out all pairs they had not seen). Often, however, humans learn theories based on positive examples alone. Suppose, for instance, that our anthropologist has spent only a few hours with a new tribe. She may have observed several pairs who are obviously friends, but should realize that many other pairs of friends have not yet interacted in her presence. 7 For the second task, P (D|T ) is set to 0 for theories that are inconsistent with the training pairs and theories 1 which do not include the observed novel pair. For all remaining theories, P (D|T ) is set to n , where n is the total number of novel pairs that are consistent with T . 8 Supporting material is available at www.charleskemp.com 6 1 221 331 441 551 c) 7 1 R(X, X, Y). 221 443 552 663 d) 7 1 R(X, Y, Z). 231 456 615 344 e) 7 1 −10 −5 −0.1 −10 −20 −20 −10 −0.2 −20 777 771 778 789 237 777 771 778 789 237 −10 231 234 235 236 0 777 771 778 789 237 0 777 771 778 789 237 0 777 771 778 789 237 0 RL 0 R(2, 3, X). 777 771 778 789 237 7 R(X, X, 1). 777 771 778 789 237 b) 777 771 778 789 237 1 111 222 333 444 777 771 778 789 237 7 R(X, X, X). 777 771 778 789 237 Human a) Figure 4: Data and model predictions for Experiment 2. The four triples observed for each set are shown at the top of the ﬁgure. The ﬁrst row of plots shows average ratings on a scale from 1 (very unlikely to belong to the set) to 7 (very likely). Model predictions are plotted as log probabilities. Our framework can handle cases like these if we assume that the data D in Equation 2 are sampled from the ground terms that are true according to the underlying theory. We follow [10] and [13] and use a distribution P (D|T ) which assumes that the examples in D are randomly sampled with replacement from the ground terms that are true. This sampling assumption encourages our model to identify the theory with the smallest extension that is compatible with all of the training examples. We tested this approach by designing an experiment where learners were given sets of examples that were compatible with several underlying theories. Materials and Methods. 15 adults participated in this experiment immediately after taking Experiment 1. In each of ﬁve conditions, subjects were told about a set of triples built from an alphabet of 9 letters. They were shown four triples that belonged to the set (Fig. 4), and told that the set might include triples that they had not seen. Subjects then gave ratings on a seven point scale to indicate whether ﬁve additional triples (see Fig. 4) were likely to belong to the set. Results. Average ratings and model predictions are shown in Fig. 4. Model predictions for each condition were computed using Equation 2 and summing over a space of theories that included the ﬁve theories shown at the top of Fig. 4, variants of these ﬁve theories which stated that certain pairs of slots could not be occupied by the same constant,9 and theories that included no variables but merely enumerated up to 5 triples.10 Although there are general theories like R(X, Y, Z) that are compatible with the triples observed in all ﬁve conditions, Fig. 4 shows that people were sensitive to different regularities in each case.11 We focus on one condition (Fig. 4b) that exposes the strengths and weaknesses of our model. According to our model, the two most probable theories given the triples for this condition are R(X, X, 1) and the closely related variant that rules out R(1, 1, 1). The next most probable theory is R(X, X, Y). These predictions are consistent with people’s judgments that 771 is very likely to belong to the set, and that 778 is the next most likely option. Unlike our model, however, people consider 777 to be substantially less likely than 778 to belong to the set. This result may suggest that the variant of R(X, X, Y) that rules out R(X, X, X) deserves a higher prior probability than our model recognizes. To better account for cases like this, it may be worth considering languages where any two variables that belong to the same clause but have different names must refer to different entities. 3 Discussion and Conclusion There are many psychological models of concept learning [4, 12, 13], but few that use representations rich enough to capture the content of intuitive theories. We suggested that intuitive theories are mentally represented in a ﬁrst-order logical language, and proposed a speciﬁc hypothesis about 9 ¯ One such theory includes two clauses: R(X, X, Y). R(X, X, X). One such theory is the following list of clauses: R(2, 2, 1). R(3, 3, 1). R(4, 4, 1). R(5, 5, 1). R(7, 7, 7). 11 Similar results have been found with 9-month old infants. Cases like Figs. 4b and 4c have been tested in an infant language-learning study where the stimuli were three-syllable strings [19]. 9-month old infants exposed to strings like the four in Fig. 4c generalized to other strings consistent with the theory R(X, X, Y), but infants in the condition corresponding to Fig. 4b generalized only to strings consistent with the theory R(X, X, 1). 10 7 this “language of thought.” We assumed that the subjective complexity of a theory depends on the length of its representation in this language, and described experiments which suggest that the resulting complexity measure helps to explain how theories are learned and used for inductive inference. Our experiments deliberately used stimuli that minimize the inﬂuence of prior knowledge. Theories, however, are cumulative, and the theory that seems simplest to a learner will often depend on her background knowledge. Our approach provides a natural place for background knowledge to be inserted. A learner can be supplied with a stock of background predicates, and the shortest representation for a data set will depend on which background predicates are available. Since different sets of predicates will lead to different predictions about subjective complexity, empirical results can help to determine the background knowledge that people bring to a given class of problems. Future work should aim to reﬁne the representation language and complexity measure we proposed. We expect that something like our approach will be suitable for modeling a broad class of intuitive theories, but the speciﬁc framework presented here can almost certainly be improved. Future work should also consider different strategies for searching the space of theories. Some of the strategies developed in the ILP literature should be relevant [14], but a detailed investigation of search algorithms seems premature until our approach has held up to additional empirical tests. It is comparatively easy to establish whether the theories that are simple according to our approach are also considered simple by people, and our experiments have made a start in this direction. It is much harder to establish that our approach captures most of the theories that are subjectively simple, and more exhaustive experiments are needed before this conclusion can be drawn. Boolean concept learning has been studied for more than ﬁfty years [4, 9], and many psychologists have made empirical and theoretical contributions to this ﬁeld. An even greater effort will be needed to crack the problem of theory learning, since the space of intuitive theories is much richer than the space of Boolean concepts. The difﬁculty of this problem should not be underestimated, but computational approaches can contribute part of the solution. Acknowledgments Supported by the William Asbjornsen Albert memorial fellowship (CK), the James S. McDonnell Foundation Causal Learning Collaborative Initiative (NDG, JBT) and the Paul E. Newton chair (JBT). References [1] N. Goodman. The structure of appearance. 2nd edition, 1961. [2] S. Carey. Conceptual change in childhood. MIT Press, Cambridge, MA, 1985. [3] H. A. Simon. Complexity and the representation of patterned sequences of symbols. Psychological Review, 79:369–382, 1972. [4] J. Feldman. An algebra of human concept learning. JMP, 50:339–368, 2006. [5] N. Chater and P. Vitanyi. Simplicity: a unifying principle in cognitive science. TICS, 7:19–22, 2003. [6] J. T. Krueger. A theory of structural simplicity and its relevance to aspects of memory, perception, and conceptual naturalness. PhD thesis, University of Pennsylvania, 1979. [7] P. Gr¨ nwald, I. J. Myung, and M. Pitt, editors. Advances in Minimum Description Length: Theory and u Applications. 2005. [8] N. Chater. Reconciling simplicity and likelihood principles in perceptual organization. Psychological Review, 103:566–581, 1996. [9] J. A. Bruner, J. S. Goodnow, and G. J. Austin. A study of thinking. Wiley, 1956. [10] D. Conklin and I. H. Witten. Complexity-based induction. Machine Learning, 16(3):203–225, 1994. [11] G. A. Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological Review, 63(1):81–97, 1956. [12] N. D. Goodman, T. L. Grifﬁths, J. Feldman, and J. B. Tenenbaum. A rational analysis of rule-based concept learning. In CogSci, 2007. [13] J. B. Tenenbaum and T. L. Grifﬁths. Generalization, similarity, and Bayesian inference. BBS, 24:629–641, 2001. [14] S. Muggleton and L. De Raedt. Inductive logic programming: theory and methods. Journal of Logic Programming, 19-20:629–679, 1994. [15] N. Chomsky. The logical structure of linguistic theory. University of Chicago Press, Chicago, 1975. [16] E. L. J. Leeuwenberg. A perceptual coding language for visual and auditory patterns. American Journal of Psychology, 84(3):307–349, 1971. [17] B. Edmonds. Syntactic measures of complexity. PhD thesis, University of Manchester, 1999. [18] W. McCune. Mace4 reference manual and guide. Technical Report ANL/MCS-TM-264, Argonne National Laboratory, 2003. [19] L. Gerken. Decisions, decisions: infant language learning when multiple generalizations are possible. Cognition, 98(3):67–74, 2006. 8

2 0.96969032 124 nips-2007-Managing Power Consumption and Performance of Computing Systems Using Reinforcement Learning

Author: Gerald Tesauro, Rajarshi Das, Hoi Chan, Jeffrey Kephart, David Levine, Freeman Rawson, Charles Lefurgy

Abstract: Electrical power management in large-scale IT systems such as commercial datacenters is an application area of rapidly growing interest from both an economic and ecological perspective, with billions of dollars and millions of metric tons of CO2 emissions at stake annually. Businesses want to save power without sacriﬁcing performance. This paper presents a reinforcement learning approach to simultaneous online management of both performance and power consumption. We apply RL in a realistic laboratory testbed using a Blade cluster and dynamically varying HTTP workload running on a commercial web applications middleware platform. We embed a CPU frequency controller in the Blade servers’ ﬁrmware, and we train policies for this controller using a multi-criteria reward signal depending on both application performance and CPU power consumption. Our testbed scenario posed a number of challenges to successful use of RL, including multiple disparate reward functions, limited decision sampling rates, and pathologies arising when using multiple sensor readings as state variables. We describe innovative practical solutions to these challenges, and demonstrate clear performance improvements over both hand-designed policies as well as obvious “cookbook” RL implementations. 1

same-paper 3 0.96339738 188 nips-2007-Subspace-Based Face Recognition in Analog VLSI

Author: Gonzalo Carvajal, Waldo Valenzuela, Miguel Figueroa

4 0.96063554 99 nips-2007-Hierarchical Penalization

Author: Marie Szafranski, Yves Grandvalet, Pierre Morizet-mahoudeaux

Abstract: Hierarchical penalization is a generic framework for incorporating prior information in the ﬁtting of statistical models, when the explicative variables are organized in a hierarchical structure. The penalizer is a convex functional that performs soft selection at the group level, and shrinks variables within each group. This favors solutions with few leading terms in the ﬁnal combination. The framework, originally derived for taking prior knowledge into account, is shown to be useful in linear regression, when several parameters are used to model the inﬂuence of one feature, or in kernel regression, for learning multiple kernels. Keywords – Optimization: constrained and convex optimization. Supervised learning: regression, kernel methods, sparsity and feature selection. 1

5 0.93633592 145 nips-2007-On Sparsity and Overcompleteness in Image Models

Author: Pietro Berkes, Richard Turner, Maneesh Sahani

Abstract: Computational models of visual cortex, and in particular those based on sparse coding, have enjoyed much recent attention. Despite this currency, the question of how sparse or how over-complete a sparse representation should be, has gone without principled answer. Here, we use Bayesian model-selection methods to address these questions for a sparse-coding model based on a Student-t prior. Having validated our methods on toy data, we ﬁnd that natural images are indeed best modelled by extremely sparse distributions; although for the Student-t prior, the associated optimal basis size is only modestly over-complete. 1

6 0.73078722 168 nips-2007-Reinforcement Learning in Continuous Action Spaces through Sequential Monte Carlo Methods

7 0.70363241 100 nips-2007-Hippocampal Contributions to Control: The Third Way

8 0.66087621 169 nips-2007-Retrieved context and the discovery of semantic structure

9 0.65604603 28 nips-2007-Augmented Functional Time Series Representation and Forecasting with Gaussian Processes

10 0.65177578 1 nips-2007-A Bayesian Framework for Cross-Situational Word-Learning

11 0.65167487 105 nips-2007-Infinite State Bayes-Nets for Structured Domains

12 0.64624828 86 nips-2007-Exponential Family Predictive Representations of State

13 0.6456911 25 nips-2007-An in-silico Neural Model of Dynamic Routing through Neuronal Coherence

14 0.64395803 148 nips-2007-Online Linear Regression and Its Application to Model-Based Reinforcement Learning

15 0.64211178 34 nips-2007-Bayesian Policy Learning with Trans-Dimensional MCMC

16 0.64054108 158 nips-2007-Probabilistic Matrix Factorization

17 0.63845468 210 nips-2007-Unconstrained On-line Handwriting Recognition with Recurrent Neural Networks

18 0.63817632 43 nips-2007-Catching Change-points with Lasso

19 0.63808405 163 nips-2007-Receding Horizon Differential Dynamic Programming

20 0.6364755 93 nips-2007-GRIFT: A graphical model for inferring visual classification features from human data