Machine learning by construction of a decision function

Data training apparatus for analysing query items, considered to be represented by respective training points within a region of feature space, and respective known answers to the query items to determine partial answers for use in evaluating answers to new query items, said apparatus comprising:

• a region subdividing portion operable to subdivide said region into subregions according to at least first and second subdivisions;
• an iteration portion which performs at least first and second iterations, corresponding respectively to said first and second subdivisions, and operable in each said iteration to calculate a partial answer for each subregion of the corresponding subdivision in dependence upon known answers to query items represented by training points, if any, in the subregion concerned and to adjust said known answers in dependence upon those partial answers so that the adjusted known answers are usable by a subsequent iteration, if any;
• and
• an output which outputs the calculated partial answers.

Data updating apparatus for analysing training query items and respective known answers to the training query items, said training query items being considered to be represented by respective training points within a region of feature space and said region being subdivided into subregions according to at least first and second subdivisions, to update precalculated partial answers usable to evaluate answers to new query items, said apparatus comprising:

• an input which receives such a training query item;
• a subregion identifying portion operable, for each said subdivision of said region, to identify which said subregion of the subdivision contains the point representing the received training query item;
• a partial answer retrieval portion having access when the apparatus is in use to a store of said precalculated partial answers for at least some said subregions of said subdivisions, and operable to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• an iteration portion which performs at least first and second iterations, corresponding respectively to said first and second subdivisions, and operable in each such iteration to update the partial answer stored for the identified subregion of the corresponding subdivision in dependence upon said known answer to said received training query item and said retrieved precalculated partial answer for the identified subregion, and to adjust said known answer in dependence upon that updated partial answer so that the adjusted known answer is usable by a subsequent iteration, if any.

A computer-implemented data processing method for evaluating answers to respective query items considered to be represented by respective points within a region of feature space, which region is subdivided into subregions according to at least first and second subdivisions, said method comprising:

• receiving such a query item;
• identifying, for each said subdivision of said region, which said subregion of the subdivision contains the point representing the received query item;
• accessing a store of precalculated partial answers for at least some said subregions of said subdivisions to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• calculating an answer to said received query item based on the retrieved partial answers;
• and
• outputting the calculated answer.

A computer-implemented data training method for analysing query items, considered to be represented by respective training points within a region of feature space, and respective known answers to the query items to determine partial answers for use in evaluating answers to new query items, said method comprising:

• subdividing said region into subregions according to at least first and second subdivisions;
• performing at least first and second iterations, corresponding respectively to said first and second subdivisions, and in each said iteration calculating a partial answer for each subregion of the corresponding subdivision in dependence upon known answers to query items represented by training points, if any, in the subregion concerned and adjusting said known answers in dependence upon those partial answers so that the adjusted known answers are usable by a subsequent iteration, if any;
• and
• outputting the calculated partial answers.

A computer-implemented data updating method for analysing training query items and respective known answers to the training query items, said training query items being considered to be represented by respective training points within a region of feature space and said region being subdivided into subregions according to at least first and second subdivisions, to update precalculated partial answers usable to evaluate answers to new query items, said method comprising:

• receiving such a training query item;
• identifying, for each said subdivision of said region, which said subregion of the subdivision contains the point representing the received training query item;
• accessing a store of said precalculated partial answers for at least some said subregions of said subdivisions to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• and
• performing at least first and second iterations, corresponding respectively to said first and second subdivisions, and in each such iteration updating the partial answer stored for the identified subregion of the corresponding subdivision in dependence upon said known answer to said received training query item and said retrieved precalculated partial answer for the identified subregion, and adjusting said known answer in dependence upon that updated partial answer so that the adjusted known answer is usable by a subsequent iteration, if any.

A computer-readable recording medium storing a program for evaluating answers to respective query items considered to be represented by respective points within a region of feature space, which region is subdivided into subregions according to at least first and second subdivisions, said program comprising:

• a receiving code portion which receives such a query item;
• a subregion identifying code portion which identifies, for each said subdivision of said region, which said subregion of the subdivision contains the point representing the received query item;
• a partial answer retrieval code portion which accesses a store of precalculated partial answers for at least some said subregions of said subdivisions to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• an answer calculation code portion which calculates an answer to said received query item based on the retrieved partial answers;
• and
• an output code portion which outputs the calculated answer.

A computer-readable recording medium storing a program for analysing query items, considered to be represented by respective training points within a region of feature space, and respective known answers to the query items to determine partial answers for use in evaluating answers to new query items, said program comprising:

• a region subdividing code portion which subdivides said region into subregions according to at least first and second subdivisions;
• an iteration code portion which performs at least first and second iterations, corresponding respectively to said first and second subdivisions, and in each said iteration calculating a partial answer for each subregion of the corresponding subdivision in dependence upon known answers to query items represented by training points, if any, in the subregion concerned and adjusting said known answers in dependence upon those partial answers so that the adjusted known answers are usable by a subsequent iteration, if any;
• and
• an output code portion which outputs the calculated partial answers.

A computer-readable recording medium storing a program for analysing training query items and respective known answers to the training query items, said training query items being considered to be represented by respective training points within a region of feature space and said region being subdivided into subregions according to at least first and second subdivisions, to update precalculated partial answers usable to evaluate answers to new query items, said program comprising:

• an input code portion which receives such a training query item;
• a subregion identifying code portion which identifies, for each said subdivision of said region, which said subregion of the subdivision contains the point representing the received training query item;
• a partial answer retrieval code portion which accesses a store of said precalculated partial answers for at least some said subregions of said subdivisions to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• and
• an iteration code portion which performs at least first and second iterations, corresponding respectively to said first and second subdivisions, and in each such iteration updating the partial answer stored for the identified subregion of the corresponding subdivision in dependence upon said known answer to said received training query item and said retrieved precalculated partial answer for the identified subregion, and adjusting said known answer in dependence upon that updated partial answer so that the adjusted known answer is usable by a subsequent iteration, if any.

A computer-readable recording medium storing partial answers created by a computer-implemented data training method for analysing query items, considered to be represented by respective training points within a region of feature space, and respective known answers to the query items to determine partial answers for use in evaluating answers to new query items, said method comprising:

• subdividing said region into subregions according to at least first and second subdivisions;
• performing at least first and second iterations, corresponding respectively to said first and second subdivisions, and in each said iteration calculating a partial answer for each subregion of the corresponding subdivision in dependence upon known answers to query items represented by training points, if any, in the subregion concerned and adjusting said known answers in dependence upon those partial answers so that the adjusted known answers are usable by a subsequent iteration, if any;
• and
• outputting the calculated partial answers.

Data processing apparatus for evaluating answers to respective query items considered to be represented by respective points within a region of feature space, which region is subdivided into subregions according to at least first and second subdivisions, said apparatus comprising:

• an input for receiving such a query item;
• subregion identifying means operable, for each said subdivision of said region, to identify which said subregion of the subdivision contains the point representing the received query item;
• partial answer retrieval means having access when the apparatus is in use to a store of precalculated partial answers for at least some said subregions of said subdivisions, and operable to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• answer calculation means for calculating an answer to said received query item based on the retrieved partial answers;
• and
• an output for outputting the calculated answer.

Data training apparatus for analysing query items, considered to be represented by respective training points within a region of feature space, and respective known answers to the query items to determine partial answers for use in evaluating answers to new query items, said apparatus comprising:

• region subdividing means operable to subdivide said region into subregions according to at least first and second subdivisions;
• iteration means for performing at least first and second iterations, corresponding respectively to said first and second subdivisions, and operable in each said iteration to calculate a partial answer for each subregion of the corresponding subdivision in dependence upon known answers to query items represented by training points, if any, in the subregion concerned and to adjust said known answers in dependence upon those partial answers so that the adjusted known answers are usable by a subsequent iteration, if any;
• and
• output means for outputting the calculated partial answers.

Data updating apparatus for analysing training query items and respective known answers to the training query items, said training query items being considered to be represented by respective training points within a region of feature space and said region being subdivided into subregions according to at least first and second subdivisions, to update precalculated partial answers usable to evaluate answers to new query items, said apparatus comprising:

• an input for receiving such a training query item;
• subregion identifying means operable, for each said subdivision of said region, to identify which said subregion of the subdivision contains the point representing the received training query item;
• partial answer retrieval means having access when the apparatus is in use to a store of said precalculated partial answers for at least some said subregions of said subdivisions, and operable to retrieve from the store the partial answers for the or each identified subregion that is present in the store;
• iteration means for performing at least first and second iterations, corresponding respectively to said first and second subdivisions, and operable in each such iteration to update the partial answer stored for the identified subregion of the corresponding subdivision in dependence upon said known answer to said received training query item and said retrieved precalculated partial answer for the identified subregion, and to adjust said known answer in dependence upon that updated partial answer so that the adjusted known answer is usable by a subsequent iteration, if any.