To understand the flow of this chapter, the reader might want to first reread Chapter 3. That chapter remarked that any inductive process is fundamentally biased. That is, human reasoning and data mining algorithms search for models in their own particular biased way. This is unavoidable as the space of models that can be generated from any data set is very large. If we understand and apply user goals, then we can quickly focus a data mining project on the small set of most crucial issues. Hence, it is vital to talk to users in order to lever age their biases to better guide the data mining. The lesson of this chapter is that bias is a first-class modeling construct. It is important to search out, record, and implement biases because, as shown below, different biases lead to radically different results.

23.2.2 The problem with exploring values

In software engineering, biases are expressed as the values business users espouse for a system. Barry Boehm [41] advocated assessing software development technologies by the value they give to particular stakeholders. Note that this is very different from the standard practice (which assesses technologies via their functionality).

In his description of value-based SE, Boehm favors continuous optimization methods to conduct cost/benefit trade-off studies. Translated into the terminology of this book, he is advocating data mining methods that are tuned to different value propositions.

A problem with this kind of trade-off is that it must explore some underlying space of options. In a conventional approach, some business process model could be developed, then exercised many times. Such a data farming approach

1. Plants a seed. Build a model from domain information. All uncertainties or missing parts of the domain information are modeled as a space of possibilities.

2. Grows the data. Execute the model and, when the model moves into the space of possibilities, output is created by selecting at random from the possibilities.

3. Harvests. Summarize the grown data via data mining.

4. Optionally, use the harvested summaries to improve the model; then, go to 1.

There are two problems with the above approach:

• Tuning instability (that complicates the above step 2);

• Value variability (that complicates the above step 3).

Tuning instability refers to the problem of tuning a model to some local domain. Ideally, there is enough local data to clearly define what outputs are expected from a model. In practice, this may not be the case so the second step of data farming, grow the data, results in very large variances in model performance.

Value variability is the point of this chapter. After doing everything we can to tame tuning instability, we still need to search the resulting space of options in order to make a recommendation that is useful for the user. If, during the third step (harvest), we change the value proposition used to guide that search then we get startlingly different recommendations.

The next two sections offer more details on tuning instability and value variability. While these two terms have many differences, they relate to a similar concept:

• Tuning instability refers to uncertainties inside a model;

• Value variability refers to uncertainty on how to assess the outputs of a model.

23.2.2.2 Value variability

Another source of variability in a model are the goals (a.k.a. values) used to generate that model. There are a surprisingly large number of ways to assess the outputs of models of software systems. For example, consider something as seemingly simple as a defect predictor. Such detectors read code and point to regions with larger odds of having bugs. What could be simpler than that?

As it turns out, defect predictors can be assessed on many criteria such as those listed in Figure 23.1. In that figure, support comments on how much training data was used to build this detector. Also, effort looks at how many lines of code are selected by the detector. Finally, reward comments on the ease of finding bugs. If reward is high, then an analyst can find many bugs after reading a small part of the code.

Figure 23.2 lists other performance measures that we have seen at client sites or in the literature. There are two important features of this figure:

1. This list is very long.

2. This list keeps growing.

As to this second point, often when we work with new clients, they surprise us with yet another domain-specific criteria that is important for the business. That is, neither Figure 23.1 nor Figure 23.2 is a complete list of all possible assessment criteria.

Our reading of the software engineering literature is that most papers only explore a small subset of Figure 23.1 or Figure 23.2. We think this is a mistake, and researchers should do more to create a more general framework where they explore a wide and changing set of evaluation criteria. The next section describes one such framework.

23.3.1 Representing value propositions

A value function should model the goals of the business users who are making project decisions about some software development. We will explore two:

• BFC = Better, faster, cheaper.

• XPOS = Risk exposure.

Value proposition #1- Better, faster, cheaper (BFC). Ideally, software is built with fewer defects D, using less effort E, and in shorter time T. A value function for this goal can be modeled as the Euclidean distance to minimum effort, time, defects:

$\mathit{bfc}=\sqrt{f{\overline{T}}^2+c{\overline{E}}^2+{\left(b\overline{D}\left(1+{1.8}^{\mathit{rely}-3}\right)\right)}^2}$

${\mathit{value}}_{\mathit{bfc}}=\frac{1}{\mathit{bfc}}$

In the above, value is highest when defects and effort and development time are lowest. Also, 0 ≤ (b, f, c) ≤ 1 represents the business importance of (better, faster, cheaper). For this study, we use b = f = c = 1. In other work, we have explored the effects of using other b, f, and c values [304].

In Equation (23.3), $\overline{T}$, $\overline{E}$, and $\overline{D}$ are the time, effort, and defect scores normalized zero to one. Equation (23.3) models the business intuition that defects in high-reliability systems are exponentially more troublesome than in low-reliability systems:

• In the COCOMO model, variables have the range 1 ≤ x ≤ 6 and at x = 3, the variable's influence on the output is nominal; in other words, its impact on effort is to multiply it by one (which is to say, it leaves it unchanged).

• In the COCOMO model, if reliability moves from very low to very high (1 to 6), the term 1.8^rely–3 models a function that (a) is ten times larger for very high than very low reliability systems; and (b) passes through 1 at rely = 3 (so systems with nominal reliability do not change the importance of defects).

Value proposition #2- Risk exposure (XPOS). The BFC value function is somewhat idealistic in that it seeks to remove all defects by spending less money on faster developments. An alternate value function comes from Huang and Boehm [183]. This alternate value function, which we call XPOS, models the situation where a software company must rush a product to market, without compromising too much on software quality. Based on Huang's PhD dissertation [182], we operationalize XPOS as follows.

Huang defines business risk exposure (RE) as a combination of software quality investment risk exposure (RE_q) and market share erosion risk exposure (RE_m). We invert that expression to yield value_XPOS (so an exposed project has low value):

$\mathit{RE}=R{E}_q+R{E}_m$

${\mathit{value}}_{\mathit{XPOS}}=\frac{1}{\mathit{RE}}$

RE_q values high-quality software and therefore prioritizes quality over time. RE_q is composed of two primary components: probability of loss due to unacceptable quality P_q(L) and size of loss due to unacceptable quality S_q(L). P_q(L) is calculated based on defects. S_q(L) is calculated based on complexity (the COCOMO cplx feature), reliability (rely), and a cost function. S_c is a value from a Pareto-valued table based on rely. We choose the project months estimate as the basis of this cost function.

$R{E}_q=P_q\left(L\right)*S_q\left(L\right)$

$P_q\left(L\right)=\frac{\mathit{defects}}{\mathit{defect}{s}_{\mathit{vl}}}$

$S_q\left(L\right)=3^{\frac{\mathit{cplx}-3}{2}}·\mathit{PM}·S_c$

In Equation (23.8), defects_vl is the lower bound on defects for that project.

In Equation (23.9), the $\frac{\mathit{cplx}-3}{2}$ term is similar to the $\overline{D}$ coefficient inside Equation (23.3): if complexity changes below or above 3, then it reduces or adds (respectively) to the unacceptable quality risk. However, at cplx = 3, the multiplier is one (i.e., no effect).

RE_m values a fast time-to-market and therefore prioritizes time over quality. RE_m is calculated from PM and reliability (rely). M_c is a value from a exponential-valued table based on rely.

$R{E}_m=\mathit{PM}·M_c$

23.4.1 Project options: P

COCOMO and COQUALMO's features are shown in Figure 23.3 and Figure 23.4. The features have a range taken from {very low, low, nominal, high, very high, extremely high} or

$\left\{\mathit{vl}=1,l=2,n=3,h=4,\mathit{vh}=5,\mathit{xh}=6\right\}$

These features include manual methods for defect removal. High values for peer reviews (or pr, see Figure 23.4) denote formal peer group review activities (participants have well-defined and separate roles, the reviews are guided by extensive review checklists/root cause analysis, and reviews are a continuous process guided by statistical control theory [397]).

COQUALMO also models automatic methods for defect removal. Chulani [99] defines the top half of automated analysis as

4 (high): intermediate-level module and intermodule code syntax and semantic analysis. Simple requirements/design view consistency checking.

5 (very high): More elaborate requirements/design view consistency checking. Basic distributed processing and temporal analysis, model checking, symbolic execution.

6 (extremely high): Formalized¹ specification and verification. Temporal analysis, model checking, symbolic execution.

The top half of execution-based testing and tools is

4 (high): Well-defined test sequence tailored to organization (acceptance / alpha / beta / flight / etc.) test. Basic test coverage tools, test support system.

5 (very high): More advanced tools, test data preparation, basic test oracle support, distributed monitoring and analysis, assertion checking. Metrics-based test process management.

6 (extremely high): Highly advanced tools: oracles, distributed monitoring and analysis, assertion checking. Integration of automated analysis and test tools. Model-based test process management.

In the sequel, the following observation will become important: Figure 23.3 is much longer than Figure 23.4. This reflects a modeling intuition of COCOMO/COQUALMO: it is better to prevent the introduction of defects (using changes to Figure 23.3) than to try and find them once they have been introduced (using Figure 23.4).

23.4.2 Tuning options: T

For COCOMO effort multipliers (the features that that affect effort/cost in a linear manner), the off-nominal ranges {vl=1, l=2, h=4, vh=5, xh=6} change the prediction by some ratio. The nominal range {n=3}, however, corresponds to an effort multiplier of 1, causing no change to the prediction. Hence, these ranges can be modeled as straight lines y = mx + b passing through the point (x, y)=(3, 1). Such a line has a y-intercept of b = 1 − 3m. Substituting this value of b into y = mx + b yields:

$\forall x\in \left\{1..6\right\}E{M}_i=m_{\alpha }\left(x-3\right)+1$

where m_α is the effect of α on effort/cost.

We can also derive a general equation for the features that influence cost/effort in an exponential manner. These features do not “hinge” around (3,1) but take the following form:

$\forall x\in \left\{1..6\right\}S{F}_i=m_{\beta }\left(x-6\right)$

where m_β is the effect of factor i on effort/cost.

COQUALMO contains equations of the same syntactic form as Equation (23.13) and Equation (23.14), but with different coefficients. Using experience for 161 projects [42], we can find the maximum and minimum values ever assigned to m for COQUALMO and COCOMO. Hence, to explore tuning variance (the t ∈ T term in Equation (23.12)), all we need to do is select m values at random from the min/max m values ever seen.

23.5.1 Case studies: p ⊆ P

We use p to denote the subset of the project options p_i ⊆ P relevant to particular projects. The four particular projects p₁, p₂, p₃, p₄ used as the case studies of this chapter are shown in Figure 23.5:

• OSP is the GNC (guidance, navigation, and control) component of NASA's Orbital Space Plane.

• OSP2 is a later version of OSP.

• Flight and ground systems reflect typical ranges seen at NASA's Jet Propulsion Laboratory.

Some of the features in Figure 23.5 are known precisely (see all the features with single fixed settings). But many of the features in Figure 23.5 do not have precise settings (see all the features that range from some low to high value). Sometimes the ranges are very narrow (e.g., the process maturity of JPL ground software is between 2 and 3), and sometimes the ranges are very broad.

Figure 23.5 does not mention all the features listed in Figure 23.3 inputs. For example, our defect predictor has inputs for use of automated analysis, peer reviews, and execution-based testing tools. For all inputs not mentioned in Figure 23.5, ranges are picked at random from (usually) {1, 2, 3, 4, 5}.

23.5.1.1 Searching for r_x

Our search runs two phases: a forward select and a back select phase. The forward select grows r_x, starting with the empty set. At each round i in the forward select one or more ranges (e.g., acap = 3) are added to r_x. The resulting r_x set found at round i is denoted rⁱ_x.

The forward select ends when the search engine cannot find more ranges to usefully add to rⁱ_x. Before termination, we say that the open features at round i are the features in Figure 23.3 and Figure 23.4 not mentioned by any range in rⁱ_x. The value of rⁱ_x is assessed by running the model N times with

1. All of rⁱ_x.

2. Any t ∈ T, selected at random.

3. Any range at random for open features.

In order to ensure minimality, a back select checks if the final r_x set can be pruned. If the forward select caches the simulation results seen at each round i, the back select can perform statistical tests to see if the results of round i − 1 are significantly different from round i. If the difference is not statistically significant, then the ranges added at round i are pruned away and the back select recurses for i − 1. We call the unpruned ranges the selected ranges and the point where pruning stops the policy point.

For example, in Figure 23.6, the policy point is round 13 and the decisions made at subsequent rounds are pruned by the back select. That is, the treatments returned by our search engines are all the ranges rⁱ_x for 1 ≤ i ≤ 13. The selected ranges are shown in a table at the bottom of the figure and the effects of applying the conjunction of ranges in r¹³_x can be seen by comparing the values at round=0 to round=13:

• Defects/KLOC reduced: 350 to 75;

• Time reduced: 16 to 10 months;

• Effort reduced: 170 to 80 staff months.

23.5.2 Search methods

Elsewhere, we have proposed and studied various methods for implementing the forward select using

• Simulated annealing: a classic nonlinear optimizer.

• MaxWalkSat: a local search algorithm from the 1990s [382].

• Various standard AI methods such as Beam search, ISSAMP, and A-Star [84].

Of all these, our own variant of MaxWalkSat called SEESAW performed best [304]. Hence, this rest of this chapter will discuss SEESAW.

While searching the ranges of a feature, this algorithm exploits the monotonic nature of Equation (23.13) and Equation (23.14). SEESAW ignores all ranges except the minimum and maximum values for a feature in p. Like MaxWalkSat, the feature chosen on each iteration is made randomly. However, SEESAW has the ability to delay bad decisions until the end of the algorithm (i.e., decisions where constraining the feature to either the minimum or maximum value results in a worse solution). These treatments are then guaranteed to be pruned during the back select.