nips nips2005 nips2005-88 knowledge-graph by maker-knowledge-mining

88 nips-2005-Gradient Flow Independent Component Analysis in Micropower VLSI

Source: pdf

Author: Abdullah Celik, Milutin Stanacevic, Gert Cauwenberghs

Abstract: We present micropower mixed-signal VLSI hardware for real-time blind separation and localization of acoustic sources. Gradient ﬂow representation of the traveling wave signals acquired over a miniature (1cm diameter) array of four microphones yields linearly mixed instantaneous observations of the time-differentiated sources, separated and localized by independent component analysis (ICA). The gradient ﬂow and ICA processors each measure 3mm × 3mm in 0.5 µm CMOS, and consume 54 µW and 180 µW power, respectively, from a 3 V supply at 16 ks/s sampling rate. Experiments demonstrate perceptually clear (12dB) separation and precise localization of two speech sources presented through speakers positioned at 1.5m from the array on a conference room table. Analysis of the multipath residuals shows that they are spectrally diffuse, and void of the direct path.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We present micropower mixed-signal VLSI hardware for real-time blind separation and localization of acoustic sources. [sent-2, score-0.767]

2 Gradient ﬂow representation of the traveling wave signals acquired over a miniature (1cm diameter) array of four microphones yields linearly mixed instantaneous observations of the time-differentiated sources, separated and localized by independent component analysis (ICA). [sent-3, score-0.745]

3 The gradient ﬂow and ICA processors each measure 3mm × 3mm in 0. [sent-4, score-0.209]

4 Experiments demonstrate perceptually clear (12dB) separation and precise localization of two speech sources presented through speakers positioned at 1. [sent-6, score-0.774]

5 Analysis of the multipath residuals shows that they are spectrally diffuse, and void of the direct path. [sent-8, score-0.061]

6 1 Introduction Time lags in acoustic wave propagation provide cues to localize an acoustic source from observations across an array. [sent-9, score-0.714]

7 The time lags also complicate the task of separating multiple co-existing sources using independent component analysis (ICA), which conventionally assumes instantaneous mixture observations. [sent-10, score-0.267]

8 Inspiration from biology suggests that for very small aperture (spacing between acoustic sensors i. [sent-11, score-0.266]

9 , tympanal membranes), small differences (gradients) in sound pressure level are more effective in resolving source direction than actual (microsecond scale) time differences. [sent-13, score-0.26]

10 The remarkable auditory localization capability of certain insects at a small (1%) fraction of the wavelength of the source owes to highly sensitive differential processing of sound pressure through inter-tympanal mechanical coupling [1] or inter-aural coupled neural circuits [2]. [sent-14, score-0.635]

11 We present a mixed-signal VLSI system that operates on spatial and temporal differences (gradients) of the acoustic ﬁeld at very small aperture to separate and localize mixtures of traveling wave sources. [sent-15, score-0.693]

12 The real-time performance of the system is characterized through experiments with speech sources presented through speakers in a conference room setting. [sent-16, score-0.493]

13 At low aperture, interaural level differences (ILD) and interaural time differences (ITD) are directly related, scaled by the temporal derivative of the signal. [sent-18, score-0.154]

14 (b) 3-D localization (azimuth θ and elevation φ) of an acoustic source using a planar geometry of four microphones. [sent-19, score-0.508]

15 2 Gradient Flow Independent Component Analysis Gradient ﬂow [3, 4] is a signal conditioning technique for source separation and localization suited for arrays of very small aperture, i. [sent-20, score-0.508]

16 , of dimensions signiﬁcantly smaller than the shortest wavelength in the sources. [sent-22, score-0.035]

17 Consider a traveling acoustic wave impinging on an array of four microphones, in the conﬁguration of Figure 1 (b). [sent-24, score-0.489]

18 The 3-D direction cosines of the traveling wave u are implied by propagation delays τ1 and τ2 in the source along directions p and q in the sensor plane. [sent-25, score-0.538]

19 Direct measurement of these delays is problematic as they require sampling in excess of the bandwidth of the signal, increasing noise ﬂoor and power requirements. [sent-26, score-0.047]

20 As shown in Figure 1 (b), the planar geometry of four microphones allows to localize a source in 3-D, with both azimuth and elevation 1 . [sent-29, score-0.389]

21 Taking the time derivative of ξ00 , we thus obtain from the sensors a linear instantaneous mixture of the time-differentiated source signals,   1    s ˙ ˙ 1 ··· 1 ν00 ˙ ξ00 1 L  . [sent-31, score-0.19]

22 1 L ν01 L τ2 · · · τ2 ξ01 s ˙ an equation in the standard form x = As + n, where x is given and the mixing matrix A and sources s are unknown. [sent-34, score-0.182]

23 Ignoring the noise term n, the problem setting is standard in Independent Component Analysis (ICA), and three independent sources can be identiﬁed from the three gradient observations. [sent-35, score-0.344]

24 ICA algorithms typically specify some sort of statistical independence assumption on the sources s either in distribution over amplitude [7] or over time [8]. [sent-37, score-0.182]

25 Most forms specify ICA to be static, in assuming that the observations contain static (instantaneous) linear mixtures of the sources. [sent-38, score-0.148]

26 Note that this deﬁnition of static ICA includes methods for blind source separation that make use of temporal structure in the dynamics within the sources themselves [8], as long as the observed mixture of the sources is static. [sent-39, score-0.887]

27 In contrast, ‘convolutive’ ICA techniques explicitly assume convolutive or delayed mixtures in the source observations. [sent-40, score-0.369]

28 , [10]) are usually much more involved and require a large number of parameters and long adaptation time horizons for proper convergence. [sent-43, score-0.06]

29 The instantaneous static formulation of gradient ﬂow (4) is convenient,2 and avoids the need for non-static (convolutive) ICA to separate delayed mixtures of traveling wave sources (in s (t + pτ1 + qτ2 ). [sent-44, score-0.83]

30 Reverberation in multipath wave propagation free space) xpq (t) = contributes delayed mixture components in the observations which limit the effectiveness of a static ICA formulation. [sent-45, score-0.33]

31 As shown in the experiments below, static ICA still produces reasonable results (12 dB of perceptually clear separation) in typical enclosed acoustic environments (conference room). [sent-46, score-0.319]

32 3 Micropower VLSI Implementation Various analog VLSI implementations of ICA exist in the literature, e. [sent-47, score-0.046]

33 , [11, 12], and digital implementations using DSP are common practice in the ﬁeld. [sent-49, score-0.056]

34 By adopting a mixedsignal architecture in the implementation, we combine advantages of both approaches: an analog datapath directly interfaces with inputs and outputs without the need for data conversion; and digital adaptation offers the ﬂexibility of reconﬁgurable ICA learning rules. [sent-50, score-0.285]

35 2 The time-derivative in the source signals (4) is immaterial, and can be removed by timeintegrating the separated signals obtained by applying ICA directly to the gradient ﬂow signals. [sent-51, score-0.601]

36 Dimensions of both processors are 3mm × 3mm in 0. [sent-55, score-0.047]

37 µC -1, 0, +1 W12 W13 W21 W22 W23 W31 update bits W11 W32 W33 x2 y1 y2 Wij y3 yj xi level comparison x1 level comparison output bits -1, 0, +1 update bits x3 Figure 3: Reconﬁgurable mixed-signal ICA architecture implementing general outerproduct forms of ICA update rules. [sent-57, score-0.672]

38 1 Gradient Flow Processor The mixed-signal VLSI processor implementing gradient ﬂow is presented in [6]. [sent-59, score-0.304]

39 A micro˙ graph of the chip is shown in Figure 2 (a). [sent-60, score-0.106]

40 Precise analog gradients ξ00 , ξ10 and ξ01 are acquired from the microphone signals by correlated double sampling (CDS) in fully differential switched-capacitor circuits. [sent-61, score-0.381]

41 Least-mean-squares (LMS) cancellation of common-mode leakage in the gradient signals further increases differential sensitivity. [sent-62, score-0.334]

42 The adaptation is performed in the digital domain using counting registers, and couples to the switchedcapacitor circuits using capacitive multiplying DAC arrays. [sent-63, score-0.394]

43 An additional stage of LMS adaptation produces digital estimates of direction cosines τ1 and τ2 for a single source. [sent-64, score-0.186]

44 In the present setup this stage is bypassed, and the common-mode corrected gradient signals are presented as inputs to the ICA chip for localization and separation of up to three independent sources. [sent-65, score-0.734]

45 2 Reconﬁgurable ICA Processor A general mixed-signal parallel architecture, that can be conﬁgured for implementation of various ICA update rules in conjunction with gradient ﬂow, is shown in Figure 3 [9]. [sent-67, score-0.312]

46 Here we brieﬂy illustrate the architecture with a simple conﬁguration designed to separate two sources, and present CMOS circuits that implement the architecture. [sent-68, score-0.266]

47 The micrograph of the reconﬁgurable ICA chip is shown in Figure 2 (a). [sent-69, score-0.106]

48 1 ICA update rule Efﬁcient implementation in parallel architecture requires a simple form of the update rule, that avoids excessive matrix multiplications and inversions. [sent-72, score-0.394]

49 A variety of ICA update algorithms can be cast in a common, unifying framework of outer-product rules [9]. [sent-73, score-0.083]

50 To obtain estimates y = ˆ of the sources s, a linear transformation with matrix W is applied s to the gradient signals x, y = Wx. [sent-74, score-0.468]

51 Diagonal terms are ﬁxed wii ≡ 1, and off-diagonal terms adapt according to ∆wij = −µ f (yi )g(yj ), i=j (5) The implemented update rule can be seen as the gradient of InfoMax [7] multiplied by WT , rather than the natural gradient multiplication factor WT W. [sent-75, score-0.445]

52 To obtain the full natural gradient in outer-product form, it is necessary to include a back-propagation path in the network architecture, and thus additional silicon resources, to implement the vector contribution yT . [sent-76, score-0.162]

53 2 Architecture Level comparison provides implementation of discrete approximations of any scalar function f (y) and g(y) appearing in different learning rules. [sent-80, score-0.067]

54 Since speech signals are approximately Laplacian distributed, the nonlinear scalar function f (y) is approximated by sign(y) and implemented using single bit quantization. [sent-81, score-0.186]

55 Conversely, a linear function g(y) ≡ y in the learning rule is approximated by a 3-level staircase function (−1, 0, +1) using 2-bit quantization. [sent-82, score-0.038]

56 The quantization of the f and g terms in the update rule (5) simpliﬁes the implementation to that of discrete counting operations. [sent-83, score-0.188]

57 The functional block diagram of a 3 × 3 outer-product incremental ICA architecture, supporting a quantized form of the general update rule (5), is shown in Figure 3 [9]. [sent-84, score-0.121]

58 The update is performed locally by once or repeatedly incrementing, decrementing or holding the current value of counter based on the learning rule served by the micro-controller. [sent-86, score-0.282]

59 The 8 most signiﬁcant bits of the 14-bit counter holding and updating the coefﬁcients are presented to a multiplying D/A capacitor array [6] to linearly unmix the separated signal. [sent-87, score-0.506]

60 The remaining 6 bits in the coefﬁcient registers provide ﬂexibility in programming the update rate to tailor convergence. [sent-88, score-0.273]

61 3 Circuit implementation As in the implementation of the gradient ﬂow processor [6], the mixed-signal ICA architecture is implemented using fully differential switched-capacitor sampled-data circuits. [sent-91, score-0.536]

62 Correlated double sampling performs common mode offset rejection and 1/f noise reduction. [sent-92, score-0.036]

63 An external micro-controller provides ﬂexibility in the implementation of different learning rules. [sent-93, score-0.067]

64 The ICA architecture is integrated on a single 3mm × 3mm chip fabricated in 0. [sent-94, score-0.229]

65 Each cell in the implemented architecture contains a 14-bit counter, decoder and D/A capacitor arrays. [sent-97, score-0.185]

66 Adaptation is performed in outer-product fashion by incrementing, decrementing or holding the current value of the counters. [sent-98, score-0.092]

67 5 m Figure 5: Experimental setup for separation of two acoustic sources in a conference room enviroment. [sent-102, score-0.591]

68 counter are presented to the multiplying D/A capacitor arrays to construct the source estimation. [sent-103, score-0.463]

69 Figure 4 shows the circuits one output component in the architecture, linearly summing the input contributions. [sent-104, score-0.143]

70 The implementation of the multiplying capacitor arrays are identical to those discussed in [6]. [sent-105, score-0.282]

71 The accumulation is performed on C2 by switch-cap ampliﬁer yielding the estimated signals during Φ2 phase. [sent-107, score-0.124]

72 While the estimation ˆ signals are valid, yi + is sampled at Φ1 by the comparator circuit. [sent-108, score-0.124]

73 The sign of the comparison of yi with variable level threshold Vth is computed in the evaluate phase, through capacitive coupling into the ampliﬁer input node. [sent-109, score-0.047]

74 4 Experimental Results To demonstrate source separation and localization in a real environment, the mixed-signal VLSI ASICs were interfaced with four omnidirectional miniature microphones (Knowles FG-3629), arranged in a circular array with radius 0. [sent-110, score-0.697]

75 At the front-end, the microphone signals were passed through second-order bandpass ﬁlters with low-frequency cutoff at 130 Hz and high-frequency cutoff at 4. [sent-112, score-0.185]

76 The signals were also ampliﬁed by a factor of 20. [sent-114, score-0.124]

77 The speech signals were presented through loudspeakers positioned at 1. [sent-116, score-0.225]

78 The system sampling frequency of both chips was set to 16 kHz. [sent-118, score-0.037]

79 A male and female speakers from TIMIT database were chosen as sound sources. [sent-119, score-0.184]

80 To provide the ground truth data and full characterization of the systems, speech segments were presented individually through either loudspeaker at different time instances. [sent-120, score-0.101]

81 The data was recorded for both speakers, archived, and presented to the ξ10 5 ξ01 2 ^ s1 2 ^ s2 1 0 0 2 1 2 3 0 0 2 1 2 3 0 0 1 1 2 3 0 0 1 1 2 3 0 1 0 1 2 3 Frequency Frequency Frequency Frequency Frequency ξ00 5 1 0. [sent-121, score-0.085]

82 5 0 0 1 Time (s) 2 Time 4 x 10 Figure 6: Time waveforms and spectrograms of the presented sources s1 and s2 , observed common-mode and gradient signals ξ00 , ξ10 and ξ01 by the gradient ﬂow chip, and recovered sources s1 and s2 by the ICA chip. [sent-126, score-0.851]

83 ˆ ˆ Table 1: Localization Performance Single-source LMS localization Dual-source ICA localization Male speaker -31. [sent-127, score-0.325]

84 Localization results obtained by gradient ﬂow chip through LMS adaptation are reported in Table 1. [sent-132, score-0.328]

85 The two recorded datasets were then added, and presented to the gradient ﬂow ASIC. [sent-133, score-0.247]

86 The gradient signals obtained from the chip were then presented to the ICA processor, conﬁgured to implement the outerproduct update algorithm in (5). [sent-134, score-0.561]

87 From the recorded 14-bit digital weights, the angles of incidence of the sources relative to the array were derived. [sent-136, score-0.407]

88 As seen, the angles obtained through LMS bearing estimation under individual source presentation are very close to the angles produced by ICA under joint presentation of both sources. [sent-138, score-0.228]

89 The original sources and the recorded source signal estimates, along with recorded common-mode signal and ﬁrst-order spatial gradients, are shown in Figure 6. [sent-139, score-0.457]

90 5 Conclusions We presented a mixed-signal VLSI system that operates on spatial and temporal differences (gradients) of the acoustic ﬁeld at very small aperture to separate and localize mixtures of traveling wave sources. [sent-140, score-0.732]

91 The real-time performance of the system was characterized through experiments with speech sources presented through speakers in a conference room setting. [sent-141, score-0.493]

92 Although application of static ICA is limited by reverberation, the perceptual quality of the separated outputs owes to the elimination of the direct path in the residuals. [sent-142, score-0.191]

93 Miniature size of the microphone array enclosure (1 cm diameter) and micropower consumption of the VLSI hardware (250 µW) are key advantages of the approach, with applications to hearing aids, conferencing, multimedia, and surveillance. [sent-143, score-0.345]

94 Webb, “New neural circuits for robot phonotaxis”, Philosophical Transactions of the Royal Society A, vol. [sent-156, score-0.143]

95 Schuster, “Separation of a mixture of independent signals using time delayed correlations,” Physical Review Letters, vol. [sent-199, score-0.181]

96 Bell, “Blind separation of multiple speakers in a multipath environment,” Proc. [sent-212, score-0.363]

97 Circuits and Systems II, vol 42 (2), pp 65-77, Feb. [sent-219, score-0.043]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ica', 0.477), ('ow', 0.186), ('sources', 0.182), ('acoustic', 0.179), ('gradient', 0.162), ('separation', 0.161), ('vlsi', 0.143), ('lms', 0.143), ('circuits', 0.143), ('localization', 0.142), ('speakers', 0.141), ('source', 0.14), ('blind', 0.129), ('signals', 0.124), ('architecture', 0.123), ('wave', 0.119), ('cauwenberghs', 0.117), ('convolutive', 0.117), ('gurable', 0.117), ('micropower', 0.117), ('recon', 0.117), ('registers', 0.117), ('traveling', 0.112), ('chip', 0.106), ('dac', 0.094), ('stanacevic', 0.094), ('static', 0.093), ('microphones', 0.093), ('multiplying', 0.088), ('aperture', 0.087), ('update', 0.083), ('miniature', 0.082), ('array', 0.079), ('cmos', 0.078), ('iscas', 0.074), ('bits', 0.073), ('cosines', 0.07), ('counter', 0.069), ('processor', 0.069), ('room', 0.069), ('implementation', 0.067), ('gradients', 0.066), ('arrays', 0.065), ('capacitor', 0.062), ('localize', 0.062), ('speech', 0.062), ('microphone', 0.061), ('multipath', 0.061), ('adaptation', 0.06), ('delayed', 0.057), ('digital', 0.056), ('mixtures', 0.055), ('separated', 0.051), ('instantaneous', 0.05), ('sensor', 0.05), ('flow', 0.049), ('hearing', 0.049), ('differential', 0.048), ('azimuth', 0.047), ('capacitive', 0.047), ('cds', 0.047), ('celik', 0.047), ('decrementing', 0.047), ('elevation', 0.047), ('ild', 0.047), ('localizer', 0.047), ('outerproduct', 0.047), ('owes', 0.047), ('perceptually', 0.047), ('processors', 0.047), ('wijc', 0.047), ('delays', 0.047), ('recorded', 0.046), ('analog', 0.046), ('holding', 0.045), ('angles', 0.044), ('spatial', 0.043), ('pp', 0.043), ('sound', 0.043), ('gured', 0.041), ('reverberation', 0.041), ('interaural', 0.041), ('itd', 0.041), ('tympanal', 0.041), ('incrementing', 0.041), ('speaker', 0.041), ('vth', 0.041), ('presented', 0.039), ('ampli', 0.039), ('hardware', 0.039), ('rule', 0.038), ('insects', 0.037), ('frequency', 0.037), ('double', 0.036), ('differences', 0.036), ('localized', 0.035), ('wavelength', 0.035), ('lags', 0.035), ('implementing', 0.034), ('cohen', 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000008 88 nips-2005-Gradient Flow Independent Component Analysis in Micropower VLSI

Author: Abdullah Celik, Milutin Stanacevic, Gert Cauwenberghs

2 0.19080471 20 nips-2005-Affine Structure From Sound

Author: Sebastian Thrun

Abstract: We consider the problem of localizing a set of microphones together with a set of external acoustic events (e.g., hand claps), emitted at unknown times and unknown locations. We propose a solution that approximates this problem under a far ﬁeld approximation deﬁned in the calculus of afﬁne geometry, and that relies on singular value decomposition (SVD) to recover the afﬁne structure of the problem. We then deﬁne low-dimensional optimization techniques for embedding the solution into Euclidean geometry, and further techniques for recovering the locations and emission times of the acoustic events. The approach is useful for the calibration of ad-hoc microphone arrays and sensor networks. 1

3 0.12904045 29 nips-2005-Analyzing Coupled Brain Sources: Distinguishing True from Spurious Interaction

Author: Guido Nolte, Andreas Ziehe, Frank Meinecke, Klaus-Robert Müller

Abstract: When trying to understand the brain, it is of fundamental importance to analyse (e.g. from EEG/MEG measurements) what parts of the cortex interact with each other in order to infer more accurate models of brain activity. Common techniques like Blind Source Separation (BSS) can estimate brain sources and single out artifacts by using the underlying assumption of source signal independence. However, physiologically interesting brain sources typically interact, so BSS will—by construction— fail to characterize them properly. Noting that there are truly interacting sources and signals that only seemingly interact due to effects of volume conduction, this work aims to contribute by distinguishing these effects. For this a new BSS technique is proposed that uses anti-symmetrized cross-correlation matrices and subsequent diagonalization. The resulting decomposition consists of the truly interacting brain sources and suppresses any spurious interaction stemming from volume conduction. Our new concept of interacting source analysis (ISA) is successfully demonstrated on MEG data. 1

4 0.12748566 25 nips-2005-An aVLSI Cricket Ear Model

Author: Andre V. Schaik, Richard Reeve, Craig Jin, Tara Hamilton

Abstract: Female crickets can locate males by phonotaxis to the mating song they produce. The behaviour and underlying physiology has been studied in some depth showing that the cricket auditory system solves this complex problem in a unique manner. We present an analogue very large scale integrated (aVLSI) circuit model of this process and show that results from testing the circuit agree with simulation and what is known from the behaviour and physiology of the cricket auditory system. The aVLSI circuitry is now being extended to use on a robot along with previously modelled neural circuitry to better understand the complete sensorimotor pathway. 1 In trod u ction Understanding how insects carry out complex sensorimotor tasks can help in the design of simple sensory and robotic systems. Often insect sensors have evolved into intricate filters matched to extract highly specific data from the environment which solves a particular problem directly with little or no need for further processing [1]. Examples include head stabilisation in the fly, which uses vision amongst other senses to estimate self-rotation and thus to stabilise its head in flight, and phonotaxis in the cricket. Because of the narrowness of the cricket body (only a few millimetres), the Interaural Time Difference (ITD) for sounds arriving at the two sides of the head is very small (10–20µs). Even with the tympanal membranes (eardrums) located, as they are, on the forelegs of the cricket, the ITD only reaches about 40µs, which is too low to detect directly from timings of neural spikes. Because the wavelength of the cricket calling song is significantly greater than the width of the cricket body the Interaural Intensity Difference (IID) is also very low. In the absence of ITD or IID information, the cricket uses phase to determine direction. This is possible because the male cricket produces an almost pure tone for its calling song. * School of Electrical and Information Engineering, Institute of Perception, Action and Behaviour. + Figure 1: The cricket auditory system. Four acoustic inputs channel sounds directly or through tracheal tubes onto two tympanal membranes. Sound from contralateral inputs has to pass a (double) central membrane (the medial septum), inducing a phase delay and reduction in gain. The sound transmission from the contralateral tympanum is very weak, making each eardrum effectively a 3 input system. The physics of the cricket auditory system is well understood [2]; the system (see Figure 1) uses a pair of sound receivers with four acoustic inputs, two on the forelegs, which are the external surfaces of the tympana, and two on the body, the prothoracic or acoustic spiracles [3]. The connecting tracheal tubes are such that interference occurs as sounds travel inside the cricket, producing a directional response at the tympana to frequencies near to that of the calling song. The amplitude of vibration of the tympana, and hence the firing rate of the auditory afferent neurons attached to them, vary as a sound source is moved around the cricket and the sounds from the different inputs move in and out of phase. The outputs of the two tympana match when the sound is straight ahead, and the inputs are bilaterally symmetric with respect to the sound source. However, when sound at the calling song frequency is off-centre the phase of signals on the closer side comes better into alignment, and the signal increases on that side, and conversely decreases on the other. It is that crossover of tympanal vibration amplitudes which allows the cricket to track a sound source (see Figure 6 for example). A simplified version of the auditory system using only two acoustic inputs was implemented in hardware [4], and a simple 8-neuron network was all that was required to then direct a robot to carry out phonotaxis towards a species-specific calling song [5]. A simple simulator was also created to model the behaviour of the auditory system of Figure 1 at different frequencies [6]. Data from Michelsen et al. [2] (Figures 5 and 6) were digitised, and used together with average and “typical” values from the paper to choose gains and delays for the simulation. Figure 2 shows the model of the internal auditory system of the cricket from sound arriving at the acoustic inputs through to transmission down auditory receptor fibres. The simulator implements this model up to the summing of the delayed inputs, as well as modelling the external sound transmission. Results from the simulator were used to check the directionality of the system at different frequencies, and to gain a better understanding of its response. It was impractical to check the effect of leg movements or of complex sounds in the simulator due to the necessity of simulating the sound production and transmission. An aVLSI chip was designed to implement the same model, both allowing more complex experiments, such as leg movements to be run, and experiments to be run in the real world. Figure 2: A model of the auditory system of the cricket, used to build the simulator and the aVLSI implementation (shown in boxes). These experiments with the simulator and the circuits are being published in [6] and the reader is referred to those papers for more details. In the present paper we present the details of the circuits used for the aVLSI implementation. 2 Circuits The chip, implementing the aVLSI box in Figure 2, comprises two all-pass delay filters, three gain circuits, a second-order narrow-band band-pass filter, a first-order wide-band band-pass filter, a first-order high-pass filter, as well as supporting circuitry (including reference voltages, currents, etc.). A single aVLSI chip (MOSIS tiny-chip) thus includes half the necessary circuitry to model the complete auditory system of a cricket. The complete model of the auditory system can be obtained by using two appropriately connected chips. Only two all-pass delay filters need to be implemented instead of three as suggested by Figure 2, because it is only the relative delay between the three pathways arriving at the one summing node that counts. The delay circuits were implemented with fully-differential gm-C filters. In order to extend the frequency range of the delay, a first-order all-pass delay circuit was cascaded with a second-order all-pass delay circuit. The resulting addition of the first-order delay and the second-order delay allowed for an approximately flat delay response for a wider bandwidth as the decreased delay around the corner frequency of the first-order filter cancelled with the increased delay of the second-order filter around its resonant frequency. Figure 3 shows the first- and second-order sections of the all-pass delay circuit. Two of these circuits were used and, based on data presented in [2], were designed with delays of 28µs and 62µs, by way of bias current manipulation. The operational transconductance amplifier (OTA) in figure 3 is a standard OTA which includes the common-mode feedback necessary for fully differential designs. The buffers (Figure 3) are simple, cascoded differential pairs. V+ V- II+ V+ V- II+ V+ V- II+ V+ V- II+ V+ V- II+ V+ V- II+ Figure 3: The first-order all-pass delay circuit (left) and the second-order all-pass delay (right). The differential output of the delay circuits is converted into a current which is multiplied by a variable gain implemented as shown in Figure 4. The gain cell includes a differential pair with source degeneration via transistors N4 and N5. The source degeneration improves the linearity of the current. The three gain cells implemented on the aVLSI have default gains of 2, 3 and 0.91 which are set by holding the default input high and appropriately ratioing the bias currents through the value of vbiasp. To correct any on-chip mismatches and/or explore other gain configurations a current splitter cell [7] (p-splitter, figure 4) allows the gain to be programmed by digital means post fabrication. The current splitter takes an input current (Ibias, figure 4) and divides it into branches which recursively halve the current, i.e., the first branch gives ½ Ibias, the second branch ¼ Ibias, the third branch 1/8 Ibias and so on. These currents can be used together with digitally controlled switches as a Digital-to-Analogue converter. By holding default low and setting C5:C0 appropriately, any gain – from 4 to 0.125 – can be set. To save on output pins the program bits (C5:C0) for each of the three gain cells are set via a single 18-bit shift register in bit-serial fashion. Summing the output of the three gain circuits in the current domain simply involves connecting three wires together. Therefore, a natural option for the filters that follow is to use current domain filters. In our case we have chosen to implement log-domain filters using MOS transistors operating in weak inversion. Figure 5 shows the basic building blocks for the filters – the Tau Cell [8] and the multiplier cell – and block diagrams showing how these blocks were connected to create the necessary filtering blocks. The Tau Cell is a log-domain filter which has the firstorder response: I out 1 , = I in sτ + 1 where τ = nC aVT Ia and n = the slope factor, VT = thermal voltage, Ca = capacitance, and Ia = bias current. In figure 5, the input currents to the Tau Cell, Imult and A*Ia, are only used when building a second-order filter. The multiplier cell is simply a translinear loop where: I out1 ∗ I mult = I out 2 ∗ AI a or Imult = AIaIout2/Iout1. The configurations of the Tau Cell to get particular responses are covered in [8] along with the corresponding equations. The high frequency filter of Figure 2 is implemented by the high-pass filter in Figure 5 with a corner frequency of 17kHz. The low frequency filter, however, is divided into two parts since the biological filter’s response (see for example Figure 3A in [9]) separates well into a narrow second-order band-pass filter with a 10kHz resonant frequency and a wide band-pass filter made from a first-order high-pass filter with a 3kHz corner frequency followed by a first-order low-pass filter with a 12kHz corner frequency. These filters are then added together to reproduce the biological filter. The filters’ responses can be adjusted post fabrication via their bias currents. This allows for compensation due to processing and matching errors. Figure 4: The Gain Cell above is used to convert the differential voltage input from the delay cells into a single-ended current output. The gain of each cell is controllable via a programmable current cell (p_splitter). An on-chip bias generator [7] was used to create all the necessary current biases on the chip. All the main blocks (delays, gain cells and filters), however, can have their on-chip bias currents overridden through external pins on the chip. The chip was fabricated using the MOSIS AMI 1.6µm technology and designed using the Cadence Custom IC Design Tools (5.0.33). 3 Methods The chip was tested using sound generated on a computer and played through a soundcard to the chip. Responses from the chip were recorded by an oscilloscope, and uploaded back to the computer on completion. Given that the output from the chip and the gain circuits is a current, an external current-sense circuit built with discrete components was used to enable the output to be probed by the oscilloscope. Figure 5: The circuit diagrams for the log-domain filter building blocks – The Tau Cell and The Multiplier – along with the block diagrams for the three filters used in the aVLSI model. Initial experiments were performed to tune the delays and gains. After that, recordings were taken of the directional frequency responses. Sounds were generated by computer for each chip input to simulate moving the forelegs by delaying the sound by the appropriate amount of time; this was a much simpler solution than using microphones and moving them using motors. 4 Results The aVLSI chip was tested to measure its gains and delays, which were successfully tuned to the appropriate values. The chip was then compared with the simulation to check that it was faithfully modelling the system. A result of this test at 4kHz (approximately the cricket calling-song frequency) is shown in Figure 6. Apart from a drop in amplitude of the signal, the response of the circuit was very similar to that of the simulator. The differences were expected because the aVLSI circuit has to deal with real-world noise, whereas the simulated version has perfect signals. Examples of the gain versus frequency response of the two log-domain band-pass filters are shown in Figure 7. Note that the narrow-band filter peaks at 6kHz, which is significantly above the mating song frequency of the cricket which is around 4.5kHz. This is not a mistake, but is observed in real crickets as well. As stated in the introduction, a range of further testing results with both the circuit and the simulator are being published in [6]. 5 D i s c u s s i on The aVLSI auditory sensor in this research models the hearing of the field cricket Gryllus bimaculatus. It is a more faithful model of the cricket auditory system than was previously built in [4], reproducing all the acoustic inputs, as well as the responses to frequencies of both the co specific calling song and bat echolocation chirps. It also generates outputs corresponding to the two sets of behaviourally relevant auditory receptor fibres. Results showed that it matched the biological data well, though there were some inconsistencies due to an error in the specification that will be addressed in a future iteration of the design. A more complete implementation across all frequencies was impractical because of complexity and size issues as well as serving no clear behavioural purpose. Figure 6: Vibration amplitude of the left (dotted) and right (solid) virtual tympana measured in decibels in response to a 4kHz tone in simulation (left) and on the aVLSI chip (right). The plot shows the amplitude of the tympanal responses as the sound source is rotated around the cricket. Figure 7: Frequency-Gain curves for the narrow-band and wide-band bandpass filters. The long-term aim of this work is to better understand simple sensorimotor control loops in crickets and other insects. The next step is to mount this circuitry on a robot to carry out behavioural experiments, which we will compare with existing and new behavioural data (such as that in [10]). This will allow us to refine our models of the neural circuitry involved. Modelling the sensory afferent neurons in hardware is necessary in order to reduce processor load on our robot, so the next revision will include these either onboard, or on a companion chip as we have done before [11]. We will also move both sides of the auditory system onto a single chip to conserve space on the robot. It is our belief and experience that, as a result of this intelligent pre-processing carried out at the sensor level, the neural circuits necessary to accurately model the behaviour will remain simple. Acknowledgments The authors thank the Institute of Neuromorphic Engineering and the UK Biotechnology and Biological Sciences Research Council for funding the research in this paper. References [1] R. Wehner. Matched ﬁlters – neural models of the external world. J Comp Physiol A, 161: 511–531, 1987. [2] A. Michelsen, A. V. Popov, and B. Lewis. Physics of directional hearing in the cricket Gryllus bimaculatus. Journal of Comparative Physiology A, 175:153–164, 1994. [3] A. Michelsen. The tuned cricket. News Physiol. Sci., 13:32–38, 1998. [4] H. H. Lund, B. Webb, and J. Hallam. A robot attracted to the cricket species Gryllus bimaculatus. In P. Husbands and I. Harvey, editors, Proceedings of 4th European Conference on Artiﬁcial Life, pages 246–255. MIT Press/Bradford Books, MA., 1997. [5] R Reeve and B. Webb. New neural circuits for robot phonotaxis. Phil. Trans. R. Soc. Lond. A, 361:2245–2266, August 2003. [6] R. Reeve, A. van Schaik, C. Jin, T. Hamilton, B. Torben-Nielsen and B. Webb Directional hearing in a silicon cricket. Biosystems, (in revision), 2005b [7] T. Delbrück and A. van Schaik, Bias Current Generators with Wide Dynamic Range, Analog Integrated Circuits and Signal Processing 42(2), 2005 [8] A. van Schaik and C. Jin, The Tau Cell: A New Method for the Implementation of Arbitrary Differential Equations, IEEE International Symposium on Circuits and Systems (ISCAS) 2003 [9] Kazuo Imaizumi and Gerald S. Pollack. Neural coding of sound frequency by cricket auditory receptors. The Journal of Neuroscience, 19(4):1508– 1516, 1999. [10] Berthold Hedwig and James F.A. Poulet. Complex auditory behaviour emerges from simple reactive steering. Nature, 430:781–785, 2004. [11] R. Reeve, B. Webb, A. Horchler, G. Indiveri, and R. Quinn. New technologies for testing a model of cricket phonotaxis on an outdoor robot platform. Robotics and Autonomous Systems, 51(1):41-54, 2005.

5 0.12307175 113 nips-2005-Learning Multiple Related Tasks using Latent Independent Component Analysis

Author: Jian Zhang, Zoubin Ghahramani, Yiming Yang

Abstract: We propose a probabilistic model based on Independent Component Analysis for learning multiple related tasks. In our model the task parameters are assumed to be generated from independent sources which account for the relatedness of the tasks. We use Laplace distributions to model hidden sources which makes it possible to identify the hidden, independent components instead of just modeling correlations. Furthermore, our model enjoys a sparsity property which makes it both parsimonious and robust. We also propose efﬁcient algorithms for both empirical Bayes method and point estimation. Our experimental results on two multi-label text classiﬁcation data sets show that the proposed approach is promising.

6 0.12234488 22 nips-2005-An Analog Visual Pre-Processing Processor Employing Cyclic Line Access in Only-Nearest-Neighbor-Interconnects Architecture

7 0.11864015 183 nips-2005-Stimulus Evoked Independent Factor Analysis of MEG Data with Large Background Activity

8 0.10692152 101 nips-2005-Is Early Vision Optimized for Extracting Higher-order Dependencies?

9 0.099104129 1 nips-2005-AER Building Blocks for Multi-Layer Multi-Chip Neuromorphic Vision Systems

10 0.080449432 174 nips-2005-Separation of Music Signals by Harmonic Structure Modeling

11 0.069126703 40 nips-2005-CMOL CrossNets: Possible Neuromorphic Nanoelectronic Circuits

12 0.066974349 15 nips-2005-A Theoretical Analysis of Robust Coding over Noisy Overcomplete Channels

13 0.066476479 163 nips-2005-Recovery of Jointly Sparse Signals from Few Random Projections

14 0.06435845 17 nips-2005-Active Bidirectional Coupling in a Cochlear Chip

15 0.063008718 169 nips-2005-Saliency Based on Information Maximization

16 0.058639381 176 nips-2005-Silicon growth cones map silicon retina

17 0.052072249 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

18 0.049518686 181 nips-2005-Spiking Inputs to a Winner-take-all Network

19 0.048453808 118 nips-2005-Learning in Silicon: Timing is Everything

20 0.048229005 7 nips-2005-A Cortically-Plausible Inverse Problem Solving Method Applied to Recognizing Static and Kinematic 3D Objects

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.149), (1, -0.077), (2, -0.021), (3, 0.079), (4, -0.036), (5, 0.011), (6, -0.142), (7, -0.128), (8, 0.166), (9, -0.013), (10, -0.407), (11, -0.061), (12, -0.074), (13, 0.141), (14, -0.04), (15, -0.04), (16, -0.063), (17, -0.033), (18, 0.097), (19, -0.02), (20, -0.155), (21, 0.016), (22, 0.091), (23, 0.046), (24, 0.037), (25, -0.032), (26, -0.056), (27, -0.058), (28, -0.05), (29, 0.005), (30, 0.137), (31, 0.023), (32, 0.049), (33, 0.028), (34, -0.056), (35, -0.034), (36, -0.011), (37, 0.025), (38, 0.097), (39, -0.019), (40, -0.042), (41, 0.001), (42, 0.047), (43, 0.111), (44, -0.033), (45, -0.014), (46, 0.048), (47, 0.141), (48, -0.065), (49, 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.98427033 88 nips-2005-Gradient Flow Independent Component Analysis in Micropower VLSI

Author: Abdullah Celik, Milutin Stanacevic, Gert Cauwenberghs

2 0.66302401 183 nips-2005-Stimulus Evoked Independent Factor Analysis of MEG Data with Large Background Activity

Author: Kenneth Hild, Kensuke Sekihara, Hagai T. Attias, Srikantan S. Nagarajan

Abstract: This paper presents a novel technique for analyzing electromagnetic imaging data obtained using the stimulus evoked experimental paradigm. The technique is based on a probabilistic graphical model, which describes the data in terms of underlying evoked and interference sources, and explicitly models the stimulus evoked paradigm. A variational Bayesian EM algorithm infers the model from data, suppresses interference sources, and reconstructs the activity of separated individual brain sources. The new algorithm outperforms existing techniques on two real datasets, as well as on simulated data. 1

3 0.64048547 20 nips-2005-Affine Structure From Sound

Author: Sebastian Thrun

4 0.60835862 25 nips-2005-An aVLSI Cricket Ear Model

Author: Andre V. Schaik, Richard Reeve, Craig Jin, Tara Hamilton

5 0.59481484 174 nips-2005-Separation of Music Signals by Harmonic Structure Modeling

Author: Yun-gang Zhang, Chang-shui Zhang

Abstract: Separation of music signals is an interesting but difﬁcult problem. It is helpful for many other music researches such as audio content analysis. In this paper, a new music signal separation method is proposed, which is based on harmonic structure modeling. The main idea of harmonic structure modeling is that the harmonic structure of a music signal is stable, so a music signal can be represented by a harmonic structure model. Accordingly, a corresponding separation algorithm is proposed. The main idea is to learn a harmonic structure model for each music signal in the mixture, and then separate signals by using these models to distinguish harmonic structures of different signals. Experimental results show that the algorithm can separate signals and obtain not only a very high Signalto-Noise Ratio (SNR) but also a rather good subjective audio quality. 1

6 0.56944293 29 nips-2005-Analyzing Coupled Brain Sources: Distinguishing True from Spurious Interaction

7 0.43770936 1 nips-2005-AER Building Blocks for Multi-Layer Multi-Chip Neuromorphic Vision Systems

8 0.40841588 163 nips-2005-Recovery of Jointly Sparse Signals from Few Random Projections

9 0.40488976 22 nips-2005-An Analog Visual Pre-Processing Processor Employing Cyclic Line Access in Only-Nearest-Neighbor-Interconnects Architecture

10 0.3737953 176 nips-2005-Silicon growth cones map silicon retina

11 0.34262973 113 nips-2005-Learning Multiple Related Tasks using Latent Independent Component Analysis

12 0.31996167 40 nips-2005-CMOL CrossNets: Possible Neuromorphic Nanoelectronic Circuits

13 0.30049998 162 nips-2005-Rate Distortion Codes in Sensor Networks: A System-level Analysis

14 0.27795014 7 nips-2005-A Cortically-Plausible Inverse Problem Solving Method Applied to Recognizing Static and Kinematic 3D Objects

15 0.26338628 101 nips-2005-Is Early Vision Optimized for Extracting Higher-order Dependencies?

16 0.24063861 137 nips-2005-Non-Gaussian Component Analysis: a Semi-parametric Framework for Linear Dimension Reduction

17 0.23896737 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

18 0.22752975 17 nips-2005-Active Bidirectional Coupling in a Cochlear Chip

19 0.21852048 9 nips-2005-A Domain Decomposition Method for Fast Manifold Learning

20 0.21251044 169 nips-2005-Saliency Based on Information Maximization

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(3, 0.031), (6, 0.035), (10, 0.041), (26, 0.384), (27, 0.028), (31, 0.029), (34, 0.056), (47, 0.029), (55, 0.045), (57, 0.015), (65, 0.011), (69, 0.073), (73, 0.022), (88, 0.078), (91, 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.82981211 88 nips-2005-Gradient Flow Independent Component Analysis in Micropower VLSI

Author: Abdullah Celik, Milutin Stanacevic, Gert Cauwenberghs

2 0.73053813 187 nips-2005-Temporal Abstraction in Temporal-difference Networks

Author: Eddie Rafols, Anna Koop, Richard S. Sutton

Abstract: We present a generalization of temporal-difference networks to include temporally abstract options on the links of the question network. Temporal-difference (TD) networks have been proposed as a way of representing and learning a wide variety of predictions about the interaction between an agent and its environment. These predictions are compositional in that their targets are deﬁned in terms of other predictions, and subjunctive in that that they are about what would happen if an action or sequence of actions were taken. In conventional TD networks, the inter-related predictions are at successive time steps and contingent on a single action; here we generalize them to accommodate extended time intervals and contingency on whole ways of behaving. Our generalization is based on the options framework for temporal abstraction. The primary contribution of this paper is to introduce a new algorithm for intra-option learning in TD networks with function approximation and eligibility traces. We present empirical examples of our algorithm’s effectiveness and of the greater representational expressiveness of temporallyabstract TD networks. The primary distinguishing feature of temporal-difference (TD) networks (Sutton & Tanner, 2005) is that they permit a general compositional speciﬁcation of the goals of learning. The goals of learning are thought of as predictive questions being asked by the agent in the learning problem, such as “What will I see if I step forward and look right?” or “If I open the fridge, will I see a bottle of beer?” Seeing a bottle of beer is of course a complicated perceptual act. It might be thought of as obtaining a set of predictions about what would happen if certain reaching and grasping actions were taken, about what would happen if the bottle were opened and turned upside down, and of what the bottle would look like if viewed from various angles. To predict seeing a bottle of beer is thus to make a prediction about a set of other predictions. The target for the overall prediction is a composition in the mathematical sense of the ﬁrst prediction with each of the other predictions. TD networks are the ﬁrst framework for representing the goals of predictive learning in a compositional, machine-accessible form. Each node of a TD network represents an individual question—something to be predicted—and has associated with it a value representing an answer to the question—a prediction of that something. The questions are represented by a set of directed links between nodes. If node 1 is linked to node 2, then node 1 rep- resents a question incorporating node 2’s question; its value is a prediction about node 2’s prediction. Higher-level predictions can be composed in several ways from lower ones, producing a powerful, structured representation language for the targets of learning. The compositional structure is not just in a human designer’s head; it is expressed in the links and thus is accessible to the agent and its learning algorithm. The network of these links is referred to as the question network. An entirely separate set of directed links between the nodes is used to compute the values (predictions, answers) associated with each node. These links collectively are referred to as the answer network. The computation in the answer network is compositional in a conventional way—node values are computed from other node values. The essential insight of TD networks is that the notion of compositionality should apply to questions as well as to answers. A secondary distinguishing feature of TD networks is that the predictions (node values) at each moment in time can be used as a representation of the state of the world at that time. In this way they are an instance of the idea of predictive state representations (PSRs) introduced by Littman, Sutton and Singh (2002), Jaeger (2000), and Rivest and Schapire (1987). Representing a state by its predictions is a potentially powerful strategy for state abstraction (Rafols et al., 2005). We note that the questions used in all previous work with PSRs are deﬁned in terms of concrete actions and observations, not other predictions. They are not compositional in the sense that TD-network questions are. The questions we have discussed so far are subjunctive, meaning that they are conditional on a certain way of behaving. We predict what we would see if we were to step forward and look right, or if we were to open the fridge. The questions in conventional TD networks are subjunctive, but they are conditional only on primitive actions or open-loop sequences of primitive actions (as are conventional PSRs). It is natural to generalize this, as we have in the informal examples above, to questions that are conditional on closed-loop temporally extended ways of behaving. For example, opening the fridge is a complex, high-level action. The arm must be lifted to the door, the hand shaped for grasping the handle, etc. To ask questions like “if I were to go to the coffee room, would I see John?” would require substantial temporal abstraction in addition to state abstraction. The options framework (Sutton, Precup & Singh, 1999) is a straightforward way of talking about temporally extended ways of behaving and about predictions of their outcomes. In this paper we extend the options framework so that it can be applied to TD networks. Signiﬁcant extensions of the original options framework are needed. Novel features of our option-extended TD networks are that they 1) predict components of option outcomes rather than full outcome probability distributions, 2) learn according to the ﬁrst intra-option method to use eligibility traces (see Sutton & Barto, 1998), and 3) include the possibility of options whose ‘policies’ are indifferent to which of several actions are selected. 1 The options framework In this section we present the essential elements of the options framework (Sutton, Precup & Singh, 1999) that we will need for our extension of TD networks. In this framework, an agent and an environment interact at discrete time steps t = 1, 2, 3.... In each state st ∈ S, the agent selects an action at ∈ A, determining the next state st+1 .1 An action is a way of behaving for one time step; the options framework lets us talk about temporally extended ways of behaving. An individual option consists of three parts. The ﬁrst is the initiation set, I ⊂ S, the subset of states in which the option can be started. The second component of an option is its policy, π : S × A ⇒ [0, 1], specifying how the agent behaves when 1 Although the options framework includes rewards, we omit them here because we are concerned only with prediction, not control. following the option. Finally, a termination function, β : S × A ⇒ [0, 1], speciﬁes how the option ends: β(s) denotes the probability of terminating when in state s. The option is thus completely and formally deﬁned by the 3-tuple (I, π, β). 2 Conventional TD networks In this section we brieﬂy present the details of the structure and the learning algorithm comprising TD networks as introduced by Sutton and Tanner (2005). TD networks address a prediction problem in which the agent may not have direct access to the state of the environment. Instead, at each time step the agent receives an observation ot ∈ O dependent on the state. The experience stream thus consists of a sequence of alternating actions and observations, o1 , a1 , o2 , a2 , o3 · · ·. The TD network consists of a set of nodes, each representing a single scalar prediction, interlinked by the question and answer networks as suggested previously. For a network 1 n of n nodes, the vector of all predictions at time step t is denoted yt = (yt , . . . , yt )T . The predictions are estimates of the expected value of some scalar quantity, typically of a bit, in which case they can be interpreted as estimates of probabilities. The predictions are updated at each time step according to a vector-valued function u with modiﬁable parameter W, which is often taken to be of a linear form: yt = u(yt−1 , at−1 , ot , Wt ) = σ(Wt xt ), (1) where xt ∈ m is an m-vector of features created from (yt−1 , at−1 , ot ), Wt is an n × m matrix (whose elements are sometimes referred to as weights), and σ is the n-vector 1 form of either the identity function or the S-shaped logistic function σ(s) = 1+e−s . The feature vector is an arbitrary vector-valued function of yt−1 , at−1 , and ot . For example, in the simplest case the feature vector is a unit basis vector with the location of the one communicating the current state. In a partially observable environment, the feature vector may be a combination of the agent’s action, observations, and predictions from the previous time step. The overall update u deﬁnes the answer network. The question network consists of a set of target functions, z i : O × n → , and condition i y functions, ci : A× n → [0, 1]n . We deﬁne zt = z i (ot+1 , ˜t+1 ) as the target for prediction i 2 i i yt . Similarly, we deﬁne ct = c (at , yt ) as the condition at time t. The learning algorithm ij for each component wt of Wt can then be written ij ij i i wt+1 = wt + α zt − yt ci t i ∂yt , (2) ij ∂wt where α is a positive step-size parameter. Note that the targets here are functions of the observation and predictions exactly one time step later, and that the conditions are functions of a single primitive action. This is what makes this algorithm suitable only for learning about one-step TD relationships. By chaining together multiple nodes, Sutton and Tanner (2005) used it to predict k steps ahead, for various particular values of k, and to predict the outcome of speciﬁc action sequences (as in PSRs, e.g., Littman et al., 2002; Singh et al., 2004). Now we consider the extension to temporally abstract actions. 3 Option-extended TD networks In this section we present our intra-option learning algorithm for TD networks with options and eligibility traces. As suggested earlier, each node’s outgoing link in the question 2 The quantity ˜ is almost the same as y, and we encourage the reader to think of them as identical y here. The difference is that ˜ is calculated by weights that are one step out of date as compared to y, y i.e., ˜t = u(yt−1 , at−1 , ot , Wt−1 ) (cf. equation 1). y network will now correspond to an option applying over possibly many steps. The policy of the ith node’s option corresponds to the condition function ci , which we think of as a recognizer for the option. It inspects each action taken to assess whether the option is being followed: ci = 1 if the agent is acting consistently with the option policy and ci = 0 othert t wise (intermediate values are also possible). When an agent ceases to act consistently with the option policy, we say that the option has diverged. The possibility of recognizing more than one action as consistent with the option is a signiﬁcant generalization of the original idea of options. If no actions are recognized as acceptable in a state, then the option cannot be followed and thus cannot be initiated. Here we take the set of states with at least one recognized action to be the initiation set of the option. The option-termination function β generalizes naturally to TD networks. Each node i is i given a corresponding termination function, β i : O× n → [0, 1], where βt = β i (ot+1 , yt ) i is the probability of terminating at time t.3 βt = 1 indicates that the option has terminated i at time t; βt = 0 indicates that it has not, and intermediate values of β correspond to soft i or stochastic termination conditions. If an option terminates, then zt acts as the target, but if the option is ongoing without termination, then the node’s own next value, yt+1 , should ˜i be the target. The termination function speciﬁes which of the two targets (or mixture of the two targets) is used to produce a form of TD error for each node i: i i i i i i δt = βt zt + (1 − βt )˜t+1 − yt . y (3) Our option-extended algorithm incorporates eligibility traces (see Sutton & Barto, 1998) as short-term memory variables organized in an n × m matrix E, paralleling the weight matrix. The traces are a record of the effect that each weight could have had on each node’s prediction during the time the agent has been acting consistently with the node’s option. The components eij of the eligibility matrix are updated by i eij = ci λeij (1 − βt ) + t t t−1 i ∂yt ij ∂wt , (4) where 0 ≤ λ ≤ 1 is the trace-decay parameter familiar from the TD(λ) learning algorithm. Because of the ci factor, all of a node’s traces will be immediately reset to zero whenever t the agent deviates from the node’s option’s policy. If the agent follows the policy and the option does not terminate, then the trace decays by λ and increments by the gradient in the way typical of eligibility traces. If the policy is followed and the option does terminate, then the trace will be reset to zero on the immediately following time step, and a new trace will start building. Finally, our algorithm updates the weights on each time step by ij ij i wt+1 = wt + α δt eij . t 4 (5) Fully observable experiment This experiment was designed to test the correctness of the algorithm in a simple gridworld where the environmental state is observable. We applied an options-extended TD network to the problem of learning to predict observations from interaction with the gridworld environment shown on the left in Figure 1. Empty squares indicate spaces where the agent can move freely, and colored squares (shown shaded in the ﬁgure) indicate walls. The agent is egocentric. At each time step the agent receives from the environment six bits representing the color it is facing (red, green, blue, orange, yellow, or white). In this ﬁrst experiment we also provided 6 × 6 × 4 = 144 other bits directly indicating the complete state of the environment (square and orientation). 3 The fact that the option depends only on the current predictions, action, and observation means that we are considering only Markov options. Figure 1: The test world (left) and the question network (right) used in the experiments. The triangle in the world indicates the location and orientation of the agent. The walls are labeled R, O, Y, G, and B representing the colors red, orange, yellow, green and blue. Note that the left wall is mostly blue but partly green. The right diagram shows in full the portion of the question network corresponding to the red bit. This structure is repeated, but not shown, for the other four (non-white) colors. L, R, and F are primitive actions, and Forward and Wander are options. There are three possible actions: A ={F, R, L}. Actions were selected according to a ﬁxed stochastic policy independent of the state. The probability of the F, L, and R actions were 0.5, 0.25, and 0.25 respectively. L and R cause the agent to rotate 90 degrees to the left or right. F causes the agent to move ahead one square with probability 1 − p and to stay in the same square with probability p. The probability p is called the slipping probability. If the forward movement would cause the agent to move into a wall, then the agent does not move. In this experiment, we used p = 0, p = 0.1, and p = 0.5. In addition to these primitive actions, we provided two temporally abstract options, Forward and Wander. The Forward option takes the action F in every state and terminates when the agent senses a wall (color) in front of it. The policy of the Wander option is the same as that actually followed by the agent. Wander terminates with probability 1 when a wall is sensed, and spontaneously with probability 0.5 otherwise. We used the question network shown on the right in Figure 1. The predictions of nodes 1, 2, and 3 are estimates of the probability that the red bit would be observed if the corresponding primitive action were taken. Node 4 is a prediction of whether the agent will see the red bit upon termination of the Wander option if it were taken. Node 5 predicts the probability of observing the red bit given that the Forward option is followed until termination. Nodes 6 and 7 represent predictions of the outcome of a primitive action followed by the Forward option. Nodes 8 and 9 take this one step further: they represent predictions of the red bit if the Forward option were followed to termination, then a primitive action were taken, and then the Forward option were followed again to termination. We applied our algorithm to learn the parameter W of the answer network for this question network. The step-size parameter α was 1.0, and the trace-decay parameter λ was 0.9. The initial W0 , E0 , and y0 were all 0. Each run began with the agent in the state indicated in Figure 1 (left). In this experiment σ(·) was the identity function. For each value of p, we ran 50 runs of 20,000 time steps. On each time step, the root-meansquared (RMS) error in each node’s prediction was computed and then averaged over all the nodes. The nodes corresponding to the Wander option were not included in the average because of the difﬁculty of calculating their correct predictions. This average was then 0.4 Fully Observable 0.4 RMS Error RMS Error p=0 0 0 Partially Observable p = 0.1 5000 p = 0.5 10000 15000 20000 Steps 0 0 100000 200000 Steps 300000 Figure 2: Learning curves in the fully-observable experiment for each slippage probability (left) and in the partially-observable experiment (right). itself averaged over the 50 runs and bins of 1,000 time steps to produce the learning curves shown on the left in Figure 2. For all slippage probabilities, the error in all predictions fell almost to zero. After approximately 12,000 trials, the agent made almost perfect predictions in all cases. Not surprisingly, learning was slower at the higher slippage probabilities. These results show that our augmented TD network is able to make a complete temporally-abstract model of this world. 5 Partially observable experiment In our second experiment, only the six color observation bits were available to the agent. This experiment provides a more challenging test of our algorithm. To model the environment well, the TD network must construct a representation of state from very sparse information. In fact, completely accurate prediction is not possible in this problem with our question network. In this experiment the input vector consisted of three groups of 46 components each, 138 in total. If the action was R, the ﬁrst 46 components were set to the 40 node values and the six observation bits, and the other components were 0. If the action was L, the next group of 46 components was ﬁlled in in the same way, and the ﬁrst and third groups were zero. If the action was F, the third group was ﬁlled. This technique enables the answer network as function approximator to represent a wider class of functions in a linear form than would otherwise be possible. In this experiment, σ(·) was the S-shaped logistic function. The slippage probability was p = 0.1. As our performance measure we used the RMS error, as in the ﬁrst experiment, except that the predictions for the primitive actions (nodes 1-3) were not included. These predictions can never become completely accurate because the agent can’t tell in detail where it is located in the open space. As before, we averaged RMS error over 50 runs and 1,000 time step bins, to produce the learning curve shown on the right in Figure 2. As before, the RMS error approached zero. Node 5 in Figure 1 holds the prediction of red if the agent were to march forward to the wall ahead of it. Corresponding nodes in the other subnetworks hold the predictions of the other colors upon Forward. To make these predictions accurately, the agent must keep track of which wall it is facing, even if it is many steps away from it. It has to learn a sort of compass that it can keep updated as it turns in the middle of the space. Figure 3 is a demonstration of the compass learned after a representative run of 200,000 time steps. At the end of the run, the agent was driven manually to the state shown in the ﬁrst row (relative time index t = 1). On steps 1-25 the agent was spun clockwise in place. The third column shows the prediction for node 5 in each portion of the question network. That is, the predictions shown are for each color-observation bit at termination of the Forward option. At t = 1, the agent is facing the orange wall and it predicts that the Forward option would result in seeing the orange bit and none other. Over steps 2-5 we see that the predictions are maintained accurately as the agent spins despite the fact that its observation bits remain the same. Even after spinning for 25 steps the agent knows exactly which way it is facing. While spinning, the agent correctly never predicts seeing the green bit (after Forward), but if it is driven up and turned, as in the last row of the ﬁgure, the green bit is accurately predicted. The fourth column shows the prediction for node 8 in each portion of the question network. Recall that these nodes correspond to the sequence Forward, L, Forward. At time t = 1, the agent accurately predicts that Forward will bring it to orange (third column) and also predicts that Forward, L, Forward will bring it to green. The predictions made for node 8 at each subsequent step of the sequence are also correct. These results show that the agent is able to accurately maintain its long term predictions without directly encountering sensory veriﬁcation. How much larger would the TD network have to be to handle a 100x100 gridworld? The answer is not at all. The same question network applies to any size problem. If the layout of the colored walls remain the same, then even the answer network transfers across worlds of widely varying sizes. In other experiments, training on successively larger problems, we have shown that the same TD network as used here can learn to make all the long-term predictions correctly on a 100x100 version of the 6x6 gridworld used here. t y5 t st y8 t 1 1 O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG O Y R BG 2 3 4 5 25 29 Figure 3: An illustration of part of what the agent learns in the partially observable environment. The second column is a sequence of states with (relative) time index as given by the ﬁrst column. The sequence was generated by controlling the agent manually. On steps 1-25 the agent was spun clockwise in place, and the trajectory after that is shown by the line in the last state diagram. The third and fourth columns show the values of the nodes corresponding to 5 and 8 in Figure 1, one for each color-observation bit. 6 Conclusion Our experiments show that option-extended TD networks can learn effectively. They can learn facts about their environments that are not representable in conventional TD networks or in any other method for learning models of the world. One concern is that our intra-option learning algorithm is an off-policy learning method incorporating function approximation and bootstrapping (learning from predictions). The combination of these three is known to produce convergence problems for some methods (see Sutton & Barto, 1998), and they may arise here. A sound solution may require modiﬁcations to incorporate importance sampling (see Precup, Sutton & Dasgupta, 2001). In this paper we have considered only intra-option eligibility traces—traces extending over the time span within an option but not persisting across options. Tanner and Sutton (2005) have proposed a method for inter-option traces that could perhaps be combined with our intra-option traces. The primary contribution of this paper is the introduction of a new learning algorithm for TD networks that incorporates options and eligibility traces. Our experiments are small and do little more than exercise the learning algorithm, showing that it does not break immediately. More signiﬁcant is the greater representational power of option-extended TD networks. Options are a general framework for temporal abstraction, predictive state representations are a promising strategy for state abstraction, and TD networks are able to represent compositional questions. The combination of these three is potentially very powerful and worthy of further study. Acknowledgments The authors gratefully acknowledge the ideas and encouragement they have received in this work from Mark Ring, Brian Tanner, Satinder Singh, Doina Precup, and all the members of the rlai.net group. References Jaeger, H. (2000). Observable operator models for discrete stochastic time series. Neural Computation, 12(6):1371-1398. MIT Press. Littman, M., Sutton, R. S., & Singh, S. (2002). Predictive representations of state. In T. G. Dietterich, S. Becker and Z. Ghahramani (eds.), Advances In Neural Information Processing Systems 14, pp. 1555-1561. MIT Press. Precup, D., Sutton, R. S., & Dasgupta, S. (2001). Off-policy temporal-difference learning with function approximation. In C. E. Brodley, A. P. Danyluk (eds.), Proceedings of the Eighteenth International Conference on Machine Learning, pp. 417-424. San Francisco, CA: Morgan Kaufmann. Rafols, E. J., Ring, M., Sutton, R.S., & Tanner, B. (2005). Using predictive representations to improve generalization in reinforcement learning. To appear in Proceedings of the Nineteenth International Joint Conference on Artiﬁcial Intelligence. Rivest, R. L., & Schapire, R. E. (1987). Diversity-based inference of ﬁnite automata. In Proceedings of the Twenty Eighth Annual Symposium on Foundations of Computer Science, (pp. 78–87). IEEE Computer Society. Singh, S., James, M. R., & Rudary, M. R. (2004). Predictive state representations: A new theory for modeling dynamical systems. In Uncertainty in Artiﬁcial Intelligence: Proceedings of the Twentieth Conference in Uncertainty in Artiﬁcial Intelligence, (pp. 512–519). AUAI Press. Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction. Cambridge, MA: MIT Press. Sutton, R. S., Precup, D., Singh, S. (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artiﬁcial Intelligence, 112, pp. 181-211. Sutton, R. S., & Tanner, B. (2005). Conference 17. Temporal-difference networks. To appear in Neural Information Processing Systems Tanner, B., Sutton, R. S. (2005) Temporal-difference networks with history. To appear in Proceedings of the Nineteenth International Joint Conference on Artiﬁcial Intelligence.

3 0.44913563 144 nips-2005-Off-policy Learning with Options and Recognizers

Author: Doina Precup, Cosmin Paduraru, Anna Koop, Richard S. Sutton, Satinder P. Singh

Abstract: We introduce a new algorithm for off-policy temporal-difference learning with function approximation that has lower variance and requires less knowledge of the behavior policy than prior methods. We develop the notion of a recognizer, a ﬁlter on actions that distorts the behavior policy to produce a related target policy with low-variance importance-sampling corrections. We also consider target policies that are deviations from the state distribution of the behavior policy, such as potential temporally abstract options, which further reduces variance. This paper introduces recognizers and their potential advantages, then develops a full algorithm for linear function approximation and proves that its updates are in the same direction as on-policy TD updates, which implies asymptotic convergence. Even though our algorithm is based on importance sampling, we prove that it requires absolutely no knowledge of the behavior policy for the case of state-aggregation function approximators. Off-policy learning is learning about one way of behaving while actually behaving in another way. For example, Q-learning is an off- policy learning method because it learns about the optimal policy while taking actions in a more exploratory fashion, e.g., according to an ε-greedy policy. Off-policy learning is of interest because only one way of selecting actions can be used at any time, but we would like to learn about many different ways of behaving from the single resultant stream of experience. For example, the options framework for temporal abstraction involves considering a variety of different ways of selecting actions. For each such option one would like to learn a model of its possible outcomes suitable for planning and other uses. Such option models have been proposed as fundamental building blocks of grounded world knowledge (Sutton, Precup & Singh, 1999; Sutton, Rafols & Koop, 2005). Using off-policy learning, one would be able to learn predictive models for many options at the same time from a single stream of experience. Unfortunately, off-policy learning using temporal-difference methods has proven problematic when used in conjunction with function approximation. Function approximation is essential in order to handle the large state spaces that are inherent in many problem do- mains. Q-learning, for example, has been proven to converge to an optimal policy in the tabular case, but is unsound and may diverge in the case of linear function approximation (Baird, 1996). Precup, Sutton, and Dasgupta (2001) introduced and proved convergence for the ﬁrst off-policy learning algorithm with linear function approximation. They addressed the problem of learning the expected value of a target policy based on experience generated using a different behavior policy. They used importance sampling techniques to reduce the off-policy case to the on-policy case, where existing convergence theorems apply (Tsitsiklis & Van Roy, 1997; Tadic, 2001). There are two important difﬁculties with that approach. First, the behavior policy needs to be stationary and known, because it is needed to compute the importance sampling corrections. Second, the importance sampling weights are often ill-conditioned. In the worst case, the variance could be inﬁnite and convergence would not occur. The conditions required to prevent this were somewhat awkward and, even when they applied and asymptotic convergence was assured, the variance could still be high and convergence could be slow. In this paper we address both of these problems in the context of off-policy learning for options. We introduce the notion of a recognizer. Rather than specifying an explicit target policy (for instance, the policy of an option), about which we want to make predictions, a recognizer speciﬁes a condition on the actions that are selected. For example, a recognizer for the temporally extended action of picking up a cup would not specify which hand is to be used, or what the motion should be at all different positions of the cup. The recognizer would recognize a whole variety of directions of motion and poses as part of picking the cup. The advantage of this strategy is not that one might prefer a multitude of different behaviors, but that the behavior may be based on a variety of different strategies, all of which are relevant, and we would like to learn from any of them. In general, a recognizer is a function that recognizes or accepts a space of different ways of behaving and thus, can learn from a wider range of data. Recognizers have two advantages over direct speciﬁcation of a target policy: 1) they are a natural and easy way to specify a target policy for which importance sampling will be well conditioned, and 2) they do not require the behavior policy to be known. The latter is important because in many cases we may have little knowledge of the behavior policy, or a stationary behavior policy may not even exist. We show that for the case of state aggregation, even if the behavior policy is unknown, convergence to a good model is achieved. 1 Non-sequential example The beneﬁts of using recognizers in off-policy learning can be most easily seen in a nonsequential context with a single continuous action. Suppose you are given a sequence of sample actions ai ∈ [0, 1], selected i.i.d. according to probability density b : [0, 1] → ℜ+ (the behavior density). For example, suppose the behavior density is of the oscillatory form shown as a red line in Figure 1. For each each action, ai , we observe a corresponding outcome, zi ∈ ℜ, a random variable whose distribution depends only on ai . Thus the behavior density induces an outcome density. The on-policy problem is to estimate the mean mb of the outcome density. This problem can be solved simply by averaging the sample outcomes: mb = (1/n) ∑n zi . The off-policy problem is to use this same data to learn what ˆ i=1 the mean would be if actions were selected in some way other than b, for example, if the actions were restricted to a designated range, such as between 0.7 and 0.9. There are two natural ways to pose this off-policy problem. The most straightforward way is to be equally interested in all actions within the designated region. One professes to be interested in actions selected according to a target density π : [0, 1] → ℜ+ , which in the example would be 5.0 between 0.7 and 0.9, and zero elsewhere, as in the dashed line in 12 Probability density functions 1.5 Target policy with recognizer 1 Target policy w/o recognizer without recognizer .5 Behavior policy 0 0 Action 0.7 Empirical variances (average of 200 sample variances) 0.9 1 0 10 with recognizer 100 200 300 400 500 Number of sample actions Figure 1: The left panel shows the behavior policy and the target policies for the formulations of the problem with and without recognizers. The right panel shows empirical estimates of the variances for the two formulations as a function of the number sample actions. The lowest line is for the formulation using empirically-estimated recognition probabilities. Figure 1 (left). The importance- sampling estimate of the mean outcome is 1 n π(ai ) mπ = ∑ ˆ zi . n i=1 b(ai ) (1) This approach is problematic if there are parts of the region of interest where the behavior density is zero or very nearly so, such as near 0.72 and 0.85 in the example. Here the importance sampling ratios are exceedingly large and the estimate is poorly conditioned (large variance). The upper curve in Figure 1 (right) shows the empirical variance of this estimate as a function of the number of samples. The spikes and uncertain decline of the empirical variance indicate that the distribution is very skewed and that the estimates are very poorly conditioned. The second way to pose the problem uses recognizers. One professes to be interested in actions to the extent that they are both selected by b and within the designated region. This leads to the target policy shown in blue in the left panel of Figure 1 (it is taller because it still must sum to 1). For this problem, the variance of (1) is much smaller, as shown in the lower two lines of Figure 1 (right). To make this way of posing the problem clear, we introduce the notion of a recognizer function c : A → ℜ+ . The action space in the example is A = [0, 1] and the recognizer is c(a) = 1 for a between 0.7 and 0.9 and is zero elsewhere. The target policy is deﬁned in general by c(a)b(a) c(a)b(a) = . (2) π(a) = µ ∑x c(x)b(x) where µ = ∑x c(x)b(x) is a constant, equal to the probability of recognizing an action from the behavior policy. Given π, mπ from (1) can be rewritten in terms of the recognizer as ˆ n π(ai ) 1 n c(ai )b(ai ) 1 1 n c(ai ) 1 mπ = ∑ zi ˆ = ∑ zi = ∑ zi (3) n i=1 b(ai ) n i=1 µ b(ai ) n i=1 µ Note that the target density does not appear at all in the last expression and that the behavior distribution appears only in µ, which is independent of the sample action. If this constant is known, then this estimator can be computed with no knowledge of π or b. The constant µ can easily be estimated as the fraction of recognized actions in the sample. The lowest line in Figure 1 (right) shows the variance of the estimator using this fraction in place of the recognition probability. Its variance is low, no worse than that of the exact algorithm, and apparently slightly lower. Because this algorithm does not use the behavior density, it can be applied when the behavior density is unknown or does not even exist. For example, suppose actions were selected in some deterministic, systematic way that in the long run produced an empirical distribution like b. This would be problematic for the other algorithms but would require no modiﬁcation of the recognition-fraction algorithm. 2 Recognizers improve conditioning of off-policy learning The main use of recognizers is in formulating a target density π about which we can successfully learn predictions, based on the current behavior being followed. Here we formalize this intuition. Theorem 1 Let A = {a1 , . . . ak } ⊆ A be a subset of all the possible actions. Consider a ﬁxed behavior policy b and let πA be the class of policies that only choose actions from A, i.e., if π(a) > 0 then a ∈ A. Then the policy induced by b and the binary recognizer cA is the policy with minimum-variance one-step importance sampling corrections, among those in πA : π(ai ) 2 π as given by (2) = arg min Eb (4) π∈πA b(ai ) Proof: Denote π(ai ) = πi , b(ai ) = bi . Then the expected variance of the one-step importance sampling corrections is: Eb πi bi πi bi 2 2 − Eb = ∑ bi i πi bi 2 −1 = ∑ i π2 i − 1, bi where the summation (here and everywhere below) is such that the action ai ∈ A. We want to ﬁnd πi that minimizes this expression, subject to the constraint that ∑i πi = 1. This is a constrained optimization problem. To solve it, we write down the corresponding Lagrangian: π2 L(πi , β) = ∑ i − 1 + β(∑ πi − 1) i i bi We take the partial derivatives wrt πi and β and set them to 0: βbi ∂L 2 = πi + β = 0 ⇒ πi = − ∂πi bi 2 (5) ∂L = πi − 1 = 0 ∂β ∑ i (6) By taking (5) and plugging into (6), we get the following expression for β: − β 2 bi = 1 ⇒ β = − 2∑ ∑i bi i By substituting β into (5) we obtain: πi = bi ∑i b i This is exactly the policy induced by the recognizer deﬁned by c(ai ) = 1 iff ai ∈ A. We also note that it is advantageous, from the point of view of minimizing the variance of the updates, to have recognizers that accept a broad range of actions: Theorem 2 Consider two binary recognizers c1 and c2 , such that µ1 > µ2 . Then the importance sampling corrections for c1 have lower variance than the importance sampling corrections for c2 . Proof: From the previous theorem, we have the variance of a recognizer cA : Var = ∑ i π2 bi i −1 = ∑ bi ∑ j∈A b j i 2 1 1 1 −1 = −1 = −1 bi µ ∑ j∈A b j 3 Formal framework for sequential problems We turn now to the full case of learning about sequential decision processes with function approximation. We use the standard framework in which an agent interacts with a stochastic environment. At each time step t, the agent receives a state st and chooses an action at . We assume for the moment that actions are selected according to a ﬁxed behavior policy, b : S × A → [0, 1] where b(s, a) is the probability of selecting action a in state s. The behavior policy is used to generate a sequence of experience (observations, actions and rewards). The goal is to learn, from this data, predictions about different ways of behaving. In this paper we focus on learning predictions about expected returns, but other predictions can be tackled as well (for instance, predictions of transition models for options (Sutton, Precup & Singh, 1999), or predictions speciﬁed by a TD-network (Sutton & Tanner, 2005; Sutton, Rafols & Koop, 2006)). We assume that the state space is large or continuous, and function approximation must be used to compute any values of interest. In particular, we assume a space of feature vectors Φ and a mapping φ : S → Φ. We denote by φs the feature vector associated with s. An option is deﬁned as a triple o = I, π, β where I ⊆ S is the set of states in which the option can be initiated, π is the internal policy of the option and β : S → [0, 1] is a stochastic termination condition. In the option work (Sutton, Precup & Singh, 1999), each of these elements has to be explicitly speciﬁed and ﬁxed in order for an option to be well deﬁned. Here, we will instead deﬁne options implicitly, using the notion of a recognizer. A recognizer is deﬁned as a function c : S × A → [0, 1], where c(s, a) indicates to what extent the recognizer allows action a in state s. An important special case, which we treat in this paper, is that of binary recognizers. In this case, c is an indicator function, specifying a subset of actions that are allowed, or recognized, given a particular state. Note that recognizers do not specify policies; instead, they merely give restrictions on the policies that are allowed or recognized. A recognizer c together with a behavior policy b generates a target policy π, where: b(s, a)c(s, a) b(s, a)c(s, a) π(s, a) = (7) = µ(s) ∑x b(s, x)c(s, x) The denominator of this fraction, µ(s) = ∑x b(s, x)c(s, x), is the recognition probability at s, i.e., the probability that an action will be accepted at s when behavior is generated according to b. The policy π is only deﬁned at states for which µ(s) > 0. The numerator gives the probability that action a is produced by the behavior and recognized in s. Note that if the recognizer accepts all state-action pairs, i.e. c(s, a) = 1, ∀s, a, then π is the same as b. Since a recognizer and a behavior policy can specify together a target policy, we can use recognizers as a way to specify policies for options, using (7). An option can only be initiated at a state for which at least one action is recognized, so µ(s) > 0, ∀s ∈ I. Similarly, the termination condition of such an option, β, is deﬁned as β(s) = 1 if µ(s) = 0. In other words, the option must terminate if no actions are recognized at a given state. At all other states, β can be deﬁned between 0 and 1 as desired. We will focus on computing the reward model of an option o, which represents the expected total return. The expected values of different features at the end of the option can be estimated similarly. The quantity that we want to compute is Eo {R(s)} = E{r1 + r2 + . . . + rT |s0 = s, π, β} where s ∈ I, experience is generated according to the policy of the option, π, and T denotes the random variable representing the time step at which the option terminates according to β. We assume that linear function approximation is used to represent these values, i.e. Eo {R(s)} ≈ θT φs where θ is a vector of parameters. 4 Off-policy learning algorithm In this section we present an adaptation of the off-policy learning algorithm of Precup, Sutton & Dasgupta (2001) to the case of learning about options. Suppose that an option’s policy π was used to generate behavior. In this case, learning the reward model of the option is a special case of temporal-difference learning of value functions. The forward ¯ (n) view of this algorithm is as follows. Let Rt denote the truncated n-step return starting at ¯ (0) time step t and let yt denote the 0-step truncated return, Rt . By the deﬁnition of the n-step truncated return, we have: ¯ (n) ¯ (n−1) Rt = rt+1 + (1 − βt+1 )Rt+1 . This is similar to the case of value functions, but it accounts for the possibility of terminating the option at time step t + 1. The λ-return is deﬁned in the usual way: ∞ ¯ (n) ¯ Rtλ = (1 − λ) ∑ λn−1 Rt . n=1 The parameters of the linear function approximator are updated on every time step proportionally to: ¯ ¯ ∆θt = Rtλ − yt ∇θ yt (1 − β1 ) · · · (1 − βt ). In our case, however, trajectories are generated according to the behavior policy b. The main idea of the algorithm is to use importance sampling corrections in order to account for the difference in the state distribution of the two policies. Let ρt = (n) Rt , π(st ,at ) b(st ,at ) be the importance sampling ratio at time step t. The truncated n-step return, satisﬁes: (n) (n−1) Rt = ρt [rt+1 + (1 − βt+1 )Rt+1 ]. The update to the parameter vector is proportional to: ∆θt = Rtλ − yt ∇θ yt ρ0 (1 − β1 ) · · · ρt−1 (1 − βt ). The following result shows that the expected updates of the on-policy and off-policy algorithms are the same. Theorem 3 For every time step t ≥ 0 and any initial state s, ¯ Eb [∆θt |s] = Eπ [∆θt |s]. (n) (n) ¯ Proof: First we will show by induction that Eb {Rt |s} = Eπ {Rt |s}, ∀n (which implies ¯ that Eb {Rtλ |s} = Eπ (Rtλ |s}). For n = 0, the statement is trivial. Assuming that it is true for n − 1, we have (n) Eb Rt |s = a ∑b(s, a)∑Pss ρ(s, a) a = s ∑∑ a Pss b(s, a) a s = a ∑π(s, a)∑Pss a (n−1) a rss + (1 − β(s ))Eb Rt+1 |s π(s, a) a ¯ (n−1) r + (1 − β(s ))Eπ Rt+1 |s b(s, a) ss a ¯ (n−1) rss + (1 − β(s ))Eπ Rt+1 |s ¯ (n) = Eπ Rt |s . s Now we are ready to prove the theorem’s main statement. Deﬁning Ωt to be the set of all trajectory components up to state st , we have: Eb {∆θt |s} = ∑ ω∈Ωt Pb (ω|s)Eb (Rtλ − yt )∇θ yt |ω t−1 ∏ ρi (1 − βi+1 ) i=0 πi (1 − βi+1 ) i=0 bi t−1 = t−1 ∑ ∏ bi Psaiisi+1 ω∈Ωt Eb Rtλ |st − yt ∇θ yt ∏ i=0 t−1 = ∑ ∏ πi Psaiisi+1 ω∈Ωt = ∑ ω∈Ωt ¯ Eπ Rtλ |st − yt ∇θ yt (1 − β1 )...(1 − βt ) i=0 ¯ ¯ Pπ (ω|s)Eπ (Rtλ − yt )∇θ yt |ω (1 − β1 )...(1 − βt ) = Eπ ∆θt |s . Note that we are able to use st and ω interchangeably because of the Markov property. ¯ Since we have shown that Eb [∆θt |s] = Eπ [∆θt |s] for any state s, it follows that the expected updates will also be equal for any distribution of the initial state s. When learning the model of options with data generated from the behavior policy b, the starting state distribution with respect to which the learning is performed, I0 is determined by the stationary distribution of the behavior policy, as well as the initiation set of the option I. We note also that the importance sampling corrections only have to be performed for the trajectory since the initiation of the updates for the option. No corrections are required for the experience prior to this point. This should generate updates that have signiﬁcantly lower variance than in the case of learning values of policies (Precup, Sutton & Dasgupta, 2001). Because of the termination condition of the option, β, ∆θ can quickly decay to zero. To avoid this problem, we can use a restart function g : S → [0, 1], such that g(st ) speciﬁes the extent to which the updating episode is considered to start at time t. Adding restarts generates a new forward update: t ∆θt = (Rtλ − yt )∇θ yt ∑ gi ρi ...ρt−1 (1 − βi+1 )...(1 − βt ), (8) i=0 where Rtλ is the same as above. With an adaptation of the proof in Precup, Sutton & Dasgupta (2001), we can show that we get the same expected value of updates by applying this algorithm from the original starting distribution as we would by applying the algorithm without restarts from a starting distribution deﬁned by I0 and g. We can turn this forward algorithm into an incremental, backward view algorithm in the following way: • Initialize k0 = g0 , e0 = k0 ∇θ y0 • At every time step t: δt = θt+1 = kt+1 = et+1 = ρt (rt+1 + (1 − βt+1 )yt+1 ) − yt θt + αδt et ρt kt (1 − βt+1 ) + gt+1 λρt (1 − βt+1 )et + kt+1 ∇θ yt+1 Using a similar technique to that of Precup, Sutton & Dasgupta (2001) and Sutton & Barto (1998), we can prove that the forward and backward algorithm are equivalent (omitted due to lack of space). This algorithm is guaranteed to converge if the variance of the updates is ﬁnite (Precup, Sutton & Dasgupta, 2001). In the case of options, the termination condition β can be used to ensure that this is the case. 5 Learning when the behavior policy is unknown In this section, we consider the case in which the behavior policy is unknown. This case is generally problematic for importance sampling algorithms, but the use of recognizers will allow us to deﬁne importance sampling corrections, as well as a convergent algorithm. Recall that when using a recognizer, the target policy of the option is deﬁned as: c(s, a)b(s, a) π(s, a) = µ(s) and the recognition probability becomes: π(s, a) c(s, a) = b(s, a) µ(s) Of course, µ(s) depends on b. If b is unknown, instead of µ(s), we will use a maximum likelihood estimate µ : S → [0, 1]. The structure used to compute µ will have to be compatible ˆ ˆ with the feature space used to represent the reward model. We will make this more precise below. Likewise, the recognizer c(s, a) will have to be deﬁned in terms of the features used to represent the model. We will then deﬁne the importance sampling corrections as: c(s, a) ˆ ρ(s, a) = µ(s) ˆ ρ(s, a) = We consider the case in which the function approximator used to model the option is actually a state aggregator. In this case, we will deﬁne recognizers which behave consistently in each partition, i.e., c(s, a) = c(p, a), ∀s ∈ p. This means that an action is either recognized or not recognized in all states of the partition. The recognition probability µ will have one ˆ entry for every partition p of the state space. Its value will be: N(p, c = 1) µ(p) = ˆ N(p) where N(p) is the number of times partition p was visited, and N(p, c = 1) is the number of times the action taken in p was recognized. In the limit, w.p.1, µ converges to ˆ ∑s d b (s|p) ∑a c(p, a)b(s, a) where d b (s|p) is the probability of visiting state s from partiˆ ˆ tion p under the stationary distribution of b. At this limit, π(s, a) = ρ(s, a)b(s, a) will be a ˆ well-deﬁned policy (i.e., ∑a π(s, a) = 1). Using Theorem 3, off-policy updates using imˆ portance sampling corrections ρ will have the same expected value as on-policy updates ˆ ˆ using π. Note though that the learning algorithm never uses π; the only quantities needed ˆ are ρ, which are learned incrementally from data. For the case of general linear function approximation, we conjecture that a similar idea can be used, where the recognition probability is learned using logistic regression. The development of this part is left for future work. Acknowledgements The authors gratefully acknowledge the ideas and encouragement they have received in this work from Eddie Rafols, Mark Ring, Lihong Li and other members of the rlai.net group. We thank Csaba Szepesvari and the reviewers of the paper for constructive comments. This research was supported in part by iCore, NSERC, Alberta Ingenuity, and CFI. References Baird, L. C. (1995). Residual algorithms: Reinforcement learning with function approximation. In Proceedings of ICML. Precup, D., Sutton, R. S. and Dasgupta, S. (2001). Off-policy temporal-difference learning with function approximation. In Proceedings of ICML. Sutton, R.S., Precup D. and Singh, S (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artiﬁcial Intelligence, vol . 112, pp. 181–211. Sutton,, R.S. and Tanner, B. (2005). Temporal-difference networks. In Proceedings of NIPS-17. Sutton R.S., Raffols E. and Koop, A. (2006). Temporal abstraction in temporal-difference networks”. In Proceedings of NIPS-18. Tadic, V. (2001). On the convergence of temporal-difference learning with linear function approximation. In Machine learning vol. 42, pp. 241-267. Tsitsiklis, J. N., and Van Roy, B. (1997). An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control 42:674–690.

4 0.3568404 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

Author: Jin Yu, Douglas Aberdeen, Nicol N. Schraudolph

Abstract: Reinforcement learning by direct policy gradient estimation is attractive in theory but in practice leads to notoriously ill-behaved optimization problems. We improve its robustness and speed of convergence with stochastic meta-descent, a gain vector adaptation method that employs fast Hessian-vector products. In our experiments the resulting algorithms outperform previously employed online stochastic, ofﬂine conjugate, and natural policy gradient methods. 1

5 0.34817585 20 nips-2005-Affine Structure From Sound

Author: Sebastian Thrun

6 0.34062093 200 nips-2005-Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery

7 0.3385759 139 nips-2005-Non-iterative Estimation with Perturbed Gaussian Markov Processes

8 0.33187544 132 nips-2005-Nearest Neighbor Based Feature Selection for Regression and its Application to Neural Activity

9 0.33035094 67 nips-2005-Extracting Dynamical Structure Embedded in Neural Activity

10 0.33027542 96 nips-2005-Inference with Minimal Communication: a Decision-Theoretic Variational Approach

11 0.32889184 179 nips-2005-Sparse Gaussian Processes using Pseudo-inputs

12 0.32878113 21 nips-2005-An Alternative Infinite Mixture Of Gaussian Process Experts

13 0.32811844 32 nips-2005-Augmented Rescorla-Wagner and Maximum Likelihood Estimation

14 0.32776564 45 nips-2005-Conditional Visual Tracking in Kernel Space

15 0.32773471 54 nips-2005-Data-Driven Online to Batch Conversions

16 0.32709822 30 nips-2005-Assessing Approximations for Gaussian Process Classification

17 0.32703555 136 nips-2005-Noise and the two-thirds power Law

18 0.32703462 74 nips-2005-Faster Rates in Regression via Active Learning

19 0.32702786 16 nips-2005-A matching pursuit approach to sparse Gaussian process regression

20 0.32621339 98 nips-2005-Infinite latent feature models and the Indian buffet process