# Behavioral Shaping for Geometric Concepts

Manu Chhabra, Robert A. Jacobs, Daniel Štefankovič.

Year: 2007, Volume: 8, Issue: 64, Pages: 1835−1865

#### Abstract

In a search problem, an agent uses the membership oracle of a target
concept to find a positive example of the concept. In a *shaped
search problem* the agent is aided by a sequence of increasingly
restrictive concepts leading to the target concept (analogous to
behavioral shaping). The concepts are given by membership oracles, and
the agent has to find a positive example of the target concept while
minimizing the total number of oracle queries. We show that for the
concept class of intervals on the real line an agent using a bounded
number of queries *per oracle* exists. In contrast, for the
concept class of unions of two intervals on the real line no agent
with a bounded number of queries per oracle exists. We then
investigate the (amortized) number of queries per oracle needed for
the shaped search problem over other concept classes. We explore the
following methods to obtain efficient agents. For axis-parallel
rectangles we use a bootstrapping technique to obtain gradually better
approximations of the target concept. We show that given rectangles
*R* ⊆ *A* ⊆ ℝ^{d} one can
obtain a rectangle *A'* ⊇ *R*
with vol(*A'*) / vol(*R*) ≤ 2, using only *O*(*d*
⋅ vol(*A*) / vol(*R*)) random samples from *A*. For ellipsoids of
bounded eccentricity in ℝ^{d} we analyze a deterministic ray-shooting
process which uses a sequence of rays to get close to the
centroid. Finally, we use algorithms for generating random points in
convex bodies (Dyer et al., 1991; Kannan et al., 1997) to give a randomized agent for the
concept class of convex bodies. In the final section, we explore
connections between our bootstrapping method and active
learning. Specifically, we use the bootstrapping technique for
axis-parallel rectangles to active learn axis-parallel rectangles
under the uniform distribution in *O*(*d* ln(1/ε)) labeled
samples.