There are many systems in which data is generated by an unknown entity (e.g. a human user) and it would be useful to be able to categorise the entity (e.g. to categorise the user as a child or as an adult) in Order to modify the behaviour of a system with which the unknown entity (e.g. a user) is interacting accordingly (e.g. to provide a simpler user interface to children than to adults, etc.). This is typically done by asking the user/entity for identity information (e.g. asking the user to “log on” to the system). However there may be circumstances where it is preferable to perform the categorisation required for a particular purpose without requesting the information directly from the user (one such example being where the user is not trusted to provide his/her log on credentials honestly, although more normal situations are likely to be just for the user's convenience, where the user interface does not permit a normal typed log-in procedure, or for users or other entities which are not able or willing generally to provide suitable credentials for logging on purposes, or where a group of individuals is involved and all that is required is a categorisation of the group and it would be tedious to determine this by requesting log-on info from each individual and/or still difficult to determine the group correctly even if all of the individuals were known).
There are also many systems which generate lots of data which could be useful for tasks such as identifying a category to which a user of the system belongs, etc. but is too voluminous to be efficiently transmitted and/or stored for subsequent processing and is also possibly too voluminous to be efficiently processed (even if it could be suitably stored and/or transmitted) Known mechanisms for summarising data include attempting to fit the data to a particular well known mathematical distribution (e.g. data which conforms to a normal distribution can be very efficiently summarised by noting details such as the number of data elements (or data points) and the mean and standard deviation of the collection of data. Similar calculations can be performed for a collection of data items corresponding to any other of several well known distributions (e.g. uniform, Poisson, etc.). Another method is to divide time into a series of intervals or “bins” and to count the occurrence of events (by type) and storing the total counts for each recorded event type within a particular bin (i.e. occurring within a particular duration of time corresponding to the bin). (E.g. if storing data about the behaviour of a Digital Subscriber Line, information about the occurrence of forward error corrections, errored seconds and resynchronisations might be summarised and stored as a series of groups of four numbers—e.g. (1251, 230, 10, 0)—i.e. bin No. 1251, 230 forward error corrections, 10 errored seconds and 0 resynchronisations which could be stored in a relational database table).
US2002/0129368 describes a method of profiling a television viewer based on the interactions between each viewer of a television and the television, and using the generated profiles to infer, at a particular time, which specific individual or individuals are actually interacting with the television. Data is stored in time bins and is moved from one bin to another as time passes. The bins include different bins of different durations (i.e. covering periods of time of different lengths). Also sliding windows covering a number of small bins are described. However there is no discussion of the use of fuzzy bins or of how these could be used to produce a multi-scale system in which data is moved only partially from one bin to another.
WO 2007/131069 describes another method of profiling a television viewer based on the interactions between television viewers and a television set, but also describes how fuzzy logic can be used to help to categorise a current user as being one of a plurality members of a household (or of being identified as a guest or visitor user who is not a member of the household). However, there is no disclosure of multiple data summary bins wherein the periods of time covered by respective summary bins include overlapping periods of time and periods of time having different durations.
According to a first aspect of the present invention, there is provided a system controller comprising: a receiver for receiving data about a system to be controlled (e.g. data input to the system, data output by the system or intermediate data generated by the system as a result of some processing of input data, etc.) and for associating the received data with a time factor (e.g. a timestamp or a time interval, etc.); a summariser for updating a set of summary bins, each of which is associated with a respective period of time, and each of which stores a summary of the received data associated with its respective period of time; and a processor for processing the summary bins; and a director for issuing control instructions to the system to be controlled based on the results of the processor; wherein the periods of time associated with respective summary bins include overlapping periods of time and periods of time having different durations.
According to an alternative expression of the first aspect of the present invention, there is provided a system controller comprising: a receiver for receiving data about a system to be controlled and for associating the received data with a time factor; a summariser for updating a set of summary bins, each of which covers a respective period of time, and each of which stores a summary of the received data having a time factor which falls within the respective period of time covered by the summary bin; a processor for processing the summary bins; and a director for issuing control instructions to the system to be controlled based on the results of the processor; wherein the periods of time covered by respective summary bins include overlapping periods of time and periods of time having different durations.
Where the time factor associated with received data specifies a duration of time (as opposed to an instant of time), the phrase “each of which [summary bins] stores a summary of the received data having a time factor which falls within the respective period of time covered by the summary bin” is intended to include the possibility that the two durations of time (i.e. that associated with the received data and that covered by the summary bin) are overlapping rather than one being entirely contained within the other as is apparent from the following.
The use of summary bins which are associated with overlapping and non-equal time durations enables a much better summarisation of event data which is difficult to map to a well understood mathematical distribution (e.g. a normal or Poisson distribution etc.) compared to the use of conventional bins of data associated with non-overlapping equal time durations. Preferably, the bins are also fuzzy bins in the sense that an event may partially belong to a particular time duration (rather than crisply either belonging to a particular duration or not). For example a fuzzy bin of one hour's duration storing the most recent events might ascribe events occurring at a present time (of to) a membership of 1 with events which have occurred up to one hour preceding the present time being given a membership of between 1 and zero according to a linear relationship moving between 1 and 0 between the present time and one hour preceding the present time, such that, for example, an event which occurred 30 minutes prior to the present time would be ascribed a membership value of 0.5 to the fuzzy bin associated with the most recent duration (see FIG. 3 described below). Such bins (i.e. fuzzy bins associated with overlapping, non-equal time durations) are hereinafter referred to as overlapping, fuzzy, multi-scale bins.
Thus, the summary bins are preferably fuzzy bins in the sense that where bins, having the same granularity, cover overlapping periods of time, data associated with a time falling within such an overlap is apportioned between the overlapping summary bins for summarising purposes in accordance with fuzzy membership rules as discussed above. Preferably the total membership of an event at a specified instant of time to two or more fuzzy bins of the same granularity will be one; for example, following on from the example given above, it is preferable if, as membership of the fuzzy bin which stores the most recent events as described above falls linearly from one to zero as time proceeds from the present time to a time one hour in the past, that a second bin has a membership which increases from zero to one during this same period, such that the total membership to these two bins is one for all times between the present time and one hour in the past, with the apportionment between the bins varying across this period from being wholly apportioned to the first bin at the present time to being wholly apportioned to the second bin at one hour in the past.
An alternative manner of specifying fuzzy overlapping multi-scale bins is to associate a few (e.g. four to eight) one hour bins each with a fixed one hour period, for example from 17:30 hours to 18:30 hours, 16:30 to 17:30, etc. such that full membership (of one) to a single one hour bin is ascribed only to events occurring exactly on the hour (e.g. at 18:00 hours) with a linearly increasing membership level between zero and one for events occurring at times between one hour before the hour in question (e.g. from 17:00 hours to 18:00 hours) and a decreasing membership between one and zero for events occurring between the hour in question and one hour later (e.g. from 18.00 hours to 19:00 hours), such that any event occurring at any time will be ascribed a total membership of 1 between two adjacent bins (apart from events occurring exactly on the hour); for example, an event occurring at 18:30 would be ascribed 0.5 membership to the 17:30-18:30 bin and 0.5 membership to the 18:30-19:30 bin; and an event occurring at 18:15 would be ascribed 0.75 membership to the 17:30-18:30 bin and 0.25 to the 18:30-19:30 bin. In this arrangement, when time has passed sufficiently that a bin associated with a relatively short scale time duration (e.g. a one hour bin) is associated with a time period (e.g. 15:30-16:30) which is more than a predetermined length of time in the past (e.g. more than say four hours in the past), it may be assimilated (or number of such fine grain bins may be amalgamated) into a larger scale bin (e.g. after say 19:00 hours the 15:30-16:30 bin may be assimilated into a four hour bin associated with say 12:30-16:30)—this process may be performed as a batch process at intervals related to the duration of the larger scale bin—e.g. after say 19:00 hours four one hour bins (e.g. 12:30-13:30, 13:30-14:30, 14:30-15:30 and 15:30-16:30) may be assimilated/amalgamated at that time to become a new four hour 12:30-16:30 bin, with the next assimilation/amalgamation of four one hour bins 16:30-17:30, . . . , 19:30-20:30 not occurring until after 23:00, etc.). A similar process may be occurring at the next scale—e.g. on an approximate daily basis, groups of six four hour periods may be assimilated into a one day bin, etc.
Preferably, the summariser generates from the received data one or more attribute values and stores these as the summary of the data. Each generated attribute value preferably depends upon the existing value for a particular attribute (which may be null or zero if no “relevant” data has previously been received—where “relevant” here means both that it pertains to the attribute in question and pertains to the time period covered at least partially by the summary bin in question) as well as the received data.
Preferably, the content of each bin is updated from time-to-time (e.g. on a periodic basis or, more preferably on an event driven basis such as whenever a new event which will have an effect on the content of at least one bin is detected—refinements on this may include buffering a predetermined number of events (or the events occurring—or commencing or ending—within a predetermined period of time) and then performing an update based on the contents of the buffer when the buffer is read at a predetermined time (e.g. because the buffer period of time has expired or the buffer is full or has reached a trigger capacity, etc.). When an update is performed it is preferable if all of the bins are also updated at that time. Updating the bins preferably includes ascertaining a portion of one or more bins to be transferred to one or more other bins as well as ascertaining the additional new contents to be added to new bins based on newly detected events/acquired data. In some embodiments, updating bins may additionally involve ascertaining the proportion of the contents of one or more old bins to now be discarded as a result of the contents being associated with data/events which are now so old as to not be relevant to any of the stored bins.
Preferably, transferring some portion of the contents of one bin into another is just a matter of transferring the complete contents from a bin of one scale to a bin of another larger scale/coarser granularity (or possibly sharing the contents of one bin between two adjacent and overlapping coarser grain bins). Alternatively, each time a new event is recorded, the time period with which a bin is associated may be changed (in absolute terms because the bins may be associated with a period of time specified in relation to a time which is changing absolutely—e.g. the time periods could be with reference to a current time which is of course constantly changing) and therefore the contents of the bins must be transferred on each such occasion so that the contents transfer over time from more recent to more distant (in time) bins over the course of time. The different possible ways of transferring the contents of one bin to another (either of the same or of a different scale) may result in different contents being assigned to the bins, but so long as whenever a portion of one bin is taken out from that bin, that same amount is transferred into, another bin (or bins) so that no contents are lost), and so long as the amounts ascribed to each bin are approximately similar regardless of the manner employed for performing the transfer, the bins may still be useful for the principal function of performing a categorisation of the generating entity (or entities) responsible for generating the recorded events/acquired data.
By arranging that, in times of overlap between two fuzzy overlapping bins of the same scale, the total membership of an event to the bins sums to 1, it is possible to easily combine the contents (of several adjacent fuzzy overlapping bins to move the contents of two overlapping bins to a different bin (e.g. so as to enable an update of a later bin (of either the same scale as the original bins, or perhaps of a different—e.g. longer duration—scale bin, at a later time—this updating of bins is described in greater detail below).
By associating bins with overlapping non-equal durations of time different levels of detail can be recovered from the bins in respect of different times. In particular, since it is often more useful to have a finer granularity knowledge of recent events than of older events, it is preferable if there are fuzzy bins covering relatively short durations in respect of more recent events and fuzzy bins covering progressively longer durations in respect of less recent events. By using fuzzy, overlapping, multi-scale bins it is possible to avoid the problems associated with fixed duration, crisp, non-overlapping bins that it can be difficult to determine (in respect of certain types of data such as message activity on a social networking web-site) the optimum window size for each bin—too short and the change from window to window (or bin to bin) becomes noisy or chaotic (and therefore less useful for performing automatic categorisation based on the data), too long and interesting changes may be lost in the smoothing inherently involved in the summarisation process (of storing the data as counts within a bin). The use of fuzzy, overlapping multi-scale bins significantly mitigates these problems enabling interesting changes to be detected relatively rapidly (i.e. not smoothed away) whilst avoiding noisy unpredictable results as a result of having bins associated with too short a time scale.
Preferably the processing performed on the summary bins includes identifying a sub-set of the data associated with a single unknown entity (whether an Individual, a group of individuals or one or more computer systems or programs, autonomous agents, software applications, etc.) and performing a categorisation of the data in order to identify a category with which to associate the entity, such that the system to be controlled can then be modified in order to be tailored for future use by the categorised entity in accordance with the categorisation. For example, in a social networking environment, it may be desirable to categorise users by age and gender so that adults can be excluded from interacting with children in a child oriented social networking environment. To achieve this, a standard categoriser (e.g. a neural network) could be trained on summary bins of data derived from a combination of known children and known adults (possibly including adults pretending to be children) and thereafter, fresh data from unknown entities can be summarised into the summary bins and then processed by the now trained standard categoriser which can, based on its training, attempt to categorise the unknown entities accordingly as either children or adults, and an alert can be generated in respect of entities identified as adults attempting to masquerade as children, etc.
Thus, in a preferred embodiment of the present invention, a system controller according to the first aspect of the present invention is provided wherein the received data is data resulting from interactions between an unknown entity and the system to be controlled and wherein the processor is operable to perform a categorisation of the received data in order to identify a category with which to associate the entity, and wherein the director issues instructions to the system to be controlled to modify its behaviour in order to be tailored to the unknown entity in accordance with the categorisation performed by the processor. Furthermore, where the system to be controlled is a social networking platform, each user of the social networking platform can be considered as constituting an unknown entity to be categorised, and the system can preferably be controlled to disable certain functionality for a particular user if the category identified by the processor disagrees with a categorisation provided by the user (e.g. if a user self-identifying as a child is identified as being an adult).
Similarly, a set-top box associated with a television apparatus may tailor its user interface according to whether it determines that a child or an adult is operating the set top box at any given moment in time, or indeed in accordance with a particular individual or group of individuals which it may determine is currently operating the set-top box (or viewing the television, etc.).
A further aspect of the present invention relates to the summariser of the first aspect of the present invention per se.
A yet further aspect of the present invention relates to a summarised data reconstructer which is operable to provide a (generally lossy) reconstruction of summarised data for a specified time interval, comprising a receiver for receiving an indication of an interval of time of interest for which data is required and optionally an indication of the attributes of interest; a bin identifier for identifying the or each summary bin that is relevant to the received interval of time of interest; an aggregator for, in the event that more than one summary bin is identified by the bin identifier, aggregating the identified summary bins; and an extractor for extracting from the summary bin, or from the summary bins after aggregation where the bin identifier identified more than one bin, attribute values. The extractor may perform some processing of the raw values in order to account for the duration of the interval of time of interest versus the size of the respective bin. For example if the reconstructor is aiming to obtain the amount of time spent by a user viewing news programmes between 16:00 and 17:00 and the only bin, available covering this period is a four hour bin it may be appropriate to extract the value for the amount of time spent viewing news programmes during the entire 4 hour bin period and then divide this value by 4 to obtain an approximation of the amount watched during the requested period (i.e. between 16:00 and 17:00); where the requested interval of time of interest falls within or overlaps a period of time for which two adjacent bins both have some shared membership/association (e.g. the fuzzy overlap period between two adjacent bins) the aggregator preferably aggregates both such bins to generate an aggregated bin and then may consider multiplying the or each summarised attribute value of interest by the ratio of the duration of the interval of time of interest to the duration of time covered by the aggregated bin (e.g. if an interval of time of interest was 15:00-16:00 and there was a one hour bin designatable as (15:00/0, 16:00/1, 17:00/0) and a four hour bin designatable as (11:00/0, 12:00/1, 15:00/1, 16:00/0) then these two bins could be aggregated to a five hour bin designatable as (11:00/0, 12:00/1, 16:00/1, 17:00/0) and the value of an attribute summarised within the aggregated bin could be reduced by multiplying by ⅕ to obtain an estimate of the value for the one hour interval from 15:00-16:00.
Where no indication of desired attributes is given (or in embodiments in which the reconstructer is not designed to receive and process an indication of desired attributes) it is preferable if some default set of attribute values is given which may be user settable, or it may be predefined (e.g. comprising all stored attributes having a non-zero or non-null value, etc.).
In an alternative aspect of the present invention, there is provided a method of controlling a system, the method comprising: receiving data about the system being controlled (e.g. data input to the system, data output by the system or intermediate data generated by the system as a result of some processing of input data, etc.); associating the received data with a time factor (e.g. a timestamp or a time interval, etc.); generating or updating a set of summary bins and storing the associated values thereof within a suitable data store (preferably computer data store such as a suitable random access memory), each of which summary bins is associated with a respective period of time, and each of which stores a summary of the received data associated with its respective period of time; processing the summary bins; and generating and issuing control instructions to the system being controlled based on the results of the processing of the summary bins; wherein the periods of time associated with respective summary bins include overlapping periods of time and periods of time having different durations.
Further aspects relate to computer processor implementable instructions for causing a processor to carry out the methods of aspects of the present invention, and to carrier media, most preferably non-transient carrier media, carrying such instructions. Preferably the non-transient carrier media include one or more of the following: magnetic or optical storage disks (e.g. a magnetic hard-drive, or a CD ROM or a DVD etc.) or a volatile or non-volatile solid state memory device (e.g. a RAM chip, an EEPROM, an SSD drive, a USB thumb drive, etc.).