Automatically assigned DDC number: 00631

Manually assigned DDC number: 00631

Number of references: 4

Title: Learning Unions of Rectangles with Queries

Author:

Author:

Subject: Zhixiang Chen,Steven Homer Learning Unions of Rectangles with Queries

Description: We investigate the efficient learnability of unions of k rectangles in the discrete plane f1; : : : ; ng 2 with equivalence and membership queries. We exhibit a learning algorithm that learns any union of k rectangles with O(k 3 log n) queries, while the time complexity of this algorithm is bounded by O(k 5 log n). We design our learning algorithm by finding "corners" and "edges" for rectangles contained in the target concept and then constructing the target concept from those "corners" and "edges". Our result provides a first approach to on-line learning of nontrivial subclasses of unions of intersections of halfspaces with equivalence and membership queries. 1 Introduction Learning unions of rectangles is closely related to other central problems in machine learning theory. It is a generalization of learning DNF (disjunctive normal form) formulas and a special case of unions of intersections of half-spaces in f1; : : : ; ng d , two of the major open problems in computatio...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1994-01-11

Pubyear: 0

Format: ps

Identifier: http://citeseer.ist.psu.edu/140796.html

Source: http://www.cs.bu.edu/techreports/93-010-learning-rect.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/96531.html"   Type="inproceedings"   CiteSeer_Book="Proceedings   of   the   Sixth   Annual   ACM   Conference   on   Computational   Learning   Theory"   CiteSeer_Volume=""   Title="On-line   learning   of   rectangles   in   noisy   environments,">

            <identifier   Org="ISBN:0780331214"   Paper_ID="/96531.html"   Extracted="0780331214"   />

            <identifier   Org="ISBN:079239478X"   Paper_ID="/96531.html"   Extracted="079239478X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0897916115"   Paper_ID="/96531.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/96531.html"   Extracted="0897917235"   />

            <identifier   Org="ISBN:0897918886"   Paper_ID="/96531.html"   Extracted="0897918886"   />

            <identifier   Org="ISBN:1558603778"   Paper_ID="/96531.html"   Extracted="1558603778"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540423435"   Paper_ID="/96531.html"   Extracted="3540423435"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/96531.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540635777"   Paper_ID="/96531.html"   Extracted="3540635777"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.16666666666666666"   />

      </rec>

      <rec   ID="/273753.html"   Type="inproceedings"   CiteSeer_Book="ACM   Symposium   on   Theory   of   Computing"   CiteSeer_Volume=""   Title="Fast   Learning   of   k-Term   {DNF}   Formulas   with   Queries,">

            <identifier   Org="ISBN:0780331214"   Paper_ID="/273753.html"   Extracted="0780331214"   />

            <identifier   Org="ISBN:0897915119"   Paper_ID="/273753.html"   Extracted="0897915119"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/273753.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:0897918916"   Paper_ID="/273753.html"   Extracted="0897918916"   />

            <identifier   Org="ISBN:0898712963"   Paper_ID="/273753.html"   Extracted="0898712963"   DDC="519.2"   Normalized_DDC="5192"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:1581134959"   Paper_ID="/273753.html"   Extracted="1581134959"   />

            <identifier   Org="ISBN:3540752242"   Paper_ID="/273753.html"   Extracted="3540752242"   />

            <identifier   Org="ISBN:3540879862"   Paper_ID="/273753.html"   Extracted="3540879862"   />

      </rec>

      <rec   ID="/145196.html"   Type="article"   CiteSeer_Book="Machine   Learning"   CiteSeer_Volume="17"   Title="On-Line   Learning   of   Rectangles   and   Unions   of   Rectangles,">

            <identifier   Org="ISBN:0897916115"   Paper_ID="/145196.html"   Extracted="0897916115"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:354043836X"   Paper_ID="/145196.html"   Extracted="354043836X"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:354060216X"   Paper_ID="/145196.html"   Extracted="354060216X"   DDC="004/.01/5116"   Normalized_DDC="004015116"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540635777"   Paper_ID="/145196.html"   Extracted="3540635777"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.25"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Learning   Unions   of   Rectangles   with   Queries">

            <identifier   Org="ISBN:0818665823"   Paper_ID="SELF"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="SELF"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540591192"   Paper_ID="SELF"   Extracted="3540591192"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:354060216X"   Paper_ID="SELF"   Extracted="354060216X"   DDC="004/.01/5116"   Normalized_DDC="004015116"   Normalized_Weight="0.3333333333333333"   />

      </rec>

      <rec   ID="/292486.html"   Type="techreport"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="{COMPOSITE}   {GEOMETRIC}   {CONCEPTS}   {AND}   {POLYNOMIAL}   {PREDICTABILITY},">

            <identifier   Org="ISBN:0195085914"   Paper_ID="/292486.html"   Extracted="0195085914"   DDC="005.2"   Normalized_DDC="0052"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0262111934"   Paper_ID="/292486.html"   Extracted="0262111934"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0444891781"   Paper_ID="/292486.html"   Extracted="0444891781"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:079239478X"   Paper_ID="/292486.html"   Extracted="079239478X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0805812016"   Paper_ID="/292486.html"   Extracted="0805812016"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818643706"   Paper_ID="/292486.html"   Extracted="0818643706"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818665823"   Paper_ID="/292486.html"   Extracted="0818665823"   />

            <identifier   Org="ISBN:0818681985"   Paper_ID="/292486.html"   Extracted="0818681985"   />

            <identifier   Org="ISBN:0821837931"   Paper_ID="/292486.html"   Extracted="0821837931"   />

            <identifier   Org="ISBN:0897915119"   Paper_ID="/292486.html"   Extracted="0897915119"   />

            <identifier   Org="ISBN:0897917235"   Paper_ID="/292486.html"   Extracted="0897917235"   DDC="006.31"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0897917855"   Paper_ID="/292486.html"   Extracted="0897917855"   />

            <identifier   Org="ISBN:1558601481"   Paper_ID="/292486.html"   Extracted="1558601481"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:354060216X"   Paper_ID="/292486.html"   Extracted="354060216X"   DDC="004/.01/5116"   Normalized_DDC="004015116"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540626859"   Paper_ID="/292486.html"   Extracted="3540626859"   DDC="006.3/1"   Normalized_DDC="00631"   Normalized_Weight="0.1"   />

      </rec>

</references_metadata>