System and method for providing digital communications between a head end and a set top terminal5734720Abstract A system and method for scheduling the receipt of desired movies and other forms of data from a network. Feedback paths are provided so that customer's profiles and/or the profiles of the video programs or other data may be modified to reflect actual usage. Secure digital communications between a video head end and a customer's set top terminal in the feedback path is provided by generating, at the video head end, a seed random number N for seeding a random number generator of the customer's set top terminal, encrypting seed random number N using a public key algorithm using a public key P of the video head end to yield encrypted seed random number E(N,P), sending the encrypted seed random number E(N,P) to the customer's set top terminal, decrypting the encrypted seed random number E(N,P) at the customer's set top terminal using a private key of the customer's set top terminal to yield seed random number N, generating a first number for each number i in a sequence K.sub.i at the customer's set top terminal and logically exclusive-ORing the first number in the sequence K.sub.i with a first data word in the decrypted data stream P.sub.i from the video head end, thereby forming a data stream C.sub.i, sending the result C.sub.i from the customer's set top terminal to the video head end, and decrypting C.sub.i to yield a decrypted P.sub.i by logically exclusive-ORing sequence K.sub.i with C.sub.i. Claims We claim: Description BACKGROUND OF THE INVENTION
______________________________________
i customers (i = 1, 2, . . ., I);
j programs (j = i, 2, . . ., J);
k characteristics
(k = 1, 2, . . ., K);
l categories (1 = 1, 2, . . ., L);
______________________________________
and the following variables will be used throughout this specification: cv.sub.ik : customer i's rating for characteristic k; CV.sub.i : the vector {cv.sub.ik .vertline.k.epsilon.K} which forms customer i's profile for all characteristics k; sv.sub.ik : spread (flexibility) in viewer i's rating for characteristic k; wv.sub.ik : customer i's weight of characteristic k; cp.sub.jk : objective weighting of program j for characteristic k; CP.sub.j : the vector {cp.sub.jk .vertline.k.epsilon.K} which forms program j's profile for all characteristics k; sp.sub.jk : spread (flexibility) in program j's rating for characteristic k; and ac.sub.ij : agreement scalar representing similarity between CV.sub.i and CP.sub.j. It should be noted at the outset that cv.sub.ik indicates customer i's preferred level for characteristic k, while cp.sub.jk indicates the level of presence of a characteristic in the program. sv.sub.ik and sp.sub.jk, on the other hand, respectively represent customer i's flexibility in accepting different levels of characteristic k and the flexibility in the determination of the degree of content of characteristic k in program j. cv and cp may have values between 0 and +10, where the actual range number indicates the relevance of that characteristic. In other words, a video programming having a value of +10 for a given characteristic has the highest degree of content for that variable. The values of cv and cp should always be non-negative, since both are related to the level of characteristics, the former being the desired level and the latter being the actual level. Naturally, zero in cv means the customer's rejection of a characteristic, while zero in cp indicates the absence of a characteristic in a program. Those skilled in the art may wish to allow cv to become negative so that the magnitude of negativity could indicate the level of the customer's aversion to a characteristic. However, there are drawbacks in using negative values in this manner. First, a negative value will blur the meaning of cv and sv and weaken the statistical basis for their calculation. Second, cv has been defined as the desired level of a characteristic, which should be non-negative. Thus, the level of aversion is preferably expressed as a point value, instead of a range of values. Preferably, the level of aversion is expressed by the combination of a zero-value in cv and a certain value in the corresponding wv. For example, when customer i totally rejects characteristic k, cv.sub.ik can be set to -1, which means prohibition. Any program k for which cv.sub.ik <0 will be excluded from the recommendation list for customer i. Of course, as in the Strubbe system, the values could simply be "0" or "1" to indicate the presence or absence of a characteristic. wv.sub.ik illustrates the importance of characteristic k to customer i. Typically, different characteristics bear different levels of importance for a customer, and the introduction of this variable catches the variation. Although any scaling system may be used, the weight variable, wv, may simply weight the associated characteristic on a scale of 0-5, where 5 indicates the highest affinity for the associated characteristic. On the other hand, as in the Strubbe system, the weights could simply indicate a "like" or "dislike" value for each characteristic. Finally, as will be described in more detail below, the agreement scalar for characteristics, ac, is the weighted average of the values of a variant of the two-sample t test for significance between CV and CP. B. Creating Initial Customer and Content Profiles A profile, either of a customer (Customer Profile) or of a program (Content Profile), is composed of arrays of characteristics which define the customer profile vector CV.sub.i and the program profile vector CP.sub.j. To increase the accuracy in statistical estimation, the selection of the characteristics should follow the following guidelines: The characteristics should be descriptive of the features of the programs; The list should be fairly inclusive, i.e., include all the common features of the programs; and There should be no synonyms, nor much overlapping in meaning between two or more characteristics. In other words, the correlations between the characteristics are desirably minimized. For example, characteristics currently in use for characterizing video programming include film genres such as westerns, comedies, dramas, foreign language, etc. as defined by the American Film Institute and/or as provided via existing television database services; directors; actors/actresses; attributes such as amount and degree of sex, violence, and profanity; MPAA rating; country of origin; and the like. Of course, many other characteristics may be used, such as those characteristics used in the Minnesota Psychological Test or other more particularized categories based on life experiences and emotions. Such characteristics may also be value based by indicating the scientific, socio-political, cultural, imagination evoking, or psychological content as well as the maturity level to which the program appeals. In accordance with the invention, there are several ways to develop the initial customer and content profiles for such characteristics. For example, the initial customer profile may be assigned on the basis of the customer's zip code or other characteristic demographic information. In other words, the profile may be set to a profile typical of the customer's zip code area or to a typical profile determined by interviews or empirically by monitoring what customers watch. Similarly, each customer may be assigned a generic customer profile which is personalized over time through the profile adjustment techniques to be described below. Alternatively, a customer may be asked to name several of his or her favorite movies and television shows so that an initial customer profile may be determined by combining or averaging the content profiles of the selected movies and television shows. In addition, each customer may complete a ballot for each viewing mood. This latter approach builds upon the technique described by Hashimoto in U.S. Pat. Nos. 4,745,549 and 5,075,771 and will be described in some detail here. For explanation purposes, it will be assumed that the initial customer profile is determined from an initial customer questionnaire or ballot. When completing the initial questionnaire, the customer may choose between two voting schemes, one (Scheme A) by characteristics, and the other (Scheme B) by categories. Scheme A is straight-forward. In Scheme A, the customer gives acceptable ranges for all the characteristics which identify a video program. The customer's profile {cv.vertline.cv.epsilon.CV} is immediately obtained by simply calculating the means of these ranges. In Scheme B, however, the customer gives a specific rating for each of the categories. If ccv.sub.il is the rating for customer i for category l, with a scale of 10 in which zero means least satisfaction with the category and 10 means the greatest satisfaction, the customer's profile {cv.sub.ik .vertline.cv.sub.ik .epsilon.CV.sub.i } may be calculated as: cv.sub.ik =1/N.sub.L,*.SIGMA..sub.l,cc.sub.kl,(1'.epsilon.L') Equation (1) where L' is the set of categories in which ccv.sub.il =max.sub.l ccv.sub.il, and N.sub.L, is the cardinality of L'. In other words, a customer's rating of a characteristic equals the objective content rating of that characteristic in the customer's most preferred category. If there are multiple most-preferred categories, indicated as ties in ccv, the objective content ratings can be used. Alternatively, the customer may be required to input an upper limit cvu.sub.ik and a lower limit cvl.sub.ik for characteristic k to show his/her acceptable range for characteristic k, where cv.sub.ik is calculated as: cv.sub.ik =(cvu.sub.ik +cvl.sub.ik)/2 Equation (2) i.e., the middle point of the range. If customer i wants to indicate his/her indifference to characteristic k, i.e., that he/she can accept any level of characteristic k, then he/she may either let cvu.sub.ik =10 and cvl.sub.ik =0, or let wv.sub.ik =0. The initial value for cp.sub.jk is calculated as the mean of all votes on that characteristic by "experts" or other viewers used to characterize the video programs. As will be noted below, initial profiles for video programs may be obtained by using a panel of experts or customers to assign content profiles or by assigning the customer profiles to the video programs on the basis of those who liked the video program during a test screening. On the other hand, the initial value for sv.sub.ik is calculated as: sv.sub.ik =(cvu.sub.ik -cvl.sub.ik)/Z, Equation (3) where Z preferably equals 2. The calculation simulates that for standard deviation, where the cutting point for rejection in normal distribution is usually when the divisor Z=2. Accordingly, cv is of point value, and sv is of range value. Thus, while the value of the divisor Z in Equation (3) may be altered to tighten/loosen the cutting point, the divisor in Equation (2) may not be changed. sp, on the other hand, may be calculated as the standard deviation in the experts' or test group's votes on cp. The major advantage of Scheme B is that much burden will be taken away from the customer in the ballot completion process, since as a rule, the number of characteristics well exceed the number of categories. The disadvantage, however, is the inaccuracies due to the fact that not all the characteristics in the customer's favorite category are on the customer's most preferred level. The inaccuracy may be reduced by expanding the most-preferred categories to those with ccv values in a certain upper percentile, rather than with the maximum ccv values. The value of sv can be derived from the deviation of ccv's in the customer's most-preferred categories. To help the customers vote more consistently, each category is preferably accompanied by a list of keywords (i.e., characteristics that are relevant to the category). Similarly, the content profile may be determined using questionnaires completed by a panel of experts or customers who determine the content of all video programming available for broadcast. The same scaling systems would be used as for the customer profiles. For statistical purposes, it is desired that the expert or customer panel be as large as possible. As will be noted below, once the system of the invention is in operation, the customer profiles of those who actually watch a particular video program during an initial screening by a sample group may be used to assign a content profile to that program for subsequent viewings. In such a system, those customers who watch the program from beginning to end will be presumed to have "liked" the program. The customer profiles of those who "liked" the program would then be combined to create the initial profile for that program. That program would then be ready for broadcast to all members of the network. Alternatively, in the presently preferred embodiment, more sophisticated techniques are used to generate the initial content profiles. In the preferred embodiment, the content profile of a program is determined automatically from the word frequency of certain words in the text or on-line description of a program or the frequency of certain words in the closed captions of a television show, where such words are chosen as representative of certain categories. Of course, other simpler techniques such as one which simply determines the presence or absence of particular characteristics may be used within the scope of the invention. The weighting of the characteristics in the customer and content profiles somewhat depends on how the profiles were determined initially. For example, the weighting of the customer profiles may be obtained directly from a questionnaire by asking the customer to appropriately scale (from 1-10) his or her preference for each characteristic. On the other hand, if the customer profile is assigned based on demographics, zip code, and the like, the average weights for other customers with the same demographics, zip code, and the like may be used. When more statistical techniques are used for creating the initial customer and content profiles, the weights may be determined mathematically as, for example, the reciprocal of the standard deviation of the characteristics. Of course, other weighting techniques may also be used. C. Adjusting Customer Profiles As noted above, the data from which the initial customer profile is derived may be obtained through ballot filling, whereby a number of characteristics are listed and the customer gives his/her preference rating (cv) and flexibility range (sv) for each characteristic. However, people often do not provide all of the necessary responses or the correct responses to such ballots or questionnaires. Similarly, when the initial customer profiles are assigned to new customers on the basis of demographics and the like, there is a substantial likelihood that the initial customer profile will need considerable adjustment. Moreover, the system should account for the fact that many people's tastes change over time. Thus, to ensure accuracy of the profiles, there must be some way to correct errors in the initial customer profiles and to adjust the customer profiles over time. In accordance with the invention, a passive feedback technique is provided whereby the programming viewed by the customers are automatically monitored and used to adjust the customer profiles. That technique will be described in more detail in Section V below. This section will instead refer to an active feedback mechanism which will be referred to as a "rave review." As noted above, one way to establish an initial customer profile is to show an unrated program or portion of a program to a target audience and to assign to the unrated program a combination of the customer profiles of those who actually watched the program or portion of the program from beginning to end or to assign ratings inputted by those who completed a survey. A similar technique may be used for error correction or for creating initial customer profiles. In particular, the customer is exposed to a series of short sections of different video programs. Each section is characterized by a few characteristics, and the assigned characteristic level of each of the characteristics is presented to the customer. The customer is then asked to state his/her most preferred level for the characteristic given the assigned characteristic level for the viewed section of the video program. For instance, if the level of "action" in a section of the movie "First Blood" is assigned a value of 8, the customer may give 4-6 as his/her acceptance range. On the other hand, if the customer strongly disagrees with the assigned characteristic level, he/she may provide his/her own estimation of the level of the characteristic in the presented program section and give his/her acceptance accordingly. Of course, the major advantage of such a "rave review" procedure over ballot completion is that instead of voting on an abstract concept, the customer now makes estimations based on concrete examples. Since the customer may not be able to remember exactly his/her preferred level of a characteristic that he/she indicated in a previous review or in an original ballot or may not have known his or her assigned initial value for a characteristic, he/she may intentionally or involuntarily repeat the same level for the same characteristic in one review if that characteristic appears in more than one program section, even if that characteristic should not have the same level. Therefore, in a "rave review" a program section with a large variety of characteristics should be selected to avoid repetitions of the same characteristic across several video clips. In addition, the customer should be advised that while making level estimations he/she should concentrate on the features of the current program sections and forget his/her previous ratings. As mentioned above, changes in a customer profile should be expected over time. In other words, the values of cv and sv obtained from the rave reviews typically will be different from the values specified in the original ballot and during previous rave reviews. In order to avoid dramatic changes in the values, the setting of the new values should take into consideration both the old and the new data. Thus, if x represents either cv or sv, x.sup.n is the value of x after period n (n "rave review" changes), and y.sup.n is the value obtained during time n, then: x.sup.n =y.sup.n when n=1 Equation (4) and x.sup.n =x.sup.n-1 +(1/n)(y.sup.n-1 -x.sup.n-1) when n>1. Equation (5) Each y is obtained either from the customer's ballot or rave review, but typically y.sup.1 is from the ballot data, and y.sup.l, 1>1, is from the rave review data. From the above equations, it follows that: x.sup.n =(1/n).SIGMA..sub.l y.sup.l, Equation (6) i.e., the new value of x after the n iterations is equal to the average of all the n-1 previous data. The method is formally termed MSA, or Method of Successive Average. With this method, data at each iteration is equally accounted for in the final value. Any dramatic changes will be damped down, especially at later iterations (when n is large). This approach agrees with intuition, since a customer's profile should stabilize over time. However, customers may have systematic bias in estimating their preferences. For instance, a customer may constantly underestimate or overestimate his/her preference rating for a characteristic. One way to detect the inaccuracy is to check if there are some customers who, when viewing various programs in rave reviews, constantly disagree with the content profile value for a particular characteristic and suggest disproportionately higher/lower ratings. If frequently the t values in the t significance test turn out to be insignificant despite their agreement, then it may be necessary to adjust the customers' ratings of the characteristic in question in the direction opposite to their suggestions. Another way to make adjustments to the customers' combined ratings is through the clustering of customers. Customers are asked to give overall ratings for various programs. If a group of customers come up with very similar ratings for most of the programs in a category, it is assumed that the actual acceptance ranges for these customers for each characteristic relevant to the category forms a narrow distribution, i.e., their values are close to each other. However, if in the distribution of stated ratings, some outside values which are far away from the majority are seen, then the indication is that these outside values need to be adjusted. There are many algorithms to find outsiders in a population. For instance, all the values may be sorted in the ascending order of their absolute distances from the mean, and gaps searched for at the lower end. Those values that are located below the largest gap would be outsiders. For statistical validity, the mean and standard deviation of the population less the outsiders may be calculated and a t significance test conducted to determine if any of the outsiders belong to the population. Only those that do not belong will be subject to adjustment. D. Adjusting Content Profiles As discussed above, in a rave review, the customer may state his/her disagreement with the rating of a characteristic in a video program and put forward his/her own rating for each characteristic in the program. This provides a mechanism for adjustment of the content profiles. In general, the present invention may use the ratings of experts or test groups as the reference base. Generally, the calculation of the agreement scalar ac is based on the values of cp and sp. Since the values of cp and sp are used in calculating ac for all customers, any inaccuracy in their values will affect the final results for all customers. (By contrast, an inaccuracy in the value of a customer's cv and sv only affects the results for that customer.) By definition, customers collectively make ratings relatively closer to reality than any experts or test groups. In other words, the customer's rating is reality. For instance, if all the customers on the average tend to overestimate a particular characteristic (for one or all programs), then the experts' or test groups' objective ratings for that characteristic (for one or all programs) should be raised to agree with the customers' perceptions. Again, MSA may be used for the content profile adjustment, letting x be either cp or sp and letting y.sup.n be the value collectively suggested in period n by the customers for the variable, where y.sup.n is defined as: y.sup.n =(1/I).SIGMA..sub.i y.sup.n.sub.i, Equation (7) where y.sup.n.sub.i is the value suggested by customer i during period n. By substituting y in Equation (5) into Equation (4), the x.sup.n+1 value may be calculated. For customers who do not state disagreement, their y.sup.n.sub.i may be set to x.sup.n, i.e., the original content profile. Therefore, y.sup.n is the average of the customers' suggested value at period n. The resultant x.sup.n+1 is the adjusted content profile after period n. This method would be less useful if only the content profiles of a characteristic for individual programs may be adjusted. Often, the relative bias is systematic, i.e., as seen from the customer's side, the characteristic values may underestimate or overestimate the significance of a characteristic for programs of certain or all categories. This problem can also be addressed as follows. For clarity in discussion, subscripts again will be used. y.sub.jk is the customers' average suggested rating for characteristic k for program j. The distribution of the customers' ratings is assumed to be normal. For simplicity, time subscripts are dropped. A t value significance test is then conducted as: ##EQU1## and where: t.sub.jk is the t value for significance of difference between the customers' suggested rating of characteristic k for program j and the corresponding assigned objective rating; s.sub.Yjk-CPjk is the standard deviation between the distribution of Y.sub.jk and that of cp.sub.jk ; I is the total number of customers; and M is the total number of "experts." If t.sub.jk is significant for a pre-defined level (say 0.05) with degree of freedom of I+M-2, then cp.sub.jk is determined to be significantly different from y.sub.jk. In that case, an adjustment in cp.sub.jk is necessary, and MSA is calculated to obtain the new cp.sub.jk from y.sub.jk. With the above method, only the assigned objective rating of a characteristic for individual programs is adjusted. In order to adjust the assigned objective ratings of a characteristic for all the programs in a category, the following is used: T.sub.lk =(1/J.sub.l).SIGMA..sub.j.sbsb.l t.sub.j-lk Equation (10) where: T.sub.lk is the average of the t values for characteristic k in all the programs for category l; t.sub.j-lk is the t value for significance of the difference between the customers' suggested rating of characteristic k for program j.sub.l and the corresponding objective rating; and J.sub.l is the number of programs in category l. If an adjustment of the assigned objective rating of a characteristic over several or all categories is desired, the t values of an even wider range are averaged. For instance, if it is necessary to make an adjustment for all categories, calculate: T.sub.k =(1/L*.SIGMA..sub.l J.sub.l).SIGMA..sub.l .SIGMA..sub.j-l t.sub.j-lk, Equation (11) where: T.sub.k is the average of the t values for characteristic k in all programs. When a content profile value cp is changed to cp', it is also necessary to change the corresponding sp (deviation in cp) to sp'. Because there is a distribution in cp, there must be some expert(s) whose rating(s) is below or above the mean (cp). If through the above calculation cp overestimates/underestimates reality, it is assumed that only those experts whose ratings are above/below the mean made an overestimation/underestimation. Therefore, after the adjustment, the new deviation sp' should be smaller than sp. One possible calculation of sp' is: sp'=sp/(1+.alpha.*.vertline.cp'-cp.vertline./cp) Equation (12) Since cp>0, sp'<sp (i.e., sp always declines after adjustment). If .alpha.=1, cp=3, cp'=4, and sp=1, then sp'=0.75. The parameter .alpha. thus determines the rate of decreasing in sp with the rate of change in cp. It should be pointed out that before making actual changes to content profiles determined by experts or test groups, it is desirable to consult with the experts or test groups for the proposed changes. That will not only preclude any unreasonable changes, but also will reduce possible future bias by the experts or test groups. E. Customer Moods and Time Windows Few people are purely single minded, especially when enjoying entertainment. Besides a generic propensity, it is therefore reasonable to assume that each customer could have one or more viewing moods, and in each of the moods he/she would like to watch a particular set of program categories. For normal and not highly capricious people, the moods should be time-specific, i.e., each mood has a time window, within which the mood is effective. On the other hand, people are not free all the time. The time when they can enjoy entertainment is limited. The time window concept can be used to represent this temporal limitation as well. Thus, each time window can be expressed as a pair of time variables, l and u, where l is the starting point of the window and u is the ending point of the window. Customer profiles used in accordance with the preferred embodiment of video scheduling preferably incorporate this concept of moods and time windows. In the present invention, each customer preferably has a generic mood and may also have some specific moods. Both generic moods and specific moods may or may not be time-specific. In fact, a non time-specific mood can also have a time window, only with l=u, i.e., its window covers the whole day. Typically, for a particular customer, the time window for his/her generic mood will have the greatest width, and the width of the windows for his/her specific moods will decrease with an increase in specification. In this sense, all the moods of a customer form a tree, in which the generic mood is the root, and a specific mood becomes the child of another mood if the former's window is contained in the latter's window. For example, if a customer has four moods: generic, peaceful, violent, speculative, the generic mood may cover all times, the violent mood may cover 6 a.m. to noon, the peaceful mood 6 p.m. to midnight, and the speculative mood from 8 p.m. to midnight. Thus, the speculative mood is a child (subset) of the peaceful mood. The mood at the lowest (most specific) level of the hierarchy is generally used to develop the program list for the customer (described below). The definition of moods can be the responsibility of the customer. When ballots are used to create the initial customer profiles, each ballot may correspond to a mood. In other words, a mood may be equivalent to a customer profile. The generic mood or generic customer profile is required unless there is an automatic system default mood or profile. Beyond that, the customer can fill out as many ballots as he/she likes to establish specific moods. A satisfaction factor, sf, is attached to each mood. For the generic mood, sf=1, which is the base. sf increases as the time window narrows since it is reasonable to believe that people get greater satisfaction as their more specific requirements are met. sf is either determined by the customer or takes a default value. For instance, the system may set a maximum value on sf for the most specific window, which is two hours wide, and do a linear interpolation to find the sf values for windows of greater widths. If the customer provides the sf values for his various mood windows, the values will be normalized in light of the base value of one and the above-mentioned system-set maximum value. With the introduction of time windows, each customer i (or customer-mood i, to be more accurate) will take on time window superscripts as i.sup.l.sbsp.--.sup.i,u.sbsp.--.sup.i, while each program j will become j.sup.l.sbsp.--.sup.j,u.sbsp.--.sup.j, where l.sub.j is the starting time of program j and u.sub.j is the ending time of program j. The calculation of the agreement scalar ac then proceeds as will be described in the next section. However, the calculation of as, the final objective value, becomes: as.sub.ij =sf.sub.i *›wc.sub.i *ac.sub.ij -wf*f(l.sub.i,u.sub.i,l.sub.j,u.sub.j)!, Equation (13) where f(l.sub.i,u.sub.i,l.sub.j,u.sub.j) gives a punishment value expressing the customer's dissatisfaction due to the mismatch between the time window of customer-mood i and the broadcast time of program j, sf.sub.i is the normalized satisfaction factor of customer-mood i, wc.sub.i is the weight for the existing agreement scalar, and wf is the weight for f, which needs to be determined through practice. The major issue here is the form of the punishment function f. Intuitively, f=0 when the mood window contains the broadcast window, i.e., l.sub.i .ltoreq.l.sub.j, and u.sub.i .gtoreq.u.sub.j, and f increases as the two windows move away from each other. Since u.sub.i -l.sub.i .gtoreq.u.sub.j -l.sub.j, i.e., the mood window is not narrower than the broadcast window, the time discrepancy d between the two windows may be expressed as: d=max(0,l.sub.i -l.sub.j,u.sub.j -u.sub.i), Equation (14) So f=f(d). It is reasonable to expect that the customer's dissatisfaction increases rather sharply when the mismatch of the time windows first begins, which means he/she will miss some part of the program. But when the time mismatch increases further, the customer's discontent will level off. For example, the customer will feel quite upset if he/she misses the beginning ten minutes of a program which he/she likes. However, if he/she has already missed the first one hour and a half, his/her dissatisfaction will not increase much if he/she misses the remaining half an hour. This non-linear relationship can be well expressed by the following negative exponential equation: f(d)=.alpha.(l-e.sup.-.beta.d), Equation (15) where .alpha. is the maximum dissatisfaction that a customer could have for missing a program, and .beta. is a parameter which determines how sharply f(d) increases with d. The greater the value of .beta., the steeper the curve would be. It can be seen through Equation (15) that f(d)=0 when d=0, and f(d)=.alpha. when d=.infin.. Thus, the punishment function becomes: f(l.sub.i,u.sub.i,l.sub.j,u.sub.j)=.alpha.(1-exp(max(0,l.sub.i -l.sub.j,u.sub.j -u.sub.i))). Equation (16) Given the form of Equation (13), .alpha. may be set to one since the extent of dissatisfaction can be adjusted by the weight parameter wf. III. Calculation of Agreement Matrix The calculated agreement scalars, ac, form an agreement matrix, AC, which provides measurements of the similarity between the customer profiles and the content profiles. Its calculation incorporates the desired amounts of the various characteristics used to define the programs, their importance (weights) to each customer, and the amounts of these characteristics present in each program as determined by experts or test groups. Assuming there are I customers, J programs, K characteristics, and M experts, then each cell in the initial agreement matrix (agreement scalar for cv.sub.ik and cp.sub.jk) may be calculated as: ##EQU2## and: ac.sub.ij : agreement scalar between the profiles of customer i and that of program j; t.sub.ijk : t value for significance of difference between the rating of characteristic k in customer i and that in program j; s.sub.CVik-CPjk : standard deviation between the distribution of cv.sub.ik and that of cp.sub.jk ; W.sub.i : .SIGMA..sub.k wv.sub.ik, i.e., the sum of all weights for customer i; M: number of "experts" who rate program j; and N: number of times of consideration before the customer reaches a final decision on the rating for cv. The magnitude of each of the t values shows the deviation of the customer's ratings of a characteristic from that of the video program given the distributions of the ratings by both the customer and the experts or test group. If the t value is significant at a predetermined level of significance, e.g., 0.05 for degree of freedom of 2M-2, then the two distributions could be regarded as belonging to the same population. The average of all the t values can serve as an indicator of the divergence (distance in characteristic space) between the profile of the customer and that of the program. Therefore, the variable ac, which is basically the reciprocal of the average of the t values (reciprocal of the distance), exhibits the level of agreement between the two profiles. Thus, ac.epsilon.(0,1) and reaches its maximum value of 1 (perfect agreement) only when .SIGMA..sub.k wv.sub.ik *t.sub.ijk =0 or wv.sub.ik *t.sub.ijk =0 (i=1, 2, . . . , I; j=1, 2, . . . , J; k=1, 2, . . . , K) since wv.sub.ik >=0 and t.sub.ijk >=0. In other words, perfect agreement will be met only when there is no difference between the customer profile and the content profile, or when there are differences only on certain characteristics and the customer ignores those characteristics. As a result, sorting all the programs in the ascending order of ac renders a recommendation list of programs for the customer. In the original formulation of the t significance test, both M and N are the sample sizes. While M is the number of experts or members in the test group, N represents the number of times of consideration before the customer reaches his/her final decision on the rating for cv. N's value may be determined empirically through experiments. Generally speaking, the higher N's value, the lower the flexibility in the customer's acceptance for various characteristics on average. Preferably, N=M-1 so that dispersions in cv, which is interpreted as the customer's acceptance range, and in cp, which represents the difference in the experts' voting, are equally counted. This calculation is underpinned by the assumption that both the distributions of the experts' vote and the customer's rating are normal (Gaussian). Although the assumption is not guaranteed, that is the best that can be hoped for. Once the initial customer profiles and initial content profiles have been established, a simpler form of Equation (17) may be used by combining wv and s into a single measure of importance: ##EQU3## where sv.sub.ik is the spread in customer i's rating for characteristic k (inversely correlated with the importance of k to i), and sp.sub.jk is the spread in the experts' ratings for characteristic k. Thus: ac.sub.ij =l/›l+.SIGMA..sub.k w.sub.ik .vertline.cv.sub.ik -cp.sub.jk .vertline.!, Equation (21) This simpler notation is preferred and will be used throughout the discussion below. However, the algorithms described below are all easily extended to the more complex model of Equation (17). Generally, the more complex form of the agreement matrix (Equation (17)) is only preferred when the customers are asked questions to build their customer profiles. The simpler form of the agreement matrix (Equation (21)) is preferred when the profiles are initialized using demographics and updated using passive monitoring, as in the presently preferred implementation of the present invention. For purposes of illustration, a calculation of a simple agreement matrix will be described here. It is assumed that there are only two customers: (1) John and (2) Mary. Their sample customer profiles are as follows:
______________________________________
romance high-tech
violence
______________________________________
characteristic (cv):
1 John 3.0 9.0 7.0
2 Mary 9.0 3.0 0.0
standard deviation (sv):
1 John 1.0 2.0 1.0
2 Mary 1.0 0.5 0.0
weight (wv):
1 John 2.0 9.0 5.0
2 Mary 8.0 3.0 7.0
______________________________________
The available programs are as follows:
______________________________________
Program Titles
______________________________________
1 Star Trek
2 Damnatian Alley
3 Forever Young
4 Terminator II
5 Aliens
6 Fatal Attraction
______________________________________
The sample content profiles are as follows:
______________________________________
romance
high-tech
violence
______________________________________
char. (cp):
program
1 Star Trek 2.0 9.0 4.0
2 Damnation Alley 5.0 0.0 1.0
3 Forever Young 8.0 3.0 0.0
4 Terminator II 0.0 10.0 8.0
5 Aliens 0.0 8.0 9.0
6 Fatal Attraction
7.0 0.0 8.0
standard deviation (sp):
program
1 Star Trek 0.5 1.0 1.0
2 Damnation Alley 1.0 0.0 1.0
3 Forever Young 1.0 0.5 0.0
4 Terminator II 0.0 1.0 1.5
5 Aliens 0.0 1.0 1.0
6 Fatal Attraction
2.0 0.0 1.0
______________________________________
After normalizing w using: ##EQU4## where s.sub.CVik-CPjk is defined in Equation (19), the above input data produces the following weight matrix (w):
______________________________________
characteristic:
romance high-tech
violence
______________________________________
customer
1 John .166 .425 .409
2 Mary .292 .192 .516
______________________________________
Given the weight matrix and the characteristic profiles of the customers and the programs, the agreement matrix may be calculated. For example, the agreement scalar between customer 1 and program 2 is: ##EQU5## The final agreement matrix (AC) is thus:
______________________________________
Program 1 2 3 4 5 6
______________________________________
Customer
1 John .418 .131 .138 .429 .365 .170
2 Mary .160 .307 .774 .110 .108 .159
______________________________________
From the agreement matrix, it is evident that John prefers "Star Trek", "Terminator II", and "Aliens", while Mary prefers "Forever Young" and "Damnation Alley". This is the results that would have been expected from the profiles, only here the preferences have been quantified. Of course, in the simple case where merely the presence or absence of particular characteristics are measured, the agreement matrix would look for identity in the most categories rather than the distance between the customer profile vector and the content profile vector using the techniques described above. IV. Scheduling Video Delivery in Accordance with Customer and Content Profiles The introduction of time dimensions makes possible the scheduling of video programs, i.e., the assignment of programs to days and to time slots in accordance with each customer profile. A. Scheduling Constraints Solving the problem of assigning days and time slots simultaneously is often impractical because of the exponential increasing order in the number of possible combinations. Therefore, the two tasks are preferably performed separately through heuristic methods. The first task, assigning programs to days, is simplified significantly by the fact that in the present system the customers' preferences are differentiated mostly by time slots (hours), rather than by days. When the customer defines weekday mood time windows, it is assumed that the window will apply to any weekday. Of course, the customer may define some weekend time windows, which apply to either Saturday or Sunday. Therefore, for a given set of programs available for a week, the major question is not on which day to broadcast them, but during which hours to broadcast them. A possible approach to scheduling is that for each program its top n most-preferred broadcast windows are determined from the average of the objective values as calculated using Equation (13). The scheduler then uses some methods to find a solution in which the average objective value reaches a reasonably high value, and in which the time slots are covered. There are many such methods available, such as integer linear programming. An extra complexity is the possible necessity of repeating some programs during a day or a week, because of their high popularity. A simple approach is to let the scheduler first determine the number of necessary repetitions, and then add the number in as constraints in the programming. However, it should be noted that the above approach is for just one channel. If there are multiple channels, then it is usually necessary to first categorize the channels, find their respective "target audience", and then run the scheduling procedure on the target audience of each channel. Attention should also be paid to the mutual exclusion among the overlapping time windows of a customer. Although the customer may define time windows which conflict with each other, in terms of overlapping and containment, only one of the windows in the conflicting set can be used in the final assignment. This condition should be added to the constraints. B. Scheduling Algorithm With the above scheduling constraints in mind, the present inventors have developed an algorithm which uses customer profiles and content profiles for scheduling the broadcast of movies and other shows over a video distribution network which allows the simultaneous distribution of many channels from a head end to the set top multimedia terminals associated with many customers' television sets. The same approach is then used to develop "virtual channels" at the set top multimedia terminals based on domain or genre or tastes of individuals so that the customer can view the video programming predicted to be most desirable to that customer. The "virtual channels" may be displayed on dedicated channels, or the recommended programming may be highlighted directly on the electronic program guide or displayed on the customer's screen as recommended programming selections. Also, the channels may be reprioritized for presentation on the electronic program guide on the basis of the calculated "virtual channels." Similarly, video programming of a particular type, even if not part of the "virtual channels" may be highlighted on the electronic program guide as desired. The algorithm for determining the recommended programming is based on the above-mentioned "agreement matrix" which characterizes the attractiveness of each movie and video program to each prospective customer. In short, a broadcast schedule and/or virtual channel is generated which is designed to produce the greatest total customer satisfaction. The generation of the agreement matrix and the scheduling of programs in accordance with the generated agreement matrix will now be described in more detail. As described above, the agreement matrix may be produced by comparing the customer profiles and the content profiles. In the following description, it is assumed that the agreement matrix is normalized so that all agreements between customers and movies lie between zero and one. The basic problem of scheduling a cable television broadcast can be formulated as follows. Given an agreement matrix A where ac.sub.ij is the agreement scalar between customer i and program j, find: ##EQU6## where J is a set of programs to be broadcast drawn from a set Q of candidate programs available for broadcast, the first summation is over all customers i, and the second summation (of j) is over the n.sub.i programs in the set of programs K.sub.i that customer i would most desire to watch. In other words, given the agreement matrix between customers and programs, it is desired to pick the set of programs which maximizes the agreement between customers and those programs which the customers might watch. For example, if a hundred programs are being broadcast and a given customer would not consider more than five of them, it does not matter how much the customer likes the other ninety-five programs. However, as noted above, the actual problem can be much more complex, since different agreement matrices can depend on the time of day and since multiple time slots cannot be scheduled independently. If only one program were to be broadcast using the method of the invention, the above optimization problem is trivially solved by summing each column of A (calculating .SIGMA..sub.i ac.sub.ij) and picking the program j which gives the largest value. When many programs are being selected, however, it is not possible to try all possible combinations; therefore, heuristic methods must be used. The following algorithm is an example of a greedy algorithm which provides an efficient algorithm for approximately solving the above scheduling problem including the fact that it is desired to select n.sub.i programs for each customer i (the "viewing appetite"). In other words, n.sub.i represents the number of programs scheduled for broadcast to a particular customer at any time. In a preferred embodiment, n.sub.i corresponds to the number of "virtual" channels available to each customer. In accordance with the invention, the "greedy" scheduling algorithm will function as follows. As illustrated in FIG. 2, at each step of the algorithm: 1) Pick the program j which yields the greatest satisfaction summed over the current customer population (i.e., those eligible to receive program j). 2) Decrement the viewing appetite n.sub.i of those customers who have the greatest agreement scalars with the currently selected program. 3) Remove from the customer population any customers whose viewing appetite has dropped to zero (n.sub.i =0), since they have all the shows they need and hence are not a factor in selecting further shows. The scheduling process stops when the number of programs selected, m, equals the number of broadcast channels available, M, for the schedule time. A more precise description of the process may be described in pseudocode as: 0) Initialize:
______________________________________
Let ap.sub.i = n.sub.i for all i
set all customers'
appetites to n.sub.i
Let V = {1} initialize the customer
population to include all
customers
Let m = 0. start with no programs
selected
______________________________________
As described below, different initializations are possible to account for programs which will always be broadcast. Also, if individual appetites are not available, all can be set to a single value, n. 1) Select the currently most popular program: Select program j which gives max .SIGMA..sub.i in V ac.sub.ij
______________________________________
Let m = m + 1 increment number of programs
selected
If m = M, stop, stop if done
______________________________________
otherwise proceed to (2). 2) Decrement the appetite of those customers who like the currently selected program: Select the customers i in V for which ac.sub.ij is above a threshold value .alpha.. Then decrement the appetites for selected customers by letting ap.sub.i =ap.sub.i -1. 3) Remove customers from the current customer population V who have no appetite left: Remove from V customers j for whom ap.sub.ij =0. Go to (1). This method automatically produces a schedule in which a variety of programs are selected according to the spread of customer interests. Note that the simpler algorithm of selecting the most popular programs (those with highest agreement matrices) will not produce acceptable results, for if a majority of customers prefer action films, then only action films would be selected, leaving the minority of customers with no films that they find attractive. FIGS. 1-3 summarize the above-mentioned procedures for establishing customized channels of preferred programs in accordance with the invention. As illustrated in FIG. 1, a schedule of available shows and their characteristics (content profiles) is created and stored in a database at step 102. As noted above, the characteristics of the shows may be determined by "experts" or test groups by completing questionnaires and the like, or the content profiles may be generated from the frequency of usage of certain words in the text of the video programs (the on-line descriptions or the script). Alternatively, the content profiles may be determined by combining the customer profiles of those who "liked" the video program during a "rave review." Preferably, the content profiles are downloaded all at once for a given time period along with the corresponding scheduling data as part of the electronic program guide data and sent via a separate data channel. On the other hand, the content profiles may be transmitted as part of the bit stream of the video program (for digital transmission), in the vertical blanking intervals of the video program (for analog transmission), or by other appropriate means. At step 104, the customers' preferred characteristics (customer profiles) are created and stored in a database. As noted above, the customer profiles represent the customers' preferences for the program characteristics and preferably differ in accordance with the time of day to account for different moods of the customer and different customers within each household. In a preferred embodiment, the customer profiles for each household are stored in the set top multimedia terminal for that customer's household. The content profiles received with the electronic program guide data are preferably stored at the set top multimedia terminal and compared by the set top multimedia terminal to the customer profiles for each customer. An agreement matrix is then created at step 106 using the techniques described above. Once the agreement matrix has been generated, those programs with the highest values for ac, i.e., the closest distance (1/ac) and hence closest match to the customer's profile or profiles, are prioritized and selected for presentation as "virtual channels" (in the case of creating "virtual channels" at a set top multimedia terminal) or as the programming channels (in the case of scheduling video programming at the CATV head end) at step 108. This process is described in more detail herein with respect to FIG. 2. In a simple embodiment of the invention in which no feedback is used to update the customer profiles, no further activity is necessary. However, it is preferred that the customer and/or content profiles be updated to allow for changes in the customers' preferences as well as to correct errors in the original determinations of the profiles. Accordingly, at step 110, the customers' set top multimedia terminals maintain a record of the video programs that are actually watched by the customer for a period of time (say, 10 minutes) sufficient to establish that the customer "liked" that program. Of course, the monitoring function may be selectively activated so that the profiles are not always updated, as when a guest or child takes control of the television at an unexpected time. Finally, at step 112, the customers' profiles are updated to reflect the programs actually watched by the customers. Such updating techniques are described above and further below with respect to FIG. 3. FIG. 2 illustrates a technique for selecting video programs for "virtual channels" at the customers' set top multimedia terminals or, alternatively, for scheduling video programming at the head end from the available video programming sources. As illustrated, the method is initialized at step 202 by determining which customer profile or profiles are active for the time period to be scheduled, by determining the customers' appetites (number of channels available for transmission), and by determining the database of video programming from which the schedule may be created. For example, at the head end, the video programming database may be any video programming available for transmission during the designated time frame, while at the set top multimedia terminal, the video programming database comprises only the video programming on those channels which the customer is authorized to receive. Once the agreement matrix for the available video programs has been determined, at step 204 the most popular programs for a single customer (at the set top multimedia terminal) or a cluster of customers (at the head end) are selected and removed from the list of available programs during the relevant time interval. Of course, in the case of scheduling at the set top multimedia terminal, the video programs scheduled onto "virtual channels" are still received on their regular channels and the "virtual channels" are assigned to unused channels of the set top multimedia terminal. At step 206, it is then determined whether the customer's appetite is satisfied (at the set top multimedia terminal) and whether all the customers' appetites are satisfied (at the head end). If all relevant appetites are satisfied, the scheduling algorithm is exited at step 208. On the other hand, if all customer appetites are not satisfied, the appetites of the customers likely to watch the selected program are decremented at step 210. Hence, only those customers with preferences which relatively "match" the characteristics of a particular video program have their appetites decremented. At step 212, those with no appetites (channels for scheduling) left are removed from the scheduling list. The process is then repeated starting at step 204 for those with channels left to schedule. When establishing "virtual channels" in accordance with the invention, it is important to know which customer profile or profiles to use in creating the agreement matrix. In a preferred embodiment, this is accomplished by using the customer profile or combination of customer profiles which are given priority during a particular time interval for a predicted customer mood. This determination is made independent of the person actually viewing the television. However, the system of the invention may be easily modified to permit the customer to identify himself or herself by providing a user ID to the set top multimedia terminal so that a particular profile of that customer may be selected in the determination of the agreement matrix. In other words, customer names may be matched to particular profiles based on selections made when that customer's user ID has control of the television. In addition, combined profiles may be created which best reflect the combined viewing tastes of several persons in the same household. On the other hand, the system may come with preselected profiles which the customer may select to use as his or her initial profile. After a certain amount of time, the system would recognize a particular profile as belonging to a particular viewer or combination of viewers so that it would eventually be unnecessary for the customers to input their user IDs. In other words, the system would "guess" which customers are viewing by noting which customer profile is closest to the shows being selected. Of course, this latter approach requires the customer profiles to be matched to individuals rather than just time slots as in the preferred embodiment. FIG. 3 illustrates a preferred technique for updating customer profiles in accordance with the invention. As illustrated, the initial customer profiles are selected at step 302 using any of the techniques described above. At step 304, the agreement matrix is calculated to determine which video programs the customer might desire to view in the selected time period. Then, at step 306, the passive monitoring feature of the invention is invoked to determine if the customer actually watched the video program selected from by the agreement matrix. If the customer watched the predicted program, then the customer profile is presumed accurate at step 308 and no adjustment is made. Of course, the customer profile may be positively reinforced by varying the adjustment increment. However, if the customer did not watch the predicted video program, the customer profile for the appropriate time interval is selected at step 310 which has characteristics closest to those of the video program actually watched. That customer profile is then adjusted using the techniques described above. The adjusted profile is then considered valid until the next time slot is encountered at step 312. The agreement matrix is then recalculated at step 304 for the new customer profiles and video programs offered in the next time slot. Particular hardware implementations of the invention in a set top multimedia terminal and/or a video head end will be described in Section VI below. C. Scheduling Variations Many variations to the above generalized scheduling scheme are possible within the scope of the invention. The following variations may be used by those skilled in the art, but, of course, this list is not comprehensive. A. Special programs such as standard network broadcasts may be included in the scheduling. In this embodiment, when certain programs have already been scheduled for broadcast, such as standard network programs or specially selected popular movies, the above algorithm is modified to account for the effect of these programs on customer interest in the remaining video programming. This is easily done by initially running the above algorithm with step (2) modified to simply include the prescheduled programs rather than selecting new ones. When all prescheduled programs have been "scheduled" (i.e., customers likely to watch the prescheduled programs have been removed from the customer pool and the broadcast slots have been filled), then the scheduling algorithm proceeds as usual. As desired, this will lead to additional movies being selected which will appeal most to customers who will probably not be watching the standard network broadcasts. B. The effect of recent broadcasts may be included in the scheduling. The above scheduling algorithm is presented for a single time slot. In actuality, the video programs selected must depend on which other video programs have been shown recently. This can be done in several ways. For example, one can remove recently shown movies from the list of movies available to broadcast. Alternatively, one can remove recently shown movies from the list of movies available to broadcast when their popularity (number of customers per broadcast) drops below a threshold. This approach is better in that it allows new hits to be broadcast multiple times. More complex models may explicitly include a saturation effect by shifting the agreement matrix based on the number of similar video programs recently viewed. C. The effect of overlapping time slots, such as so-called "near video on demand" may be included in the scheduling. For this purpose, the above algorithm can be modified to account for the fact that popular video programs may occupy more than one time slot and that time slots may overlap. As an extreme example, it may be desirable to offer multiple overlapping broadcasts of a popular movie on vacant channels, e.g., at 15 minute intervals. In this example, the customer appetite concept set forth above would be augmented by a more sophisticated model which includes the fact that customers turn on the television at different, possibly random times, and only want to watch shows which are starting at times close to the time they turn on the television. D. The effect of moods may be included in the scheduling. If one has different agreement matrices for different customer moods (either reflecting multiple customers with different tastes using the same television or reflecting one customer having different viewing preferences due to mood), the above algorithm can be trivially extended. The different moods are just treated as different customers, with the appetite for each mood selected to be proportional to how often that mood occurs in the time slot being scheduled. This will result in programs being scheduled for each of the potential moods; the customer can then pick his or her preferred show. E. Programs may be matched to channels for scheduling content based channels. Customers may prefer to have channels which have a consistent content or style (e.g., sports or "happy" shows). The basic algorithm presented above could be modified so that some slots are reserved so that shows of a given type (e.g., close to a given set of characteristics typical of a channel) can be selected if they have not already been chosen in the main scheduling algorithm. F. How the customer appetites are decremented may be selected for scheduling purposes. In the above scheduling algorithm, whenever a program is chosen, the viewing appetite of all its "audience" is decremented, and those who have used up their appetites are removed from the viewing population. Since the checking of viewing appetite is made only of the audience of the currently chosen program, the outcome of the scheduling process depends in part on the definition of audience--who will potentially watch the program. Above it was assumed, for simplicity, that customers should be included in the potential audience if their agreement with the program was above a threshold. However, many variations on this are possible. For example, one could pick a fixed audience size for each show. For example: Select the n.sub.w customers i in V for which ac.sub.ij is maximum. n.sub.w can be calculated, for example, as n*I/M as the average customer appetite, n, times the number of customers, I, divided by the number of programs, M, to be broadcast. One could also make the threshold a variable, either by decreasing the threshold or the number of customers n.sub.w over the course of developing a schedule so that the first programs scheduled would have large audiences, while the last programs scheduled (those done after most customers needs are satisfied) would have smaller audiences. Ideally, this would be done in accordance with observed audience size distributions. G. The lead-in effect may be included in the scheduling. The algorithm could be modified to account for higher viewing levels in shows which follow immediately after popular shows (the "lead-in" effect). As described above, this can be accounted for by treating errors in predicting customer behavior differently if they result from the customer remaining tuned to a channel. H. The effect of repetitive showings may be included in the scheduling. Since viewership is a strong function of the time of day and of the day of the week, one cannot assess the popularity of a show based on the number of people watching it without controlling for the time slot. Similarly, movies shown at the same time as very popular programs or as very similar programs tend to have fewer viewers--the audience will be divided. The algorithm given above does not rely on absolute viewership numbers and so does not have these problems. Similarly, when many similar programs are shown over a short span of time, there is viewer "burnout". In other words, if the same movie is shown repeatedly over the course of a month, it will get fewer viewers on later showings. As another example, if many golf programs are broadcast during a week, each customer's desire to watch golf will saturate, and viewership will decay. Predictions of what a customer will want to watch only makes sense if they have not watched the same (or almost identical) show recently. Thus, changes to the customer profiles and content profiles should not be made if, for example, a customer does not select a movie to watch which they recently watched. However, depending on the indexing scheme used to store viewing habits, checking to see if a similar program was recently watched, while straight forward, may require a significant amount of database search. I. Customer profiles can be modified on an individual basis. Since different people often watch the same television, and most feedback devices in popular use do not recognize which customers are present, customer preferences cannot be characterized by a single agreement matrix. Also, customers may have different agreement matrices depending on their mood. If more than one agreement matrix per television is initially estimated (e.g., by interviewing multiple customers), then the above algorithm can be modified to only count a prediction as wrong if none of the agreement matrices for a given television yields predictions that agree with what was actually watched. One or more of the agreement matrices for the television could then be updated using the algorithm. This is not ideal, in that one does not know which mood (or customer) was present, but the best that one can do is assume that it was the mood (customer) whose agreement matrix came the closest to giving the correct prediction. On the other hand, the customer may simply identify himself or herself when the television is turned on, and preferably, may specify which profile to use based on who is present and/or the customer's mood. All of these effects can be taken into account in developing customer profiles and content profiles and in scheduling video programs in accordance with the invention. V. Passive Characterization of Customers Using Feedback Thus far, the invention has been described in the context of a "filtering" system in which all of the video programming available at the head end is scheduled on "customized" channels in accordance with the customer profiles of customers and in which a subset of the programming on the "customized" channels available to each customer is selected using an agreement matrix for presentation to the customer as "virtual channels" tailored to that customer's characteristic profiles. However, one of the more interesting applications of the above-mentioned customer profile system is that the same customer profiling system may be used to provide feedback from individual customers regarding what characteristics they find most desirable in the broadcast shows. By obtaining this information, the customer profiles may be appropriately updated as described above. As will now be described, the video programming schedules also may be updated to reflect the customers' actual preferences, and information may be combined with the customer demographics and customer profiles to provide targeted advertising and targeted shop at home opportunities for the customer. A key feature of many video/cable television installations is that it is possible to obtain active feedback from the customer: either simply what was watched at each time or, more completely, how much the customers (in their estimation) liked what they saw. Monitoring viewing patterns is referred to herein as "passive" feedback, since unlike such prior art "active" feedback systems where the customers actually rate how much they like particular programs (see, e.g., Strubbe, U.S. Pat. No. 5,223,924), passive monitoring in accordance with the invention does not require any customer actions. As will be described below, passive feedback can be used to improve characterizations of customers' preferences for programs, which, in turn, leads to better selection and scheduling of programs. Also, as just noted, passive feedback provides new target marketing opportunities. Profiles of customers indicating which video program characteristics they prefer can be combined with content profiles of video programs indicating which characteristics they possess to give a measure of how well each customer should like each video program. One way of doing this is to construct an agreement matrix as described above. Passive feedback is used in conjunction with the agreement matrices to improve customer profiles and content profiles and hence to improve program schedules. Passive feedback can be used both to improve individual customer profiles and to improve customer profiles for clusters of customers. Customer profiles of customer clusters then can be used to improve the profiles of all customers constituting the cluster. As a simple example, if one finds that most people in a cluster like movies by a particular director, then one could conclude that the other customers in the cluster would probably like that director as well. As with methods for updating individual customer profiles, one can characterize clustering methods for grouping together customers (e.g. for a "video club") as lacking feedback, using passive feedback, or using active feedback. As described above, the basic agreement matrix method of the present invention, in which video programs are characterized by certain identifying characteristics which are then compared to the customers' preferences for those characteristics, uses no measurement of what is watched or other feedback. However, as also noted above, that method can be supplemented with customer ratings of movies (active feedback) or passive feedback of who watched what movies when so that the customer profiles and/or content profiles may be adjusted. It is now proposed that those monitoring techniques be augmented by a clustering algorithm which combines passive feedback with the use of customer profiles and content profiles. This offers the advantage of using the technique of the invention even when no initial customer profiles are available and there is no past history of what the customers have watched. The technique starts, optionally, with a profile of the customer in terms of what movie characteristics he or she finds important. It then refines the importance given to different characteristics based on how accurately the characteristics predict what movies the customer actually watched. A. Algorithm for Passive Updating of Customer Profiles The same notation as used above will be used here to describe the methods for using passive feedback to improve profiles of customers, movies, and customer clusters. Namely: cv.sub.ik is the amount of characteristic k that customer i desires, wv.sub.ik is the importance of characteristic k to customer i, and cp.sub.jk is the degree to which movie j has characteristic k. For notational simplicity, it is assumed below that the weightings are normalized (.SIGMA..sub.i wv.sub.ik =1) so that the customer weightings add to one. There are: J movies, K characteristics, I customers, M "experts", and P movies to be selected for a given viewing interval (e.g., a day or week). The agreement matrix incorporates both the desired amount of each characteristic and its importance to the customer using Equation (21) set forth above, except that w.sub.ik has been normalized. Given a set of J movies available with characteristics cp.sub.ik, and a set of customer preferences, cv.sub.ik, customer i would be predicted to pick a set of P movies to maximize: ##EQU7## If the customer picks a different set of P movies than was predicted, cv and w.sub.ik should be adjusted to more accurately predict the movies he or she watched. In particular, cv and w.sub.ik should be shifted to reduce the match on movies that were predicted to be watched but were not watched, and to increase the match on movies that were predicted not to be watched but were watched. There are several ways to do this. One is to shift cv for each wrong prediction for customer i and movie j using: cv.sub.ik =cv.sub.ik -.DELTA.(cv.sub.ik -cp.sub.jk). Equation (24) This will increase the match by making cv closer to cp if .DELTA. is positive--and is representative of the case where the algorithm failed to predict a movie that the customer watched. The size of .DELTA. determines how many example movies one must see to replace what was originally believed. If .DELTA. is too large, the algorithm will be unstable, but for sufficiently small .DELTA., cv will be driven to its correct value. One could in theory also make use of the fact that the above algorithm will decrease the match if .DELTA. is negative, as for the case where the algorithm predicted a movie that the customer did not watch. However, there is no guarantee that cv will be moved in the correct direction in that case. One can also shift w.sub.ik using a similar algorithm: ##EQU8## As before, this will increase the match if .DELTA. is positive, as for the case where the algorithm failed to predict a movie that the customer watched, this time by decreasing the weights on those characteristics for which the customer profile differs from that of the movie. Again, the size of .DELTA. determines how many example movies one must see to replace what was originally believed. Unlike the case for cv, one also makes use of the fact that the above algorithm will decrease the match if .DELTA. is negative, as for the case where the algorithm predicted a movie that the customer did not watch. The denominator of Equation (25) assures that the modified weights w.sub.ik still sum to one. Both cv and w.sub.ik can be adjusted for each movie watched. When .DELTA. is small, as it should be, there is no conflict between the two parts of the algorithm. There are several ways to initialize the algorithm, depending on what information is available, including: (a) questioning the customer as to what characteristics they find important in movies or other programming; (b) using a customer profile typical of the other customers with the same demographic profile as the customer; (c) using a typical customer profile (assuming no demographics are available); and (d) random selection, which is not desirable unless a solid history of movies is available. The example set forth in Section III above will now be extended to illustrate the above-described feedback process for improving the characterizations of the customer preferences for the programs. As noted in the example in Section III above, the customers' profiles (cv', sv', wv') are initially estimated. The estimated initial normalized weight (w') and the agreement scalars with all the programs are then calculated accordingly. During the customer feedback process, each time a customer picks a program which differs from the program that is predicted based on the current estimated agreement scalars, corrections are made to the estimated characteristic and weight profiles, which assumably will move the estimated profiles closer to the true profiles. If it is assumed that at time period n customer i watches a movie j but the algorithm predicts program h, corrections will be made to customer i's characteristic profile as follows: cv'.sub.ik.sup.n+1 =cv'.sub.ik.sup.n -.DELTA.(cv'.sub.ik.sup.n -cp'.sub.jk), for all k, and to the weight profile as follows: ##EQU9## where the positive parameter .DELTA. determines the size of the correction step. For instance, an initial estimated customer profile (cv'.sup.0) could be found using a random function to be:
______________________________________
customer romance high-tech
violence
______________________________________
1 John 1.595 9.894 9.174
2 Mary 6.735 3.897 0.000
______________________________________
If it is then supposed that there are three television channels and programs 1, 2, and 6 available for broadcast, John (customer 1) chooses program 1 since it has the highest agreement scalar with him, based on his true customer profiles, among the three available programs. However, according to his current estimated customer profile, program 6 was predicted. Hence, a correction is necessary. For simplicity, changes are made only in his current estimated characteristic customer profile cv'.sub.l.sup.0 to create his new estimated profile cv'.sub.l.sup.1. In other words, his weight profile will not be adjusted. Thus, if .DELTA.=0.1, the customer profiles are adjusted to: cv'.sub.11.sup.1 =1.595-0.1*(1.595-2)=1.635 cv'.sub.12.sup.1 =9.894-0.1*(9.894-9)=9.805 cv'.sub.13.sup.1 =9.174-0.1*(9.174-4)=8.856 As a result, the new estimated customer profile cv'.sub.l.sup.1 is closer to the true customer profile than the previous estimated profile cv'.sub.l.sup.0. The following represents a typical feedback process (without weight correction):
______________________________________
Initial Estimated Profiles
1 John 3.399 10.000 5.448
2 Mary 10.000 2.190 1.216
Run 1 (92% correct predictions):
Estimated Profiles
1 John 1.943 9.760 5.941
2 Mary 10.000 2.190 1.216
Run 2 (97% correct predictions):
Estimated Profiles
1 John 1.597 9.735 6.139
2 Mary 10.000 2.190 1.216
Run 3 (100% correct predictions):
Estimated Profiles
1 John 1.597 9.735 6.139
2 Mary 10.000 2.190 1.216
______________________________________
Thus, the estimated profiles in Run 3 are the same as for Run 2, where each run contains 100 loops (time periods). After 3 runs, the estimated profiles are good enough to make constant correct predictions. By way of summary, the following steps should be provided for passive feedback of customer preferences: 1) Pick starting values for cv.sub.ik, cp.sub.jk, and w.sub.ik. As noted above, these values may be determined from questionnaires or, for new customers, the values can be set to those of a typical customer, optionally based on demographics. 2) Each time that a customer i watches a movie j that the algorithm did not predict they would watch, update cv.sub.ik, cp.sub.jk and w.sub.ik using: cv.sub.ik =cv.sub.ik -.DELTA.(cv.sub.ik -cp.sub.jk), cp.sub.jk =cp.sub.jk -.DELTA.(cv.sub.ik -cp.sub.j), and/or w.sub.ik =(w.sub.ik -.DELTA..vertline.cv.sub.ik -cp.sub.jk .vertline.)/.SIGMA..sub.k (w.sub.ik -.DELTA..vertline.cv.sub.ik -cp.sub.jk .vertline.). Each time the customer i does not watch a movie j that the algorithm predicts they would watch (but only if the customer is watching something), update w.sub.ik using: w.sub.ik =(w.sub.ik +.DELTA..vertline.cv.sub.ik -cp.sub.jk .vertline.)/.SIGMA..sub.k (w.sub.ik -.DELTA..vertline.cv.sub.ik .vertline.-cp.sub.jk .vertline.). In all of the above equations, .DELTA. is a small positive number, set to roughly one over the number of movies that one wishes to observe to half forget the original values of cv.sub.ik, cp.sub.jk, and w.sub.ik. B. Variations to Passive Characterization Algorithm Many variations to the passive characterization algorithm are possible. For example, the characterization of the movies was assumed to be correct in the above feedback system. As a result, the customer profiles were adjusted. However, if one believed the customer profiles and not the movie characterization, one could use a similar algorithm to adjust the movie characterizations. In practice, one would use both methods simultaneously: if predictions for one person are less accurate than average, that person's profile should be adjusted, but if predictions for one movie are less accurate than average for movies, that movie's characterization should be adjusted. The simplest algorithm is to shift cp for each wrong prediction for customer i and movie j using: cp.sub.jk =cp.sub.jk -.DELTA.(cv.sub.ik -cp.sub.jk) Equation (26) This will increase the match by making cp closer to cv if .DELTA. is positive. As before, this should only be done for the case where the algorithm failed to predict a movie that the customer watched. Another possibility would be to not use any characterization of the movies or customers, but simply to group the customers together based on the number of movies that they viewed in common. This requires overcoming some minor technical difficulties in controlling for different numbers of movies being watched by customers. On the other hand, if active feedback on how well the customers liked the movies is available, one could also use this information. Rather than making changes simply based on "watch/did not watch", one can weigh the changes (i.e., alter the size of the .DELTA.'s) based on the degree of customer like/dislike of the program. In addition, one can also modify the algorithm to take into account other known determinants of customer behavior. For example, customers tend to continue watching programs which are shown on the channel that they are currently watching. This means that even if the agreement matrix correctly predicts that a customer would prefer a program on a different channel, the customer may not discover the other program (or bother to change to it). In this case, the agreement matrix was not incorrect and so the customer and content profiles should not be altered. This can easily be incorporated into the passive feedback algorithm by using smaller changes (smaller .DELTA.'s) when a customer remains tuned to the same channel (possibly virtual channel) than when they simply switch channels. C. Customer Clustering As noted above, customer profiles can be kept for groups of customers as well as for individual customers. Grouping customers together into customer clusters offers several advantages. Most importantly, if the clusters are accurate, improvement of customer profiles will be much faster, since far more movies are viewed per week by a cluster than by any individual in the cluster. Clustering also provides a means of setting up an initial profile for new individuals joining a video service in accordance with the invention, as they can, as a starting point, be given a profile based on demographic data or on surveys they fill out. There is a long tradition of clustering people based on demographic or other data, and many clustering algorithms exist ranging from traditional methods such as factor analysis or the k-means clustering algorithm to more esoteric neural network-based methods such as Kohenen networks. Any of these can be used for the task described here, but the present inventors prefer the k-median clustering algorithm. Clusters can be formed based on (1) what programs people watch, (2) what features of programs customers rate as important (e.g., how similar their agreement matrices are), or (3) a combination of programs and features. One can also include demographic or psychographic customer profiles or other information. The clustering mechanism selected must address several technical issues. Most importantly, the clustering algorithm must take into account the fact that different attributes used for clustering may have different degrees of importance, and may be correlated. If one uses as a clustering criterion a pure measure, such as maximizing the number of programs watched in common, or maximizing the degree of similarity of the customers' agreement matrices, this is not a problem, but if these attributes are combined with other information such as demographics, the algorithm must determine an appropriate metric, i.e., combination weights for the different measures. Once clusters have been determined, they can be used in several ways. As the profiles for the clusters are updated based on what the customers in the cluster watched, the profiles for the individuals in the cluster can be similarly updated. Thus, customer profiles can be updated both based on what they watch and on what customers with similar tastes watch. These modified customer profiles would be used for determining virtual channels and for scheduling which movies to broadcast. As noted above, the purpose of clustering is to group o | ||||||