Theoretical Underpinnings of Version Spaces

1 Introduction and Motivation

The problem of inductive concept learning-to form gen­ eral rules from data-has been well-studiedin machine learn­ ing and artificial intelligence [Buchanan and Mitchell, 1978; Michalski and Chilausky, 1980; Mitchell et al., 1983; Quin­ lan, 19831. The problem can be stated as follows:

Given:

• Training Data: Positive and negative exam­ ples of a concept to be identified.
• Concept Description Language: A language in which the final concept definition must be expressed.

Determine:

• The desired unknown concept.

Mitchell [1978; 1982] proposed an approach to this problem that maintains all elements of the concept description lan­ guage that could be the desired unknown concept, namely, those that correctly classify the given training data (i.e., that

I

are consistent with the data); this set is known as a version space. However, this set can be cleverly represented by only maintaining the minimal and maximal elements of the set, known as the boundary sets of the· version space. As further data are obtained, the set of possibilities is refined until ideally only one consistent result remains. This approach has been highly influential to work in concept learning, as it formalizes inductive concept learning as a search problem-to identify some concept definition out of a space of possible definitions.

This paper presents the theoretical underpinnings of version spaces, beginning with the conditions under which a set of concept definitions can be represented by boundary sets. It also presents the conditions under which the intersection and union of two version spaces is a version space, and how the resulting boundary sets can be computed from the boundary sets of the original version spaces.

These questions are important for a number of reasons. First, they clarify Mitchell's own formalization of version spaces and its central term, admissibility [Mitchell, 1978, page 61l. Second, his version-space learning algorithm, the candidate-elimination algorithm, can be expressed as a version-space intersection process [Hirsh, 1990a; Hirsh, 1990b], and thus answering the question of when intersections are legal also answers the question of when the candidate­ elimination algorithm can be used. Finally, both version­ space intersections and unions have proven useful in extend­ ing version spaces beyond strict consistency with data [Hirsh, 1990a; Hirsh, 1990cl

2 Background

The traditional scenario for inductive concept learning begins with a set of training data-examples classified by an un­ known target concept-and a language in which the desired concept must be expressed (which defines the space of pos­ sible generalizations concept learning will search). Mitchell defines a version space to be "the set of all concept descrip­ tions within the given language which are consistent with those training instances" [Mitchell, 1978, page 171. Mitchell noted that the generality of concepts imposes a partial order that allows more efficient representation of the version space by the boundary sets S and G representing the most specific and most general concept definitions in the space. The S- and G-sets delimit the set of all concept definitions consistent with the given data-the version space contains all concepts as or more general than some element in S and as or more specific than some element in G.

Given a new instance, some of the concept definitions in the version space for past data may no longer be consistent with the new instance. The candidate-elimination algorithm ma­ nipulates the boundary-setrepresentation of a version space to create boundary sets that represent a new version space con­ sistent with all the previous instances plus the new one. For a positive example the algorithm generalizes the elements of the S-set as little as possible so that they cover the new instance yet remain consistent with past data. and removes those ele­ ments of the G-set that do not cover the new instance. For a negative instance the algorithm specializes elements of the G-set so that they no longer cover the new instance yet remain consistent with past data, and removes from the S -set those el­ ements that mistakenly cover the new, negative instance. The unknown concept is determined when the version space has only one element, which in the boundary set representation is when the S-and G-sets have the same single element.

3 Terminology and Notation

Throughout this paper "CDL'' is used to refer to the (poten­ tially infinite) set of concept definitions describable in the con­ cept description language and considered in the concept learn­ ing task. There is a space of possible objects (instances), and each concept definition divides a set of objects into those ob­ jects it covers and those it does not. The subset of the entire space of possible objects that a concept definition covers is known as its extension. Concept definitions are partially or­ dered by generality, "~." "Ct ~ C2" should be read as "Ct is less general than or equal to C2,'' which means that the ex­ tension of Ct is a subset of the extension of C2. "Ct ~ C2,'' "Ct t C2,'' and "C1 >- C2" have similar, obvious meanings.

Theorem 1 (Mitchell, 1978) The relation ~ is a partial or­ dering.

Proof: The reflexivity, asymmetry, and transitivity fall out of the definition of ~ using subset. Since the subset relation is a partial ordering, so, too, is~ a partial ordering. 0

The concept learning problem is to identify one concept definition out of the set of potential concept definitions in the CDL, given information from some outside source about the nature of the unknown concept. Usually this information is of the form of positive and negative examples of this target concept, that is, classified training data of the concept.

4 Criteria for Representability by Boundary Sets

This section presents the first major results of this paper, namely, criteria that, if satisfied by a subset of a concept de­ scription language, make that subset representable by bound­ ary sets. First, however, it is necessary to define two terms, convexity and definiteness. 1 This section will show that a subset of a concept description language is representable by boundary sets if and only if it is convex and definite.

1 Earlier versions of this work [Hirsh, 1990a] used the terms "clo­ sure" and "boundedness". Convexity and definiteness better reflect existing terminology in lattice theory.

4.1 Convexity

A set C of concept definitions in the CDL is said to be con­ vex if, given any two elements of C, any element of the con­ cept description language between them (in the partial order) is also in C. This basically says that there are no "holes" in the set. More formally:

Definition 1 A subset C ~ CDL is said to be convex if and only if for all c1 ,c2 E C, c3 E CDL, c1 ~ c3 ~ c2 implies C3 E C.

Examples:

1. If the CDL is the set of all closed ranges over a single real-valued attribute x of the form " { x I a ~ x ~ b}" where a and bare reals (in less formal terins, this cor­ responds to the case where data are described using a single real-valued feature, and concept descriptions can only constrain the possible values for this feature to var­ ious closed intervals):
2. (a) If C = CDL, then C is convex.
3. (b) IfC = {c E CDL I a, bare integers}, then Cis not convex, since between any two concept definitions there will be another whose range delimiters a and b are reals but not integers.
4. (c) IfC = {c E CDL I a~ 0, b ~ 1000}, then Cis convex.
5. Given any CDL, if C is the set of all concept definitions consistent with a set of classified instances, C is convex.

4.2 Definiteness

To define definiteness, it is necessary to state what the minimal and maximal elements of a partially ordered set are:

Definition 2 The set of minimal elements of C is written Min( C), and is defined by

Similarly, the set of maximal elements ofC, Max( C), is

C is said to be definite if all elements of C are greater than or equal to some element of Min( C) and less than or equal to some element of Max( C). More formally:

Definition 3 C is definite if and only if for all c E C there exists some s E Min( C) and some g E Max( C) such that s ~ c ~g.

Min( C) is often referred to as C's S-set, and Max( C) is C's G-set, and Sand G should be viewed as shorthand for Min( C) and Max( C). Note that this definition of definiteness does not constrain either S or G to be finite.

Examples:

1. If the CDL is the set of closed ranges of the form { :z: I a ~ :z: ~ b} where a and b are reals:
2. (a) If C = CDL, then C is not definite, since G = {} (for every concept definition in the language there is another concept definition more general than it), and thus for every element c E C there is no g E G withc~g.

• (b) If C = {c E CDL I a, bare integers}, then G = {}, so C is not definite.
• (c) IfC = {c E CDL I a~ O,b ~ 1000},thenS = {{0}, ... , {1000}}, G = {{:z: I o ~ :z: ~ 1000}}, and C is definite.
• If the CDL is the set of all conjunctive expressions over a finite set of boolean features, then all subsets C ~ CDL are definite.

This second example is a simple result of the following the­ orem:

Theorem 2 If the CDL is finite (i.e., there are only a finite number of concept definitions expressible) then all subsets C of the CDL are definite.

Proof: By induction on the size of C. D

The concept of definiteness is closely related to Mitchell's (1978) notion of admissibility. 2 Admissibility is intended as a property of concept description languages-whether all sub­ sets of the language can be represented by boundary sets. The concept of definiteness applies to subsets of the concept de­ scription language. It is possible to have languages with sub­ sets that are not definite, yet also with some subsets that are definite. The important thing to guarantee is that only defi­ nite subsets will be used during the particular learning task at hand. Admissibility is a stronger restriction.

4.3 Representability by Boundary Sets

It is now possible to identify which subsets of a CDL can be represented by only retaining their minimal and maximal el­ ements (i.e., boundary sets). However, it is first necessary to state precisely what it means to be representable by boundary sets:

Definition 4 lfC ~ CDL, S =Min( C), and G =Max( C), Cis said to be representable by boundary sets if and only if

This definition states that C is representable by boundary sets if the set of elements between the minimal and maximal ele­ ments of C gives back C.

It can now be shown that any convex, definite subset C ~ CDL can be represented by boundary sets:

Theorem 3 All convex, definite subsets C of a CDL can be represented by boundary sets.

Proof: Showing that a set C can be represented by boundary sets is done by first demonstrating that

(where S = Min( C) and G = Max( C)) then demonstrating that

First the~: If d E C then there exists an sinS and g in G such that s ~ c' ~ g (since Cis definite). Furthermore, since c' E C and C ~ CDL, c' E CDL. Therefore

2 Mitchell defines a concept description language to be admissible if and only if every chain has a maximum and minimum element.

means that there is an s in S for which s ~ c' and a g in G where c' ~g. Since S, G ~ C, s, g E C. Since Cis convex, this means that c' E C, and thus that

The converse can also be shown to be true, namely, that all subsets C ~ CDL that can be represented by boundary sets are convex and definite. This demonstrates that convexity and definiteness are both necessary and sufficient conditions on when an arbitrary subset of a CDL can be represented by boundary sets.

Theorem 4 All subsets C of a CDL that can be represented by boundary sets are convex and definite.

Proof: The definiteness portion of the proof is trivial. For all c E C there exists s E S = Min(C) and g E G = Max( C) such that s ~ c ~ g (since C can be represented by boundary sets). This is for any c E C. Thus Cis definite. For convexity: Given Ct, c2 E C, it is necessary to show for all c3 E CDL when Ct ~ c3 ~ c2, c3 E C. Since c1 E C and C can be represented by boundary sets, there exists s E S such that s ~ ct. Similarly there exists g E G such that c2 ~ g. Since ct ~ c3 ~ c2, s ~ c3 ~ g. But by the definition of ''representable by boundary sets" this means c3 E C. D

4.4 Generalizing Version Spaces

Mitchell defined a version space to be the set of all concept de­ scriptions in a prespecified language that are consistent with data. The important quality that such sets have is that they can be represented by their boundary sets. This section has shown that representability by boundary sets is equivalent to convex­ ity plus definiteness. This section can thus can be viewed as generalizing Mitchell's consistency-based version spaces to arbitrary subsets of a concept description language repre­ sentable by boundary sets, or equivalently, to convex and def­ inite subsets of the concept description language. The results of the remainder of this paper apply to both Mitchell's origi­ nal notion of version space as well as this more general form. The term "version space" will be used throughout, but can be replaced with "convex definite subsets of the CDL". 3 ·

5 Version-Space Intersections

This section presents conditions under which the intersection of two version spaces is a version space, an important ques­ tion since Mitchell's candidate elimination algorithm can be expressed as a version-space intersection process. This sec­ tion furthermore provides a method for doing this intersection in boundary-set representation; such version-space intersec­ tion forms the basis for an alternative version-space learning algorithm [Hirsh, 1990a; Hirsh, 1990bl.

3 The results presented here apply more generally to convex spaces; Gunter et al. [1991] have explored this generalization of the work presented here and apply it to ATMSs, where convex spaces also arise.

It is first useful to note that the intersection of two version spaces is always convex:

Theorem 5 Given two version spaces VS1 and VS2, their in­ tersection vsl n vs2 is convex.

Proof: VS1 n VS2 is convex if for all c1 E vs, n VS2, c2 E VS1 ·n vs2. and c3 E CDL, c1 ~ c3 ~ c2 implies c3 E VS1 n VS2. Since both ct and c2 are in VS1 n VS2, they are both in VS1 and VS2. Since both VS1 and VS2 are convex (since they are version spaces), c3 E VS1 and c3 E VS2. But this means c3 E vs1 n vs2. o

A simple corollary of this is

Corollary 1 The intersection of two version spaces is a ver­ sion space if and only if the intersection is definite.

Note that the intersection of two version spaces VS1 and VS2 is not necessarily definite. To see this consider the con­ cept description language in which concept definitions are closed ranges of reals over a single variable z of the form "{z I a~ z ~ b}", but with the term "{z I 0 ~ z ~ 10}" excluded. If VS1 contains all concept definitions as or more general than " { z I 0 ~ z ~ 5}" and as or less general than "{x l-1000~ z ~ 1000}"andVS2containsallconceptdef­ initions as or more general than " { z I 5 ~ z ~ 10}" and as or less general than "{z I -1000 ~ z ~ 1000}," then their in­ tersection is still a subset of the concept description language but is no longer definite. The problem is that Min(VS1 n VS2) is empty. The desired minimal element for the intersection would ideally have been"{ x I 0 ~ x ~ 10}," but this is not in the language. .

When the intersection of two version spaces is indeed defi­ nite, rather than explicitly intersecting the two version spaces by enumerating each of their elements, it is possible to com­ pute the boundary sets for the intersection directly from the boundary sets of the two original version spaces. This is done by finding the minimal common generalizations of pairs of S -set elements for the new S -set and the maximal common specializations of pairs of G-set elements for the new G-set, and removing the overly general elements from the newS­ set and overly specific elements from the new G-set. To state this formally it is necessary to present what the most specific common generalizations (MSG) and most general common specializations (MGS) of two concept definitions are:

MSG(A,B) = { C I A ~ C and B ~ C and there is no D

such that D -< C with A ~ D and B ~ D}

MGS(A,B) = { C I C ~ A and C ~ B and there is no D such that C -< D with D ~ A and D ~ B}.

It is now possible to state more formally how the boundary sets for the intersection of two version spaces, when it is itself a version space, can be computed:

Theorem 6 (Version-Space Merging Algorithm) If VS1 n VS2 is definite, then Min(VS1 n VS2) = S1n2 and Max(VS1 n VS2) = G1n2. where S1n2 and G1n2 are determined as fol­ lows:

S1n2 = Min( { 8 E MSG( 81, 82) I 81 E S1 and 82 E S2, and 3gl E G1, Y2 E G2 with 8 ~ g1 and 8 ~ g2})

and G1n2 =Max( {g E MGS(g1, g2) I Yl E G1 and Y2 E G2, and 381 E S1, 82 E S2 with81 ~ g and 82 ~ g}).

Proof: This is done for the S-set case (the proof for the G­ set case is analogous) by first showing thatS,n2 s;:; Min(VS1 n VS2), then showing S1n2 2 Min(VS1 n VS2). Both cases use the following lemma:

Lemma 1 If cis in the set { 8 E MSG( 81, 82) I 81 E S1 and 82 E S2, and 3gl E G1, g2 E G2 with 8 ~ Yl and 8 ~ g2}. then cis in VS1 n VS2.

Proof: c E {8 E MSG(81, 82) I 81 E sl and 82 E s2. and 3gl E G1. g2 E G2 with 8 ~ g1 and 8 ~ g2} means c E MSG(8t, 82) for some 81 E S1 and 82 E S2. This means 81 ~ c and 82 ~ c (by the definition of MSG), which shows that c has some element from each of the two original S -sets below it. But furthermore c E { 8 E MSG( 81, 82) I 81 E S1 and 82 E S2, and 3gl E G1. Y2 E G2 with 8 ~ Yl and 8 ~ g2} means 3gl E G1, g2 E G2 with c ~ Yl and c ~ g2. which shows that c has some element from each of the two original G-sets below it. Therefore c E VS1 and c E VS2, and so c E vs1 n vs2. o

First the s;:;: If c E S1n2. then c E {8 E MSG(81, 82) I 81 E S1 and 82 E S2, and 3gl E G1, g2 E G2 with 8 ~ g1 and 8 ~ Y2}, so c E VS 1 n VS2 by Lemma 1. To show that c E Min(VS1 n VS2) it is necessary to show that there is no c' -< c with c' E VS1 n VS2. However, to show that there is no such c' -< c, it is sufficient to show that there is no 8 E Min(VS1 n VS2) such that 8 -< c (since the definiteness of VS 1 n VS2 means that if there were SUCh a c' ...( c, there WOUld be such an 8). This will be shown by contradiction.

Suppose there is an 8 E Min(VS1 n VS2) such that 8 -< c. 8 E Min(VS1 n VS2) means 8 E VS1 n VS2, so 8 E VS1 and 8 E VS2. This in turn means there is some 81 E S1 and some 82 E S2 with 81 ~ 8 and 82 ~ 8. Finally, there is no 8 1 -< 8 with 81 ~ 8 1 and 82 ~ 8 1 (otherwise 8 1 would be in VS1 n VS2, and so 8 would not be in Min(VS1 n VS2)). Thus 8 E MSG(81, 82). and since 8 is in VS1 and in VS2 there is some g1 E G1 and some g2 E G2 with 8 ~ Yl and 8 ~ Y2· Therefore 8 E { 8 E MSG( 81' 82) I 81 E sl and 82 E s2. and 3gl E G1, g2 E G2 with 8 ~ Yl and 8 ~ g2}. which contradicts the fact that cis a minimal element of this set (c E S1n2).

For the ;2: If c E Min(VS, n VS2). then c E VS1 n VS2. This means that c E VS1 and c E VS2, and furthermore there is some 81 ~ S1 and some 82 E S2 with 81 ~ c and 82 ~ c. Finally, thete is no c' -< c with 81 ~ c' and 82 ~ c' (otherwise c' would be in VS1 n VS2, and soc would not be in Min(VS1 n VS2)). Thus c E MSG(81, 82). and since cis in VS1 and in VS2 there is some Yl E G1 and some g2 E G2 with c ~ g1 and c ~ Y2· Therefore c E {8 E MSG(81, 82) I 81 E S1 and 82 E S2, and 3gl E G1, Y2 E G2 with 8 ~ Yl and 8 ~ Y2}·

To show that c is a minimal element of this set, and thus in S1n2. it is necessary to show that there is no c' E { 8 E MSG(81, 82) I 81 E S1 and 82 E S2, and 3gl E G1, g2 E G2 with 8 ~ g1 and 8 ~ g2} with c' -< c. This is true because if there were such a c', it would be in VS1 n VS2 (by Lemma 1), which would mean that cis not in Min(VS1 n VS2), which would be a contradiction. D

Note that Theorem 6 presents a method for computing in­ tersections in theory, but to be practical the computations must take a finite amount of time. In particular, computing MSG(81, 8z) must take a finite amount of time. If there are infinite chains in the concept description language, the pro­ cedure for computing MSG might never halt if it traverses the partial order. Thus in real applications MSG will often be computed from the syntactic form of 81 and 82, rather than traversing the partial order. For example, to determine MSG( { :c I a1 ~ :c ~ bt}, { :c I az ~ :c ~ bz}) a pro­ cedure for computing MSG directly from the partial order would never halt, since there are an infinite number of con­ cept definitions more general than each of the concept defini­ tions. However, it is a simple matter to compute their most specific common generalization from their syntactic form: {z I min( a,, az) ~ :c ~ max(b,, bz)}. Typically MSG is defined for specific concept description languages to manip­ ulate the syntactic structures so it need not face infinite-chain difficulties.

6 Version-Space Unions

This section discusses unions of version spaces, and presents conditions under which the union of two version spaces is a version space, as well as a method for doing unions in boundary-set representation. Such version-space union has proven useful for dealing with certain forms of noisy data [Hirsh, 1990a; Hirsh, 1990c].

It is first useful to note that the union of two version spaces is always definite:

Theorem 7 Given two version spaces VS1 and VSz, their union VS, U VSz is definite.

Proof: For any c E vs, U VSz, either c E vs, or c E VSz. Without loss of generality, assume c E vs,. To show that VS1 u VS2 is definite, it is necessary to show that there is some 8 E Min(VS, u VSz) with 8 :; c. The proof that there is some g E Max(VS, U VSz) with c :; g is analogous.

Since c E VS1, there is somes E s, with 8 ~c. Either 8 E Min(VS1 u VS2), in which case there is some; E Min(VS, U VSz) with 8 :; c, or else 8 ¢ Min(VS1 uVSz). If this latter case is true, there must be some c' E vs, U VSz with c' ~ s. Since sis in S1, c' must be in VSz. But VSz is a version space, and hence definite, so there is some 8 1 E Sz with 8 1 ~ c'. Since c' ~ 8, this means 8 1 ~ 8. But 8 E S1, so there is no c" E VS1 with c" ~ 8 1 · Also, there is no c" E VSz with c" ~ 8 1 (since 8 1 E Sz). This means 8 1 E Min(VS1 U VSz). Thus for any c E vs, u VSz there is some 8 E Min(VS, u VSz) with 8 :; c. 0

A simple corollary of this is

Corollary 2 The union of two version spaces is a version space if and only if the union is convex.

Note that just as the intersection of two version spaces need not be a version space, similarly the union of two ver­ sion spaces need not be a version space. To see this con­ sider any concept description language with three elements ct ~ cz ~ c3. Let VS 1 = { ct} and VSz = { c3}. The union of the two version spaces is { c,, c3}, but this doesn't include cz, which it must if it is to be convex and a version space.

Just as for intersections, the minimal and maximal elements for the union of two version spaces can be determined di­ rectly from the boundary sets for the two version spaces being unioned. These form the boundary sets for the union when the union is convex and thus a version space.

Theorem 8 (Version-Space Union Algorithm) Min(VS 1 u VSz) = S1u2 and Max(VS, U VSz) = G1u2· where S1u2 = Min(S, U Sz) and G1u2 = Max( G, U Gz).

Proof: This is done for S1u2 by first showing that S1u2 c Min(VS, U VSz), then showing that S1u2 2 Min(VS, U VSzf. The proof for G1u2 is analogous.

For the~: If c E S1uz. then c E Min(S, u Sz). This means cis ins, u Sz, which in tum means c E s, or c E Sz, and thus c E vs, or c E VSz. Hence c E vs, u VSz. To show that c is a minimal element of this set it is necessary to show that there is no c' E VS1 u VS2 with c' ~ c. Assume there is such a c'. Then it is either in VS1 or VS2· Without loss of generality assume it is in VS1. Then there must be some 81 E S1 with 8 :; c' (since VS1 is a version space). This 81 is in S1, so it is ins, USz. But since 81 :; c' ~ c, c cannot be in Min(S, USz). This is a contradiction. Therefore there is no c' E VS1 U VSz with c' ~ c, and thus c E Min(VS, U VSz)

For the ;2: If c E Min(VS, U VSz), then c E VS, U VSz and there is no c' E vs, U VSz with c' ~ c. This means c E VS1 or c E VSz. Assume c E VS,. c must be ins,, since cis in Min(VS1 U VS2), which means there is no c' E VS1 with c' ~ c. The case for c E VSz is analogous. Thus c E S1 U S2· Furthermore, there is no c" E s, U Sz with d' ~ c (otherwise c would not be in Min(VS, u VSz), since d' E s, u S2 means c" E VS, U VSz). Thus c E S1u2· 0

7 Concluding Remarks

This paper has presented formal results on the range of appli­ cability of version spaces. It analyzed when a set of concept definitions is a version space, as well as when the intersection and union of version spaces yields a version space. It also gave methods to do such intersection and union in boundary­ set representation, and proved that the algorithms to do so are correct.

An interesting open problem is how a version-space-like approach can be used even for arbitrary (nonconvex or non­ definite) sets of concept definitions. One approach would be to represent arbitrary sets as nested differences of version spaces. The intersection and union procedures could utilize facts such as (A- B) n (C-D) = (An C)- (BUD), as well as simplifications such as A- B =A if An B = 0, and (A- 0) = A. Ultimately operations will bottom out at intersections and unions of version spaces.

A final issue to consider is the size of boundary sets. The simplest question that should be answered is under what con­ ditions can a version space be represented by finite bound­ ary sets. Clearly one sufficient condition for finite boundary­ set size is if the version space is itself finite. Gunter et al. [ 1991] generalize the work presented here to give comparable conditions on when a version space is representable by finite boundary sets. Equally important is answering the question of how large the finite boundary-set size is. Haussler [1988] has shown that boundary sets can grow exponentially in the num­ ber of instances processed. However, Smith and Rosenbloom [Smith and Rosenbloom, 1990] show that, for tree-structured languages under certain conditions data can be processed to guarantee that boundary sets stay singleton. Understanding under what conditions exponential growth happens and how to avoid it is important in determining the practical utility of version spaces. These are questions for future work.

Acknowledgments

This paper presents an updated version of Chapter 8 of the author's doctoral dissertation [Hirsh, 1990al, where more lengthy acknowledgments can be found. Johanna Seibt helped with initial formalizations. Dave Smith provided feed­ back on a very early draft, and William Cohen on a more re­ cent one. Discussions with Bruce Buchanan, Carl Gunter, Jeff Kahn, Bill Landi, Tom Marlowe, Tom Mitchell, Teow-Hin Ngair, Paul Rosenbloom, and Devika Subramanian were in­ valuable.