Slide 1Features incur a costExample: Survival Prediction for Lung CancerA cascade of linear classifiersSequential Training of cascadesContributions of this paperNotationSoft CascadeSome properties of soft cascadesJoint cascade trainingAccuracy vs CostModeling the expected costExperimentsSurvival Prediction for Lung CancerSlide 15Methods comparedEvaluation ProcedureResultsComputer aided diagnosisTest set FROC CurvesConclusionsRelated workSome open issuesDesigning Efficient Cascaded Classifiers:Tradeoff between Accuracy and CostVikas Raykar Balaji Krishnapuram Shipeng YuSiemens HealthcareKDD 2010Features incur a cost•Features are acquired on demand.•A set of features can be acquired as a group.•Each feature group incurs a certain cost.•Acquisition cost can be either–Computational | fast detectors–Financial | expensive medical tests–Human discomfort | biopsyExample: Survival Prediction for Lung CancerFeature Group Number of featuresexamples Cost1 clinical features 9 gender, age 0 no cost2 features before therapy8 lung function creatinine clearance13 imaging /treatment features7 gross tumor volume treatment dose24 blood bio-markers 21 Interleukin-8 Osteopontin5 expensive•2-year survival prediction for lung cancer patients treated with chemo/radiotherapy increasing predictive power … increasing acquisition cost increasing predictive power … increasing acquisition costA cascade of linear classifiersStage 1Stage 2 Stage 3 increasing predictive power increasing acquisition cost increasing predictive power increasing acquisition cost• Training each stage of the cascade• Choosing the thresholds for each stageSequential Training of cascadesStage 1Stage 2 Stage 3•Conventionally each stage is trained using only examples that pass through all the previous stages.•Training depends on the choice of the thresholds. •For each choice of threshold we have to retrain.Contributions of this paper•Joint training of all stages of the cascade.–Notion of probabilistic soft cascades•A knob to control the tradeoff between accuracy vs cost–Modeling the expected feature cost•Decoupling the classifier training and threshold selection.–Post-selection of thresholdsNotationStage 1Stage 2 Stage KSoft Cascade•Probabilistic version of the hard cascade.•An instance is classified as positive if all the K stages predict it as positive.•An instance is classified as negative if at least one of the K classifiers predicts it as negative.Some properties of soft cascades•Sequential ordering of the cascade is not important.•Order definitely matters during testing.•A device to ease the training process.•We use a maximum a-posteriori (MAP) estimate with Laplace prior on the weights.Joint cascade training•Once we have a probabilistic cascade we can write the log-likelihood.•We impose a Laplacian prior. •Maximum a-posteriori (MAP) estimateAccuracy vs Cost•We would like to find the MAP estimate subject to the constraint that the expected cost for a new instance•The expectation is over the unknown test distribution. •Since we do not know the test distribution we estimate this quantity based on the training set.Modeling the expected costStage 1Stage 2 Stage 3For a given instance CostStage 1Stage 2Stage 3We optimize using cyclic coordinate descentExperiments•Medical Datasets–Personalized medicine•Survival prediction for lung cancer•Tumor response prediction for rectal cancer–Computer aided diagnosis for lung cancerSurvival Prediction for Lung CancerFeature Group Number of featuresexamples Cost1 clinical features 9 gender, age 0 no cost2 features before therapy8 lung function creatinine clearance13 imaging /treatment features7 gross tumor volume treatment dose24 blood bio-markers 21 Interleukin-8 Osteopontin5 expensive•2-year survival prediction for advanced non-small cell lung cancer (NSCLC) patients treated with chemo/radiotherapy.•82 patients treated at MAASTO clinic among which 24 survived two yearsPathological Complete Response (pCR) Prediction for Rectal CancerFeature Group Number of featuresCost1 Clinical features 6 02 CT/PET scan features before treatment2 13 CT/PET scan features after treatment2 10•Predict tumor response after chemo/radiotherapy for locally advanced rectal cancer•78 patients (21 had pCR)Methods compared•Single stage classifier•Proposed soft cascade–With beta = 0–Varying beta•Sequential Training–Logistic Regression–AdaBoost [Viola-Jones cascade]–LDAEvaluation Procedure•70 % for training 30 % for testing•Area under the ROC Curve•Normalized average cost per patient–Using all the features has a cost of 1•Results averages over 10 repetitions•Thresholds for each stage chosen using a two-level hierarchical grid searchResultsComputer aided diagnosisFeature Group Number of featuresAverage Cost1 9 1.07 secs2 23 3.10 secs3 25 20.7 secs•Motivation here is to reduce the computational cost•196 CT scans with 923 positive candidates and 54455 negative candidates.Test set FROC CurvesConclusions•Joint training of all stages of the cascade.–Notion of probabilistic soft cascades•A knob to control the tradeoff between accuracy vs cost–Modeling the expected feature costRelated workSome open issues•Order of the cascade•The accuracy vs cost knob is not sensitive in all problem