A widespread folklore for explaining the success of Convolutional Neural Networks (CNNs) is that CNNs use a more compact representation than the Fully-connected Neural Network (FNN) and thus require fewer training samples to accurately estimate their parameters. We initiate the study of rigorously characterizing the sample complexity of estimating CNNs. We show that for an $m$-dimensional convolutional filter with linear activation acting on a $d$-dimensional input, the sample complexity of achieving population prediction error of $\epsilon$ is $\widetilde{O(m/\epsilon^2)$, whereas the sample-complexity for its FNN counterpart is lower bounded by $\Omega(d/\epsilon^2)$ samples. Since, in typical settings $m \ll d$, this result demonstrates the advantage of using a CNN. We further consider the sample complexity of estimating a one-hidden-layer CNN with linear activation where both the $m$-dimensional convolutional filter and the $r$-dimensional output weights are unknown. For this model, we show that the sample complexity is $\widetilde{O}\left((m+r)/\epsilon^2\right)$ when the ratio between the stride size and the filter size is a constant. For both models, we also present lower bounds showing our sample complexities are tight up to logarithmic factors. Our main tools for deriving these results are a localized empirical process analysis and a new lemma characterizing the convolutional structure. We believe that these tools may inspire further developments in understanding CNNs.

However, a few new twists were added to the 1995 competition. First, a complete topological map of the environment was not available. Instead, a set of instructions, for example, "turn third left" and "go past foyer," would guide the robot through the hallways toward a goal room. Second, it would be possible that the instructions contained an error, such as directing the robot toward a nonexistent hallway or room. Third, the information provided in the instructions only specified a number of "openings" that had to be detected before turning into another hallway or entering the goal room. Only the nature of the last opening of every instruction could be inferred (a hallway in the case of a turn instruction or a doorway in the case of an enter instruction), but the intermediate openings could be of any type. The lack of a more qualitative description of the environment limited the capabilities of the probabilistic navigation algorithm on the robot, which could only be used as a sophisticated feature counter (figure 1).

These methods and ideas are discussed here. LOLA's console and see an LOLA's hard drive had decided to crash Performing all computation on board has several advantages: The video data are not corrupted by radio-transmission noise, commands are not lost, and there's no communication lag that might result in These findings are consistent with those of previous competitors (Nourbakhsh, Powers, and Birchfield 1995). On the down side, the on-board image processor contributes significantly to the battery drain, which is partly the result of its intended desktop use. Still, we are able to get about two hours of operation to each charge. Nomadic Technologies is currently making efforts to offer a version that is better suited for mobile robot use. Figure 1.

A method for unrestricted recognition of three-dimensional objects was developed. By unrestricted, we imply that the recognition will be done independently of object position, scale, orientation, and pose against a structured background. It does not assume any preceding segmentation or allow a reasonable degree of occlusion. The method uses a hierarchy of triplet feature invariants, which are at each level defined by a learning procedure. In the feedback learning procedure, percepts are mapped on system states corresponding to manipulation parameters of the object.

Probability concepts for rule-baaed expert systems are developed that are compatible with probability used in data fusion of imprecise information Procedures for treating probabilistic evidence are presented, which include the effects of statistical dependence. Confidence limits are defined as being proportional to root-mean-square errors in estimates, and a method is outlined that allows the confidence limits in the probability estimate of the hypothesis to be expressed in terms of the confidence limits in the estimate of the evidence. Procedures are outlined for weighting and combining multiple reports that pertain to the same item of evidence. These programs use a collection of facts, rules of thumb, and other knowledge about a limited field to help make inferences in the field. They differ substantially from conventional computer programs in that their goals may have no algorithmic solution, and they must make inferences based on incomplete or uncertain information.

Introduction: Typical Uses of Heuristics Heuristics are methods and criteria for judging the relative merits of alternative courses of planning or action. There is hardly any intellectual activity which does not rely on heuristics of some kind. The decision to begin reading this paper, for example, reflects a tacit use of heuristics which has lured the reader to invest time and effort in anticipation of certain benefits. Ahhough such anticipations may occasionally be disappointed, on the whole they are essential to planning our everyday activities. Complex combinatorial problems require the use of heuristics if a reasonably "good" solution is to be produced We shall demonstrate this point using three simple problems (readers familiar with the properties of A' may skip to section Where do these heuristics come from?):

An adequate natural language description of developments in a real-world scene can be taken as proof of "understanding what is going on." An algorithmic system that generates natural language descriptions from video recordings of road traffic scenes can be said to "understand" its input to the extent that algorithmically generated text is acceptable to the humans judging it. The ability to present a "variant formulation" without distorting the essential parts of the original message is taken as a cue that these essentials have been "understood." During art lessons, in particular those concerned with classical or ecclesiastic paintings, students are initially invited to merely describe what they see. Frequently, considerable a priori knowledge about ancient mythology or biblical traditions is required to succinctly characterize the depicted scene. Lack of the corresponding knowledge about other cultures can make it difficult for someone with only a European education to really understand and describe in an appropriate manner a painting by, for example, a Far East classic artist. Familiar human experiences mentioned in the preceding paragraph will now be "morphed" into a scientific challenge: to design and implement an algorithmic engine that generates an appropriate textual description of essential developments in a video sequence recorded from a real-world scene. Such an algorithmic engine will serve as one example of a cognitive vision system (CVS), which leaves room, as the experienced reader has noticed, for there to be more than one way to introduce the concept of a CVS. An alternative clearly consists in coupling a computer vision system with a robotic system of some kind and assessing the reactions of such a compound system. To whomever accepts the formulation, "one of the actions available to an agent is to produce language. This is called a speech act. Russell and Norvig (1995)" is unlikely to consider the two variants of a CVS alluded to previously as being fundamentally different. With regard to the first CVS version in particular, the following remarks are submitted for consideration: Obviously, we avoid a precise definition of understanding in favor of having humans compare the reaction of an algorithmic engine to that expected from a human. This fuzzy approach toward the circumscription of a CVS opens the road to constructive criticism--that is, to incremental system improvement--by pinpointing aspects of an output text that are not yet considered satisfactory.

In trying to attack domain-independent planning as heuristic search, the main difficulty lies in the automatic derivation of the heuristic function. For human algorithm designers, a common approach to deriving a heuristic is to relax the problem at hand into a simpler problem ' that can be solved efficiently. Facing a search state in, one can then use the solution length of the same state in ' to estimate its difficulty. Bonet, Loerincs, and Geffner (1997) proposed a way of applying this idea to domainindependent planning. They relax the highlevel problem description by simply ignoring delete lists.

Of all the parts that make up a Ford motor vehicle, the majority are actually manufactured by external suppliers, then purchased by Ford. To effectively manage this substantial vehicle cost component, Ford dedicates a whole division to this task. Purchase Cost Estimation and Analysis (PCE&A) employs a large number of estimators in Europe, typically production engineers, each one an expert in some area of vehicle component manufacture. The estimator is first involved at the design stage for future vehicle model programs. Working from initial engineering drawings, they provide feedback on production feasibility and economic considerations.

This article describes a theory of reasoning about uncertainty, baaed on a representation of states of certainty called endorsements The theory of endorsements is an alternative to numerical methods for reasoning about uncertainty, such as subjective Bayesian methods (Shortliffe and Buchanan, 1975; Duda, Hart, and Nilsson, 1976) and the Shafer-Dempster theory (Shafer, 1976). The fundamental concern with numerical representations of certainty is that they hide the reasoning that produces them and thus limit one's reasoning about uncertainty While numbers are easy to propagate over inferences, what the numbers mean is unclear The theory of endorsements provides a richer representation of the factors that affect certainty and supports multiple strategies for dealing with uncertainty. People's certainty of the past is limited by the fidelity of the devices that record it, their knowledge of the present is always incomplete, and their knowledge of the future is but speculation. Even though nothing is certain, people behave as if almost nothing is uncertain. They are adept at discounting uncertainty - making it go away.